随机返工及重加工情形下的Job-Shop调度问题

工业工程 ›› 2015, Vol. 18 ›› Issue (5): 127-133.

随机返工及重加工情形下的Job-Shop调度问题

（华南农业大学数学与信息学院，广东广州 510642）

出版日期:2015-10-31 发布日期:2016-03-24
作者简介:陈建国（1963-），男，湖南省人，教授，博士，主要研究方向为企业IE优化与信息化.
基金资助:
广东省教育部产学研结合资助项目（2011 B090400160）

A Research on Job-Shop Scheduling in Stochastic Rework and Reprocessing Situation

(College of Mathematic and Information, South China Agricultural University, Guangzhou 510642, China)

Online:2015-10-31 Published:2016-03-24

摘要/Abstract

摘要： 针对传统Job-Shop数学模型忽略返工及重加工的因素，构建了考虑该情形下的Job-Shop调度数学模型及相应的求解算法。该模型详细分析了返工及重加工的流程，对问题的定义做了进一步推导，模型以总加权拖期最小为目标，并提出一种改进的遗传算法对该模型进行求解。针对该调度情形，对算法中染色体的编码、种群初始化进行改进。种群数据的仿真实验表明，与传统遗传算法相比，改进后的算法在收敛速度、求出的最小总加权拖期方面均优于前者。最后通过对10×10实例调度方案求解及仿真，并与作业车间实际调度结果比较，模型仿真所得总加权拖期小于实际计划调度结果的46%，本模型得出的调度方案是实用且有效的。

关键词: Job-Shop调度, 返工及重加工, 总加权拖期, 改进遗传算法

Abstract: A Job-Shop scheduling is addressed with the consideration of stochastic rework and reprocessing while the traditional Job-Shop mathematical model ignored it. The objective of the model is to minimize the Total Weighted Tardiness (TWT) in these job shops. To solve the problem, a modified genetic algorithm is proposed with coding and population initialization improved. Five groups of population data for simulation experiments show that compared with the traditional genetic algorithm, the improved algorithm is better in convergence speed and the target value of TWT. Finally, through simulating the instances of scheduling scheme, and comparing with the actual Job-Shop scheduling results, the TWT of model simulation is less than 46% of the actual project scheduling results, and the scheduling scheme model proves practical and effective.

Key words: Job-Shop scheduling, rework and reprocessing, total weighted tardiness, modified genetic algorithm

陈建国, 舒辉, 余平祥. 随机返工及重加工情形下的Job-Shop调度问题[J]. 工业工程, 2015, 18(5): 127-133.

Chen Jian-guo, Shu Hui, Yu Ping-xiang. A Research on Job-Shop Scheduling in Stochastic Rework and Reprocessing Situation[J]. Industrial Engineering Journal , 2015, 18(5): 127-133.

参考文献

［1］W-Zhiming, Z-Chunwei. Genetic algorithm approach to job shop scheduling and its use in real-time cases［J］. International Journal of Computer Integrated Manufacturing,2000, 13(5): 422-429. ［2］Eskandari H, Hosseinzadeh A. A variable neighbourhood search for hybrid flow-shop scheduling problem with rework and setup times［J］. Journal of The Operational Research Society, 2014, 65(8): 1221-1231. ［3］Ko H, Kim J, Kim S, et al. Dispatching rule for non-identical parallel machines with sequence-dependent setups and quality restrictions［J］. Computers & Industrial Engineering,2010, 59(3): 448-457. ［4］Biswas P, Sarker B R. Optimal batch quantity models for a lean production system with incycle rework and scrap［J］. International Journal of Production Research, 2008, 46(23): 6585-6610. ［5］Inderfurth K, Kovalyov M Y, Ng C T, et al. Cost minimizing scheduling of work and rework processes on a single facility under deterioration of reworkables［J］. International Journal of Production Economics, 2007, 105(2): 345-356. ［6］许鹏，王焱. 车间动态调度方法研究与应用［J］. 航空制造技术, 2009(21): 82-87. Xu Peng,Wang Yan. Research and application of shop dynamic scheduling algorithm［J］. Aeronautical Manufacturing Techonlogy, 2009(21): 82-87. ［7］姜洋，孙伟，丁秋雷，等. 考虑行为主体的单机调度干扰管理模型［J］. 机械工程学报,2013,49(14): 191-198. Jiang Yang,Sun Wei,Ding Qiu-lei,et al. Model of disruption management with actors in single machine scheduling［J］.Journal of Mechanical Enginerring, 2013,49(14): 191-198. ［8］Hart E, Ross P. Real-World Applications of Evolutionary Computing［M］. Berlin: Springer Verlag,2000: 280-289. ［9］Lin T, Horng S, Kao T, et al. An efficient jobshop scheduling algorithm based on particle swarm optimization.［J］. Expert Systems with Applications, 2010,37(3): 2629-2636. ［10］Zhou R, Lee H P, Nee A Y C. Applying ant colony optimisation (ACO) algorithm to dynamic job shop scheduling problems［J］. International Journal of Manufacturing Research,2008,3(3): 301-320. ［11］Meeran S, Morshed M S. A hybrid genetic tabu search algorithm for solving job shop scheduling problems: a case study［J］. Journal of Intelligent Manufacturing, 2012,23(4): 1063-1078. ［12］Kolliopoulos S G, Steiner G. Approximation algorithms for minimizing the total weighted tardiness on a single machine［J］. Theoretical Computer Science, 2006, 355(3): 261-273. ［13］Tsai J, Liu T, Ho W, et al. An improved genetic algorithm for job-shop scheduling problems using Taguchibased crossover［J］. The International Journal of Advanced Manufacturing Technology, 2008, 38(9-10): 987-994. ［14］Zhou H, Cheung W, Leung L C. Minimizing weighted tardiness of job-shop scheduling using a hybrid genetic algorithm［J］. European Journal of Operational Research,2009, 194(3): 637-649.