基于三阶段解码机制的作业车间JIT调度算法研究

工业工程 ›› 2015, Vol. 18 ›› Issue (3): 98-104.

基于三阶段解码机制的作业车间JIT调度算法研究

（西安理工大学 1.机械与精密仪器工程学院; 2.高等技术学院，陕西西安 710082）

出版日期:2015-06-30 发布日期:2015-10-15
作者简介:王荪馨（1974-）,陕西省人，副教授，博士研究生，主要研究方向为先进制造技术、智能优化调度方法.
基金资助:
国家自然科学基金资助项目(51175420)

A Three-stage Decoding Method for Just-In-Time Job-Shop Scheduling

(1.School of Mechanical and Precision Instrument Engineering, Xi'an University of Technology, Xi'an 710082, China; 2. School of Technology, Xi'an University of Technology, Xi'an 710082, China)

Online:2015-06-30 Published:2015-10-15

摘要/Abstract

摘要： 零部件加工过程的精细化管控是保证大型复杂装备制造企业高效、均衡和低成本运营的重要手段。针对现有JIT调度方法普遍采用两阶段求解策略导致调度算法计算效率较低的问题，本文提出一种单阶段的改进型遗传算法解决思路：针对每一迭代优化过程中的染色体，设计了一种包含半主动解码、拖期工件贪婪插入、提前工件贪婪插入的三阶段渐进式解码机制，以引导待调度工序集尽可能在各自的交货时间点准时完工。这种三阶段解码方法具有与非正规调度指标吻合、解码机制简单和解码速度快等独特优势，最后采用72个JIT调度标准算例验证了该方法在优化性能、计算效率等方面的有效性。

关键词: 作业车间, JIT调度, 提前/拖期, 遗传算法, 三阶段解码机制

Abstract: Some parts of large and complex products are very complicated in manufacturing since they have many operations to go through and are time-consuming. The just-in-time (JIT) scheduling is suitable to lean control these manufacturing process. In order to cope with the time consuming problem, the two-tage strategies were employed to solve JIT scheduling problem in most researches. A novel genetic algorithm (GA) with three-stage decoding mechanism is introduced in this research. In each iteration process of GA, the chromosomes, which are represented by an operationbased scheme, are decoded successively by three stages. Firstly, the semi-active decoding method is induced to explore the more search space of solutions. Secondly, the greedy insertion for tardy operations is executed to swap the tardy operations left to the machine idle time to reduce the tardiness costs of solution. Thirdly, the greedy insertion for early operations is proposed to swap the early operations rightly to the suitable machine idle time to cut the more earliness costs. The experimental results finally demonstrate the effectiveness and efficiency of our algorithm over a wide range of benchmarks.

Key words: job-shop, jit scheduling, earliness/tardiness, genetic algorithm, three-stage decoding

王荪馨1,2，李言1，淮文博2. 基于三阶段解码机制的作业车间JIT调度算法研究[J]. 工业工程, 2015, 18(3): 98-104.

Wang Sun-xin1,2, Li Yan1, Huai Wen-bo2. A Three-stage Decoding Method for Just-In-Time Job-Shop Scheduling[J]. Industrial Engineering Journal , 2015, 18(3): 98-104.

参考文献

［1］Baptiste P, Flamini M, Sourd F. Lagrangian bounds for justintime jobshop scheduling［J］. Computers & Operations Research, 2008, 35: 906-915. ［2］Monette J N , Devill Y , Hentenryck P. JustInTime scheduling with constraint programming［C］. Proceedings of the Nineteenth International Conference on Automated Planning and Scheduling, 2009, 241-248. ［3］Araujo R P, Santos A G, Arroyo J. A combination of evolutionary algorithm, mathematical programming, and a new local search procedure for the JustInTime Job-Shop scheduling problem［J］. Learning and Intelligent Optimization, 2010, 6073: 10-24. ［4］王荪馨，李言，关雄飞，呼刚义，一种求解作业车间JIT调度问题的混合TS/MP算法［J］，机械科学与技术, 2013.32(03):372-376. Wang Sun-xin, Li Yan, Guan Xiong-fei, Hu Gang-yi.A hybrid algorithm based on tabu search and mathematical programming for Just-In-Time Job-Shop scheduling problem［J］. Mechanical Science and Technology for Aerospace Engineering, 2013.32(03):372-376. ［5］张超勇,管在林,刘琼,等.一种新调度类型及其在作业车间调度问题中的应用［J］.机械工程学报, 2008,44(10):24-31. Zhang Chao-yong, Guan Zai-lin,Liu Qiong,et al. New scheduling type applied to solving Jobshop scheduling problem［J］. Chinese Journal of Mechanical Engineering, 2008,44(10):24-31. ［6］Shi G Y, Iima H , Sannomiya N. A new encoding scheme for job shop problems by genetic algorithm［C］. The 35th Conference on Decision and Control, Kobe , 1996. ［7］张超勇，饶运清，李培根，等.基于POX交叉的遗传算法求解JobShop调度问题［J］.中国机械工程，2004,15(23):2149-2153. Zhang Chao-yong, Rao Yun-qing, Li Peigen,et al. An improved genetic algorithm for job shop scheduling problem［J］. China Mechanical Engineering, 2004,15(23):2149-2153. ［8］Cheng R. A study on genetic algorithms-based optimal scheduling techniques［D］. Tokyo Institute of Technology, 1997.

[1]	张正敏, 管在林, 岳磊. 基于Lévy Flight的混合GA在柔性作业车间调度问题中的性能分析[J]. 工业工程, 2021, 24(4): 83-92.
[2]	王晓军, 王博, 晋民杰, 杨春霞, 白新利. 改进多种群遗传算法的AutoStore系统多AGV调度优化[J]. 工业工程, 2021, 24(4): 112-118,167.
[3]	王莹莹, 吴立云. 基于改进NSGA-II的多项目多技能人力资源调度研究[J]. 工业工程, 2021, 24(3): 130-138.
[4]	曾创锋, 刘建军, 陈庆新, 毛宁. 求解一类无关并行机调度的遗传迭代贪心算法[J]. 工业工程, 2021, 24(2): 110-118.
[5]	黄露, 纪延光. 考虑顾客延误损失的配送中心选址双层规划问题研究[J]. 工业工程, 2021, 24(2): 141-147.
[6]	王冰怡, 张锦. 考虑网点共享与变更的多级快递网点选址问题[J]. 工业工程, 2021, 24(2): 155-165.
[7]	马跃如, 文铮, 易丹. 考虑老年人满意度的多目标居家养老护理员路径优化[J]. 工业工程, 2021, 24(1): 74-81,103.
[8]	王玖河, 高辉, 刘欢. 基于遗传算法的共享助力车调度问题研究[J]. 工业工程, 2021, 24(1): 90-96.
[9]	吴斌, 宋琰, 程晶, 董敏. 基于密度峰值聚类的VRPTW问题研究[J]. 工业工程, 2020, 23(5): 58-66,74.
[10]	王苏林, 邱菲尔, 陈凡, 刘川昆, 鹿腾, 王芷芸. 基于贪心遗传的地下物流节点选择规划研究[J]. 工业工程, 2020, 23(5): 88-95.
[11]	侯艳, 黄康焕, 张亿仙, 伍乃骐. 原油一次加工过程的多目标调度优化[J]. 工业工程, 2020, 23(4): 131-139.
[12]	王泽, 杨信丰, 刘兰芬. 考虑电量消耗的车辆调度优化研究[J]. 工业工程, 2020, 23(4): 140-147.
[13]	曾垂飞, 刘建军, 陈庆新, 毛宁. 装配作业车间分批调度问题的算法对比[J]. 工业工程, 2020, 23(4): 174-182.
[14]	张巍, 李鹏翔, 仝自强, 岳毅蒙. 基于损坏车辆分布预测与损益阈值分析下的共享单车回收研究[J]. 工业工程, 2020, 23(3): 132-137.
[15]	张国辉, 胡一凡, 孙靖贺. 改进遗传算法求解多时间约束的柔性作业车间调度问题[J]. 工业工程, 2020, 23(2): 19-25,48.