Job-shop Scheduling Model and Algorithm with Machine Deterioration
-
摘要: 考虑到现实作业车间调度中设备具有恶化特性,针对作业的处理时间是开始时间的线性递增函数的作业车间调度问题, 建立了以最小化最迟完成时间为目标的优化模型,进而设计了嵌套分割算法进行求解.该算法在抽样阶段嵌入单亲遗传算法以提高抽样的多样性和质量. 实例结果表明,所提出的算法在解决该问题上可以获得较高质量的解,并且具有很好的鲁棒性.Abstract: For the job-shop scheduling problem, a job-shop scheduling model with machine deterioration is built in order to minimize makespan, considering that the processing time of jobs is a linearly increasing function of the start time. Then a nested partition method is designed for solving it. In the sampling process, the partheno-genetic algorithm is embedded into the nested partition method in order to ensure the diversity of sampling and quality. Simulation experiments show that the proposed algorithm for solving job-shop scheduling problem with machine deterioration can get higher quality solutions and have a better robustness.
-
[1] Brucker P. Scheduling Algorithms. Berlin: Springer-Verlag, 2007. 69-83 [2] [2] Blazewicz J, Domschke W, Pesch E. The job shop scheduling problem: conventional and new solution techniques. European Journal of Operational Research, 1996, 93(1): 1-33 [3] [3] Wang L, Tang D B. An improved adaptive genetic algorithm based on hormone modulation mechanism for job-shop scheduling problem. Expert Systems with Applications, 2011, 38(6): 7243-7250 [4] Qiao Wei, Wang Bing, Sun Jie. Uncertain job shop scheduling problems solved by genetic algorithm. Computer Integrated Manufacturing Systems, 2007, 13(12): 2452-2455(乔威, 王冰, 孙洁. 用遗传算法求解一类不确定性作业车间调度问题. 计算机集成制造系统, 2007, 13(12): 2452-2455) [5] Li Fu-Ming, Zhu Yun-Long, Yin Chao-Wan, Song Xiao-Yu. Research on fuzzy job shop scheduling with alternative machines. Computer Integrated Manufacturing Systems, 2006, 12(2): 169-173(李富明, 朱云龙, 尹朝万, 宋晓宇. 可变机器约束的模糊作业车间调度问题研究. 计算机集成制造系统, 2006, 12(2): 169-173) [6] Yan Li-Jun, Li Zong-Bin, Wei Jun-Hu, Du Xuan. A new hybrid optimization algorithm and its application in job shop scheduling. Acta Automatica Sinica, 2008, 34(5): 604-608(闫利军, 李宗斌, 卫军胡, 杜轩. 一种新的混合优化算法及其在车间调度中的应用. 自动化学报, 2008, 34(5): 604-608) [7] [7] Gupta J N D, Gupta S K. Single facility scheduling with nonlinear processing times. Computers and Industrial Engineering, 1988, 14(4): 387-393 [8] [8] Wu H P, Huang M. Improved estimation of distribution algorithm for the problem of single-machine scheduling with deteriorating jobs and different due dates. Computational and Applied Mathematics, 2014, 33(3): 557-573 [9] [9] Mosheiov G. Scheduling jobs under simple linear deterioration. Computers and Operations Research, 1994, 21(6): 653 -659 [10] Wu C C, Wu W H, Wu W H, Hsu P H, Yin Y Q, Xu J Y. A single-machine scheduling with a truncated linear deterioration and ready times. Information Sciences, 2014, 256: 109-125 [11] Cheng M B, Tadikamalla P R, Shang J, Zhang S Q. Bicriteria hierarchical optimization of two-machine flow shop scheduling problem with time-dependent deteriorating jobs. European Journal of Operational Research, 2014, 234(3): 650-657 [12] Wang J B, Wang M Z. Solution algorithms for the total weighted completion time minimization flow shop scheduling with decreasing linear deterioration. The International Journal of Advanced Manufacturing Technology, 2013, 67(1-4): 243-253 [13] Liu C H, Chen L S, Lin P S. Lot streaming multiple jobs with values exponentially deteriorating over time in a job-shop environment. International Journal of Production Research, 2013, 51(1): 202-214 [14] Mosheiov G. Complexity analysis of job-shop scheduling with deteriorating jobs. Discrete Applied Mathematics, 2002, 117(1-3): 195-209 [15] Liu C H. Scheduling jobs with values exponentially deteriorating over time in a job shop environment. In: Proceedings of the 2011 International MultiConference of Engineers and Computer Scientists. Hong Kong, China: Newswood Limited, 2011. 1113-1118 [16] Araghi M E T, Jolai F, Rabiee M. Incorporating learning effect and deterioration for solving a SDST flexible job-shop scheduling problem with a hybrid meta-heuristic approach. International Journal of Computer Integrated Manufacturing, 2013, 27(8): 733-746 [17] Garey M R, Johnson D S, Sethi R. The complexity of flow shop and job shop scheduling. Mathematics of Operations Research, 1976, 1(2): 117-129 [18] Shi L, lafsson S. Nested Partitions Method, Theory and Applications. New York: Springer-Verlag, 2008. 131-226 [19] Shi L, lafsson S. Nested partitions method for global optimization. Operations Research, 2000, 48(3): 390-407 [20] Wang Y M, Yin H L, Qin K D. A novel genetic algorithm for flexible job shop scheduling problems with machine disruptions. The International Journal of Advanced Manufacturing Technology, 2013, 68(5-8): 1317-1326
点击查看大图
计量
- 文章访问数: 1975
- HTML全文浏览量: 83
- PDF下载量: 1302
- 被引次数: 0