Product Comprehensive Scheduling Problems Solved by Genetic Algorithm Based on Operation Constraint Chain Coding

Abstract

Abstract: A genetic algorithm based on operation constraint chain coding was proposed to solve product comprehensive scheduling problems. The coding method designed in the algorithm might accurately reflect the operation constraint relations in product operation trees, and did not impose new constraints to ensure feasibility and completeness of initial solution spaces. At the same time, the problems of imposition constraints and omission of solution spaces were avoided in division coding methods. For the infeasible solution generated by crossover and mutation operations, a repair method was designed based on adjacency matrix. Experimental results verify effectiveness of the proposed algorithm.

Key words: operation constraint chain, product comprehensive scheduling, adjacency matrix, genetic algorithm

摘要： 针对产品综合调度优化问题，提出一种基于工序约束链编码的遗传算法。该算法设计的编码方法，不但能准确体现产品工艺树中的工序约束关系，而且不会强加新的约束，保证了初始解空间的可行性和完备性；同时避免了分区编码方法存在强加约束和遗漏解空间的问题。针对交叉、变异操作产生不可行解的问题，设计了一种基于邻接矩阵的修复方法。实验测试结果验证了所提算法的有效性。

关键词: 工序约束链, 产品综合调度问题, 邻接矩阵, 遗传算法

CLC Number:

TP301.6

SHI Fei;ZHAO Shikui. Product Comprehensive Scheduling Problems Solved by Genetic Algorithm Based on Operation Constraint Chain Coding[J]. China Mechanical Engineering.

石飞;赵诗奎. 基于工序约束链编码的遗传算法求解产品综合调度问题[J]. 中国机械工程.

References

[1]赵诗奎，方水良. 基于工序编码和邻域搜索策略的遗传算法优化作业车间调度[J]. 机械工程学报，2013，49(16)：160-169.
ZHAO Shikui，FANG Shuiliang. Operation-based Encoding and Neighborhood Search Genetic Algorithm for Job Shop Scheduling Optimization[J]. Journal of Mechanical Engineering，2013，49(16)：160-169.
[2]NOWICKI E，SMUTNICKI C. A Fast Taboo Search Algorithm for the Job Shop Problem[J]. Management Science，1996，42(6)：797-813.
[3]凌海峰，王西山.求解柔性作业车间调度问题的两阶段参数自适应蚁群算法[J].中国机械工程，2013，24(24)：3380-3385.
LING Haifeng，WANG Xishan. A Two-stage Parameter Adaptive Ant Colony Algorithm for Flexible Job Shop Scheduling Problem[J]. China Mechanical Engineering，2013，24(24)：3380-3385.
[4]ZHANG C Y，LI P G，RAO Y Q，et al. A Very Fast TS/SA Algorithm for the Job Shop Scheduling Problem[J]. Computers & Operations Research，2008，35(1)：282-294.
[5]YUAN Y，XU H. Flexible Job Shop Scheduling Using Hybrid Differential Evolution Algorithms[J]. Computers & Industrial Engineering，2013，65(2)：246-260.
[6]鲁建厦，邓伟，董巧英.基于混合粒子群算法具有交货期瓶颈的作业车间调度问题[J].中国机械工程，2014，25(5)：624-629.
LU Jiansha，DENG Wei，DONG Qiaoying. Job Shop Scheduling for Due-time Bottleneck Based on HPSO Algorithm[J]. China Mechanical Engineering，2014，25(5)：624-629.
[7]谢志强. 工件间有约束的复杂产品工序调度研究[D]. 哈尔滨：哈尔滨理工大学，2009.
XIE Zhiqiang. Study on Operation Scheduling of Complex Product with Constraint among Jobs[D]. Harbin：Harbin University of Science and Technology，2009.
[8]谢志强，杨静，杨光，等. 可动态生成具有优先级工序集的动态Job-Shop调度算法[J]. 计算机学报，2008，31(3)：502-508.
XIE Zhiqiang，YANG Jing，YANG Guang，et al. Dynamic Job-shop Scheduling Algorithm with Dynamic Set of Operation Having Priority[J]. Chinese Journal of Computers，2008，31(3)：502-508.
[9]谢志强，杨静，周勇，等. 基于工序集的动态关键路径多产品制造调度算法[J]. 计算机学报，2011，34(2)：406-412.
XIE Zhiqiang，YANG Jing，ZHOU Yong，et al. Dynamic Critical Paths Multi-product Manufacturing Scheduling Algorithm Based on Operation Set[J]. Chinese Journal of Computers，2011，34(2)：406-412.
[10]谢志强，张伟涛，杨静. 前移存在调整时间综合调度工序的算法[J]. 机械工程学报，2012，48(12)：169-177.
XIE Zhiqiang，ZHANG Weitao，YANG Jing. Algorithm of Moving Integrated Scheduling Procedures with Set-up Time Forward[J]. Journal of Mechanical Engineering，2012，48(12)：169-177.
[11]赵诗奎，韩青，王桂从. 基于虚拟零部件级别分区编码的产品综合调度算法[J].计算机集成制造系统，2015，21(9)：2435-2445.
ZHAO Shikui，HAN Qing，WANG Guicong. Product Comprehensive Scheduling Algorithm Based on Virtual Component Level Division Coding[J]. Computer Integrated Manufacturing Systems，2015，21(9)：2435-2445.
[12]谢志强，刘长海，杨静. 考虑后续工序且批处理工序数为2的批综合调度算法[J]. 上海交通大学学报，2012，46(11)：1746-1752，1758.
XIE Zhiqiang，LIU Changhai，YANG Jing. Batch Integrated Scheduling Algorithm Considering Posterior Operations and with Constraint of 2 Operations Batches Processing[J]. Journal of Shanghai Jiaotong University， 2012，46(11)：1746-1752，1758.
[13]YU W C，HOOGEVEEN H，LENSTRA J K. Minimizing Make-span in a Two-machine Flow Shop with Delays and Unit-time Operations is NP-Hard[J]. Journal of Scheduling，2004，7(5)：333-348.
[14]HOU E S H，ANSARI N，REN H. A Genetic Algorithm for Multiprocessor Scheduling[J]. IEEE Transactions on Parallel and Distributed Systems，1994，5(2)：113-120.
[15]张超勇，饶运清，刘向军，等. 基于POX交叉的遗传算法求解Job-Shop调度问题[J]. 中国机械工程，2004，15(23)：2149-2153.
ZHANG Chaoyong，RAO Yunqing，LIU Xiangjun，et al. An Improved Genetic Algorithm for the Job Shop Scheduling Problem[J]. China Mechanical Engineering，2004，15(23)：2149-2153.
[16]张超勇，董星，王晓娟，等. 基于改进非支配排序遗传算法的多目标柔性作业车间调度[J]. 机械工程学报，2010，46(11)：156-164.
ZHANG Chaoyong，DONG Xing，WANG Xiaojuan，et al. Improved NSGA-II for the Multi-objective Flexible Job-shop Scheduling Problem[J]. Journal of Mechanical Engineering，2010，46(11)：156-164.
[17]赵国凯. 基于装配约束的机械产品生产调度算法研究[D]. 大连：大连理工大学，2009.
ZHAO Guokai.Research on Production Seheduling Algorithm for Mechanical Products Based on Assembly Constraints[D]. Dalian：Dalian University of Technology，2009.