Problems and Solutions of Flexible Job-shop Scheduling with Operation Lot-splitting

Abstract

Abstract: Considering that each operation in flexible job-shop scheduling with lot-splitting had its own appropriate lot-size, the concept of scheduling with lot-splitting was proposed based on operations, and a scheduling model with lot-splitting was established based on critical path operations. This model could dynamically update machinable sub-lot set, update available machines, determine optimal processing routes and appropriate operation lot-sizes thus makespan might be optimized and total lot quantity might be reduced. The experimental results show that, compared with lot-splitting based on workpieces, using the established scheduling model the makespan may be optimized, machine utilization may be improved, total machined lot quantity may be reduced (42%) and scheduling management complexity may be decreased.

Key words: flexible job shop, scheduling model with lot-splitting, operation lot-splitting, non-equal size lot-splitting

摘要： 考虑到柔性作业车间分批调度中不同工序具有各自合适批量大小，提出了基于工序分批调度的概念，建立了以关键路径工序为中心的分批调度模型。该模型动态更新可加工工序子批集，同时更新可选加工机器，及时调整加工路线，为不同工序安排大小合适的批量，以达到优化完工时间、有效降低总加工批次的目的。实验结果表明，相比基于工件分批的调度，该模型在优化最长完工时间、提高机器利用率的同时，大幅减少了总加工批次数量(42%)，降低了车间调度管理的复杂度。

关键词: 柔性作业车间, 分批调度模型, 工序分批, 不等量分批

CLC Number:

TP391.7

Xu Benzhu, Ji Jing, Fei Xiaolu. Problems and Solutions of Flexible Job-shop Scheduling with Operation Lot-splitting[J]. China Mechanical Engineering.

徐本柱, 吉靖, 费晓璐. 柔性作业车间中基于工序分批的调度问题与求解[J]. 中国机械工程.

References

[1]王万良, 吴启迪, 宋毅. 求解作业车间调度问题的自然改进自适应遗传算法 [J]. 系统工程理论与实践, 2004, 2(2):58-62.

Wang Wanliang, Wu Qidi, Song Yi. Modified Adaptive Genetic Algorithms for Solving Job-shop Scheduling Problems [J]. Systems Engineering—Theory & Practice, 2004, 24(2):58-62.

[2]Huang R H. Multi-objective Job-shop Scheduling with Lot Splitting Production [J]. International Journal of Production Economics, 2010, 124(1):206-213.

[3]刘晓平, 徐本柱, 彭军, 等. 工件工序可并行的作业车间调度模型与求解 [J]. 计算机辅助设计与图形学学报, 2012, 24(1):120-127.

Liu Xiaoping, Xu Benzhu, Peng Jun, et al. Model and Solution of Job-shop Scheduling for Parallel Processes [J]. Journal of Computer-Aided Design & Computer Graphics, 2012, 24(1):120-127.

[4]王海燕. 基于混合差分进化算法的制造过程分批优化调度研究[D]. 杭州:浙江工业大学, 2011.

[5]宋代力, 张洁. 蚁群算法求解混合流水车间分批调度问题 [J]. 计算机集成制造系统, 2013,19(7):1640-1647.

Song Daili, Zhang Jie. Batch Scheduling Problem of Hybrid Flow Shop Based on Ant Colony Algorithm [J]. Computer Integrated Manufacturing Systems, 2013,19(7):1640-1647.

[6]陆汉东, 何卫平, 周旭, 等. 基于禁忌搜索的柔性作业车间分批调度 [J]. 上海交通大学学报, 2012, 46(12):2003-2008.

Lu Handong, He Weiping, Zhou Xu, et al. An Integrated Tabu Search Algorithm for the Lot Streaming Problem in Flexible Job Shops [J]. Journal of Shanghai Jiaotong University, 2012, 46(12):2003-2008.

[7]Low C Y, Hsu C M, Huang K I. Benefits of Lot-splitting in Job-shop Scheduling [J]. International Journal of Advanced Manufacturing Technology, 2004, 24(9/10):773-780.

[8]潘多科, 朱剑英. 多工艺路线的批量生产调度优化[J]. 机械工程学报, 2004, 40(4):36-39.

Pan Duoke, Zhu Jianying. Optimization Method for a Job-shop Scheduling Problem with Alternative Machines in the Batch Process [J]. Chinese Journal of Mechanical Engineering, 2004, 40(4):36-39. [9]Jeong H I, Park J W, Leachman R C. A Batch Splitting Method for a Job Shop Scheduling Problem in an MRP Environment [J]. International Journal of Production Research, 1999, 37(15):3583-3598.

[10]孙志峻, 安进, 黄卫清. 作业车间多工艺路线批量作业计划优化[J].中国机械工程, 2008, 19(2):183-187.

Sun Zhijun, An Jin, Huang Weiqing. Lot Scheduling with Multiple Process Routes in Job Shop[J]. China Mechanical Engineering, 2008, 19(2):183-187.

[11]Chan L Y. The Application of Genetic Algorithms to Lot Streaming in a Job Scheduling Problem [J]. International Journal of Production Research, 2009, 47(12):3387-3412.

[12]陈伟达，达庆利. 工艺路线可变车间作业调度的两级遗传算发[J].系统工程学报，2002,17(2):161-166.

Chen Weida, Da Qingli. Job-shop Scheduling with Alterable Craft Based on Bilevel Genetic Algorithms[J]. Journal of Systems Engineering, 2002, 17(2):161-166.

[13]陶俐言, 聂倩, 王志峰, 等. 面向变批量生产的制造单元构建方法[J]. 计算机集成制造系统, 2014, 30(10):2411-2418.

Tao Liyan, Nie Qian, Wang Zhifeng, et al. Formation Technology of Manufacturing Cell Design for Scalable Batch Production[J]. Computer Integrated Manufacturing Systems, 2014, 30(10):2411-2418.

[14]陈亚绒, 周余庆, 周宏明, 等. 两阶段求解的可重构虚拟制造单元构建方法[J]. 中国机械工程, 2013, 24(22):3024-3029.

Chen Yarong, Zhou Yuqing, Zhou Hongming, et al. Virtual Manufacturing Cell Formation Method for Reconfigurable Manufacturing Based on Two-stage Solving [J]. China Mechanical Engineering, 2013, 24(22):3024-3029.

[15]Xie Z, Hao S, Ye G, et al. A New Algorithm for Complex Product Flexible Scheduling with Constraint between Jobs[J]. Computers & Industrial Engineering, 2009, 57(3):766-772.

[16]谢志强, 杨静, 杨光, 等. 可动态生成具有优先级工序集的动态Job-Shop调度算法 [J]. 计算机学报, 2008, 31(3):502-507.

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-507.

[17]谢志强, 辛宇, 杨静. 基于设备空闲事件驱动的综合调度算法[J]. 机械工程学报, 2011, 47(11):139-147.

Xie Zhiqiang, Xin Yu, Yang Jing. Integrated Scheduling Algorithm Based on Event-driven by Machines Idle [J]. Journal of Mechanical Engineering, 2011, 47(11):139-147.

[18]周驰, 高亮, 高海兵. 基于PSO 的置换流水车间调度算法[J]. 电子学报, 2006, 34(11):2008-2011.

Zhou Chi, Gao Liang, Gao Haibing. Particle Swarm Optimization Based Algorithm for Permutation Flow Shop Scheduling [J]. Acta Electronica Sinica, 2006, 34(11):2008-2011.

[19]苏子林. 车间调度问题及其进化算法分析[J].机械工程学报, 2008, 44(8):242-247.

Su Zilin. Job-shop Scheduling Problem and Its Evolution Algorithm Analysis [J]. Chinese Journal of Mechanical Engineering, 2008, 44(8):242-247.