考虑外包的平行机调度问题的多目标遗传算法

中国机械工程 ›› 2014, Vol. 25 ›› Issue (23): 3174-3179.

考虑外包的平行机调度问题的多目标遗传算法

孙超平1,2;杨平1;李;凯1,2

1.合肥工业大学，合肥，230009
2.过程优化与智能决策教育部重点实验室，合肥，230009

出版日期:2014-12-10 发布日期:2014-12-12
基金资助:
国家自然科学基金资助项目（71101040，71471052）；安徽省自然科学基金资助项目（1408085MG136）；教育部人文社会科学研究规划基金资助项目（14YJA630051）

Multi-objective Genetic Algorithm for Parallel Machine Scheduling Problem with Outsourcing

Sun Chaoping1,2;Yang Ping1;Li Kai1,2

1.Hefei University of Technology,Hefei,230009
2.Key Laboratory of Process Optimization and Intelligent Decision-making,Ministry of Education,Hefei,230009

Online:2014-12-10 Published:2014-12-12
Supported by:
National Natural Science Foundation of China（No. 71101040，71471052）;Anhui Provincial Natural Science Foundation of China（No. 1408085MG136）

摘要/Abstract

摘要：

研究了一类考虑外包的平行机调度问题，目标是使作业外包总成本与最大完工时间同时最小化。通过对该类问题进行形式化描述与分析，设计了一种数字串形式的解的表示方法，其中每位数字表示固定作业对应的机器编号，该方法能够有效缩小解空间，从而提高搜索效率。进而构建了一种带精英策略的非支配遗传算法PD-NSGA-Ⅱ，为该类多目标调度问题提供Pareto最优解集。大量数据实验结果表明，所构造的PD-NSGA-Ⅱ算法能够在合理的时间内有效求解该类调度问题，其解的质量与计算效率均优于SPEA算法。

关键词: 平行机调度, 外包, Pareto最优, 非支配遗传算法

Abstract:

This paper considered the parallel machine scheduling without sourcing, aiming to minimize both the total cost of outsourcing and the makespan simultaneously. On the careful analysis, a solution indicating method in a form of numeric string was designed, where every number represented the corresponding machine number of the fixed job. This method could reduce the solution effectively,thus improve the searching efficiency. Then a non-dominated sorting genetic algorithm with the elite strategy, PD-NSGA-Ⅱ was constructed, which could provide Pareto optimal solution sets of high quality to solve these multi-objective scheduling problems. Experimental results indicated that the PD-NSGA-Ⅱ algorithm could solve the scheduling problem within a reasonable period of time. The proposed PD-NSGA-Ⅱ algorithm, superior to SPEA, demonstrated an excellent performance in terms of solution quality and the computation time.

Key words: parallel machine scheduling, outsourcing, Pareto optimization, non-dominated sorting genetic algorithm Ⅱ(NSGA-Ⅱ)

中图分类号:

O223

孙超平, 杨平, 李, 凯, . 考虑外包的平行机调度问题的多目标遗传算法[J]. 中国机械工程, 2014, 25(23): 3174-3179.

Sun Chaoping, Yang Ping, Li Kai, . Multi-objective Genetic Algorithm for Parallel Machine Scheduling Problem with Outsourcing[J]. China Mechanical Engineering, 2014, 25(23): 3174-3179.

参考文献

[1]Lenstra J K, Rinnooy Kan A H G, Brucker P. Complexity of Machine Scheduling Problems[J]. Annals of Discrete Mathematics, 1997，1: 343-362.
[2]Graham R L. Boundson Multiprocessor Timing Anomalies[J]. SIAM Journal on Applied Mathematics, 1969, 17: 416-429.
[3]Coffman E G, Garey M R, Johnson D S. An Applicationof Bin-packing to Multipossor Scheduling[J]. SIAM Journal on Computing, 1978, 7: 1-17.
[4]Friesen D K. Tighter Bounds for the Multifit Processor Scheduling Algorithm[J]. SIAM Journal on Computing, 1984, 13: 170-181.
[5]Thesen A. Designand Evaluation of Tabu Search Algorithms for Multiprocessor Scheduling[J]. Journal of Heuristics, 1998, 4: 141-160.
[6]Lee W C, Wu C C, Chen P. A Simulated Annealing Approach to Makespan Minimizationon Identical Parallel Machines[J]. International Journal of Advanced Manufacturing Technology, 2006, 31:328-334.
[7]李凯, 左春荣. 基于模拟退火的多处理机调度优化算法研究[J]. 系统工程与电子技术, 2009, 31(12): 2963-2967.
Li Kai, Zuo Chunrong. Research on Optimization Algorithm for Multiprocessor Scheduling Problem Based on Simulated Annealing[J]. Systems Engineering and Electronics, 2009,31(12): 2963-2967.
[8]Nowicki E, Zdrzaka S. A Bicriterion Approach to Preemptive Scheduling of Parallel Machines with Controllable Job Processing Times[J]. Discrete Applied Mathematics, 1995, 63: 237-256.
[9]Li K, Shi Y, Yang S, et al. Parallel Machine Scheduling Problem to Minimize Makespan with Resource Dependent Processing Times[J]. Applied Soft Computing, 2011,11(8): 5551-5557.
[10]Jansen K, Mastrolilli M. Approximation Schemesfor Parallel Machine Scheduling Problem with Controllable Processing Times[J]. Computers & Operations Research, 2004, 31: 1565-1581.
[11]史烨, 李凯, 左春荣. 加工时间依赖于资源消耗量的平行机调度问题[J]. 系统工程理论与实践, 2012,32(7): 1485-1493.
Shi Ye, Li Kai, Zuo Chunrong. Parallel Machine Scheduling Problem with Resource Dependent Processing Times[J]. Systems Engineering-Theory & Practice, 2012,32(7): 1485-1493.
[12]Shabtay D, Kaspi M. Parallel Machine Schedulingwith a Convex Resource Consumption Function[J]. European Journal of Operational Research, 2006, 173(1): 92-107.
[13]李凯, 史烨, 马英. 具有凸资源消耗函数的最小化Makespan的平行机调度问题[J]. 管理工程学报, 2013, 27(1):56-62.
Li Kai, Shi Ye, Ma Ying. Parallel Machine Scheduling Problems with a Convex Resource Consumption Function to Minimize the Makespan[J]. Journal of Industrial Engineering/Engineering Management, 2013; 27(1):56-62.
[14]Vidal J C, Mucientes M, Bugarí N A,et al. Machine Schedulingin Custom Furniture Industry Through Neuro-evolutionary Hybridization[J]. Applied Soft Computing, 2011, 11: 1600-1613.
[15]Bandyopadhyay S, Bhattacharya R. Solving Multi-objective Parallel Machine Scheduling Problem by a Modified NSGA-Ⅱ[J]. Applied Mathematical Modelling, 2013, 37: 6718-6729.
[16]Guo Z X, Wong W K, Li Z,et al. Modeling and Pareto Optimization of Multi-objective Order Scheduling Problems in Production Planning[J]. Computers & Industrial Engineering, 2013, 64: 972-986.