Pareto Optimization for Single Machine Scheduling with Controllable Processing Time to Minimize Total Weighted Completion Times

doi:10.12005/orms.2016.0005

Operations Research and Management Science ›› 2016, Vol. 25 ›› Issue (1): 35-45.DOI: 10.12005/orms.2016.0005

• Theory Analysis and Methodology Study • Previous Articles Next Articles

Pareto Optimization for Single Machine Scheduling with Controllable Processing Time to Minimize Total Weighted Completion Times

WANG Du-juan¹, LIU Feng², WANG Jian-jun¹, WANG Yan-zhang¹

1.School of Management Science and Engineering, Dalian University of Technology, Dalian 116024, China;
2.School of Management Science and Engineering, Dongbei University of Finance and Economics, Dalian 116025, China

Received:2014-09-25 Online:2016-02-25

加工时间可控单机加权总完工时间Pareto优化研究

王杜娟¹, 刘锋², 王建军¹, 王延章¹

1.大连理工大学管理科学与工程学院,辽宁大连 116024;
2.东北财经大学管理科学与工程学院,辽宁大连 116025

作者简介:王杜娟(1981-),女,河北高邑人,博士,讲师,研究方向为服务干扰管理和智能优化算法。刘锋(1985-),男,河北石家庄人,博士,讲师,研究方向为服务干扰管理和智能优化算法;王建军(1977-),男,河北保定市人,博士,副教授,博士生导师,研究方向干扰管理、服务管理等;王延章(1952-),男,辽宁开原人,博士,教授,博士生导师,研究方向为复杂系统建模和智能优化算法。
基金资助:
国家自然科学基金项目(71501024;71502026;71271039;70902033);教育部“新世纪优秀人才支持计划”项目(NCET-13-0082);中央高校基本科研业务费专项资金资助项目(DUT15QY32;DUT14YQ211)

Abstract

Abstract: For single machine scheduling problem minimizing total weighted completion time, when job’s processing time could be compressed by allocating extra resources, jobs’ processing sequence and compression times are optimized simultaneously. Two in-conflicts objectives are concerned: schedule performance measured by compressed jobs’ total weighted completion times, and resource cost measured by linear function of jobs’ compression times. The problem has been proved to be NP-hard. In order to bridge the gap that this problem has rarely been solved from the perspective of Pareto optimization, we make use of algorithm hybridization to improve classic NSGA-II which tends to be pre-mature during evolution. In hybridized algorithm, Archived Multi-Objective Simulated Annealing(AMOSA) is integrated to jump out of local optimum, external archive is built up to enhance population diversity, and master/slave parallel structure is designed to improve solving efficiency. Finally for verification purposes, first hybridized algorithm is used to solve Benchmark test functions ZDT1-6, and the results demonstrate that the proposed method is applicable and effective for test functions with various structures and shapes. Second, problem features are utilized to design effective encoding scheme and correspondingly randomly generated problem instances are solved. The analysis of proximity and diversity of obtained Pareto front further verify the effectiveness of hybridized algorithm for solving single machine scheduling with controllable processing time to minimize total weighted completion times.

Key words: controllable processing time, parallel hybrid algorithm, diversity, proximity, pareto optimization

摘要： 针对单机环境最优化加权总完工时间问题,当工件加工时间可通过分配资源进行压缩时,研究对工件的加工次序和时间压缩量的优化,从而权衡调度性能目标和资源成本目标。调度性能目标为压缩后工件的加权总完工时间,资源成本目标为工件压缩量的线性函数。此问题复杂性已被证明为NP-hard,为弥补较少有研究从Pareto优化角度求解该问题有效前沿的不足,针对经典NSGA-II求解时易早熟收敛的特点,采用算法混合方式进行优化方法研究。融合归档式多目标模拟退火算法跳出局部极值的优势,启用外部存档策略提升种群的多样性,采用主从模式的并行结构提升求解效率。最后为检验优化方法的有效性,一方面通过对Benchmark测试函数ZDT1-6的求解,表明混合算法对不同结构和形状目标函数兼具普适性和有效性;另一方面结合问题特点设计有效编码方式,针对随机生成算例进行求解。通过分析有效前沿收敛性和多样性,验证了所提方法对于优化加工时间可控单机加权总完工时间问题的有效性。

关键词: 加工时间可控, 并行混合算法, 多样性, 收敛性, Pareto优化

CLC Number:

TP29

WANG Du-juan, LIU Feng, WANG Jian-jun, WANG Yan-zhang. Pareto Optimization for Single Machine Scheduling with Controllable Processing Time to Minimize Total Weighted Completion Times[J]. Operations Research and Management Science, 2016, 25(1): 35-45.

王杜娟, 刘锋, 王建军, 王延章. 加工时间可控单机加权总完工时间Pareto优化研究[J]. 运筹与管理, 2016, 25(1): 35-45.

References

[1] Shabtay D, Steiner G. A survey of scheduling with controllable processing times[J]. Discrete Applied Mathematics, 2007, 155(13): 1643-1666.
[2] Akturk M S, Atamturk A, Gurel S. Parallel machine match-up scheduling with manufacturing cost considerations[J]. Journal of Scheduling, 2010, 13(1): 95-110.
[3] 史烨,李凯,左春荣.加工时间依赖于资源消耗量的平行机调度问题[J].系统工程理论与实践,2012,32(07):1485-1493.
[4] Vickson R G. Choosing the job sequence and processing times to minimize total processing plus flow cost on a single machine[J]. Operations Research, 1980, 28(5): 1155-1167.
[5] Wan G H, Yen B, Li C L. Single machine scheduling to minimize total compression plus weighted flow cost is NP-hard[J]. Information Processing Letters, 2001, 79(6): 273-280.
[6] Janiak A, Kovalyov M Y, Kubiak W, et al. Positive half-product and scheduling with controllable processing times[J]. European Journal of Operational Research, 2005, 165(2): 413- 422.
[7] 唐恒永,赵琨.带有资源消耗的加权总完工时间单机排序问题[J].系统工程与电子技术,2004,26(11):1601-1603.
[8] 谢谢,赵传立,唐立新.一类加工时间依赖资源的单机排序问题[J].数学的实践与认识,2008,38(16):69-75.
[9] Wang J B, Xia Z Q. Single machine scheduling problems with controllable processing times and total absolute differences penalties[J]. European Journal of Operational Research, 2007, 177(1): 638- 645.
[10] Cheng T C E, Janiak A. Resource optimal control in some single-machine scheduling problem[J]. IEEE Transactions on Automatic Control, 1994, 39(6): 1243-1246.
[11] Jansen K., Mastrolilli M. Approximation schemes for parallel machine scheduling problem with controllable processing times[J], Computers & Operations Research, 2004, 31(10): 1565-1581.
[12] 李凯,史烨,马英.具有凸资源消耗函数的最小化Makespan的平行机调度问题[J].管理工程学报,2013,27(1):56- 62.
[13] Cheng T C E, Chen Z L, Li C L, Single-machine scheduling with trade-off between number of tardy jobs and resource allocation[J]. Operations Research Letters, 1996, 19(5): 237-242.
[14] Li B, Wang L. A hybrid quantum-inspired genetic algorithm for multiobjective flow shop scheduling[J]. IEEE Transactions on Systems, Man, and Cybernetics, Part B: Cybernetics, 2007, 37(3): 576-591.
[15] Deb K, Pratap A, Agarwal S, et al. A fast and elitist multiobjective genetic algorithm: NSGA-II[J]. IEEE Transactions on Evolutionary Computation. 2002, 6(2): 182-197.
[16] 刘锋,王建军,杨德礼,等.面向多目标优化的一种混合进化算法[J].运筹与管理,2012,21(4):15-21.
[17] Zitzler E, Deb K, Thiele L. Comparison of multiobjective evolutionary algorithms: empirical results[J]. Evolutionary Computation, 2000, 8(2): 173-195.
[18] Hoogeveen H, Woeginger G J. Some comments on sequencing with controllable processing times[J]. Computing, 2002, 68(2): 181-192.
[19] Service T C. A No Free Lunch theorem for multi-objective optimization[J]. Information Processing Letters, 2010, 110(21): 917-923.
[20] Bandyopadhyay S, Saha S, Maulik U, et al. A simulated annealing-based multiobjective optimization algorithm: AMOSA[J]. IEEE Transactions on Evolutionary Computation, 2008, 12(3): 269-283.
[21] Linder M, Sekaj I. Parallel genetic algorithms. 17th international conference on soft computing[C], Mendel, 2011. 9-15.
[22] C∨repinek M, Liu S, Mernik M. Exploration and exploitation in evolutionary algorithms: a survey[J]. ACM Computing Surveys, 2013,45(3):1-33.
[23] Ishibuchi H, Tsukamoto N, Nojima Y. Diversity improvement by non-geometric binary crossover in evolutionary multiobjective optimization[J]. IEEE Transactions on Evolutionary Computation, 2010,14(6): 985-998.
[24] Nearchou A C. Scheduling with controllable processing times and compression costs using population-based heuristics[J]. International Journal of Production Research, 2010, 48(23): 7043-7062.
[25] Alba E, Luque G, Nesmachnow S. Parallel metaheuristics: recent advances and new trends[J]. International Transactions in Operational Research, 2013, 20(1): 1- 48.
[26] Van Veldhuizen D A, Zydallis J B, Lamont G B. Considerations in engineering parallel multiobjective evolutionary algorithms[J]. IEEE Transactions on Evolutionary Computation, 2003, 7(2): 144-173.
[27] Suman B, Kumar P. A survey of simulated annealing as a tool for single and multiobjective optimization[J]. Journal of the Operational Research Society, 2006, 57(10): 1143-1160.

Pareto Optimization for Single Machine Scheduling with Controllable Processing Time to Minimize Total Weighted Completion Times

加工时间可控单机加权总完工时间Pareto优化研究

PDF

Knowledge

Abstract

Cite this article

share this article

References

Related Articles 2

Recommended Articles

Metrics

[1]	LIU Xiao-hui, PENG Xiao-hong, CHI Guo-tai, LI Gang, GUO Yu-xin, CHEN Kai. Research on Profitability Difference Based on the Theil Index [J]. Operations Research and Management Science, 2020, 29(7): 123-130.
[2]	GUI Hua-ming, ZHANG Lin-lan, GUAN Xu. Study on Investment Coordination Strategy for Constructing the Capacity of Production-Line Inventory under JIT Environment [J]. Operations Research and Management Science, 2014, 23(4): 238-245.