具有工序顺序柔性的车间调度问题研究综述

doi:10.3969/j.issn.1007-7375.2020.02.015

摘要/Abstract

摘要： 某些加工车间在生产过程中具有多种柔性，工序顺序柔性就是其中重要的一种。通过对具有工序顺序柔性的车间调度问题的优化求解，能够极大地提高生产效率，节约生产成本。本文对具有工序顺序柔性的车间调度问题的研究现状进行整理分析，主要包括混合车间调度问题(mixed shop scheduling problem, MSP)、分组车间调度问题(group shop scheduling problem, GSP)和部分车间调度问题(partial shop scheduling problem, PSP)。最后，指出了具有工序顺序柔性的车间调度问题的发展前景及发展方向。

关键词: 车间调度, 工序顺序柔性, 研究综述

Abstract: There are various kinds of flexibility in some workshop in the production process, and the flexibility of the process sequence is one of the important ones. By solving the shop scheduling problem with flexible process sequence, the production efficiency can be greatly improved and the cost can be saved. The research status of the shop scheduling problem with flexible process sequence is analyzed, including mixed shop scheduling problem (MSP), group shop scheduling problem (GSP) and partial shop scheduling problem (PSP). Finally, the development prospects and direction of the shop scheduling problem with flexible process sequence are pointed out.

Key words: shop scheduling, flexible process sequence, research review

中图分类号:

TP301.6

桂林, 张春江, 李新宇. 具有工序顺序柔性的车间调度问题研究综述[J]. 工业工程, 2020, 23(2): 116-123.

GUI Lin, ZHANG Chunjiang, LI Xinyu. A Review of Research on Shop Scheduling Problem with Flexible Process Sequence[J]. Industrial Engineering Journal, 2020, 23(2): 116-123.

参考文献

[1] 王凌. 车间调度及其遗传算法[M]. 北京: 清华大学出版社, 2003.
[2] 王凌, 周刚, 许烨, 等. 混合流水线调度研究进展[J]. 化工自动化及仪表, 2011, 38(1): 1-8
WANG Ling, ZHOU Gang, XU Ye, et al. Advances in the study on hybrid flow-shop scheduling[J]. Control and Instruments in Chemical Industry, 2011, 38(1): 1-8
[3] 高亮, 李新宇. 工艺规划与车间调度集成研究现状及进展[J]. 中国机械工程, 2011, 22(8): 1001-1007
GAO Liang, LI Xinyu. Current researches on integrated process planning and scheduling[J]. China Mechanical Engineering, 2011, 22(8): 1001-1007
[4] MASUDA T, ISHII H, NISHIDA T. The mixed shop scheduling problem[J]. Discrete Applied Mathematics, 1985, 11(2): 175-186
[5] ISHII H, MASUDA T, NISHIDA T. Two machine mixed shop scheduling problem with controllable machine speeds[J]. Discrete applied mathematics, 1987, 17(1-2): 29-38
[6] SHAKHLEVICH N V, SOTSKOV Y N, WERNER F. Shop scheduling problems with fixed and non-fixed machine orders of the jobs[J]. Annals of Operations Research, 1999, 92(1): 281-304
[7] SHAKHLEVICH N V, SOTSKOV Y N, WERNER F. Complexity of mixed shop scheduling problems: a survey[J]. European Journal of Operational Research, 2000, 120(2): 343-351
[8] CHENG T C E, KOVALYOV M Y. An exact algorithm for batching and scheduling two part types in a mixed shop: a technical note[J]. International Journal of Production Economics, 1998, 55(1): 53-56
[9] KIS T. On the complexity of non-preemptive shop scheduling with two jobs[J]. Computing, 2002, 69(1): 37-49
[10] LIU Z, LI Y. Two-machine mixed shop problem with setup, processing and removal time separated[J]. OR Transactions, 2009, 13(4): 31-38
[11] ÇETINKAYA F C, DUMAN M. Lot streaming in a two-machine mixed shop[J]. International Journal of Advanced Manufacturing Technology, 2010, 49(9-12): 1161-1173
[12] KOULAMAS C, KYPARISIS G J. The three-machine proportionate open shop and mixed shop minimum makespan problems[J]. European Journal of Operational Research, 2015, 243(1): 70-74
[13] DUGARZHAPOV A, KONONOV A. A polynomial-time algorithm for the preemptive mixed-shop problem with two unit operations per job[J]. Journal of Scheduling, 2015, 19(1): 61-72
[14] LIU L, NI G, CHEN Y, et al. Approximation algorithms and a hardness result for the three-machine proportionate mixed shop[C]//International Conference on Algorithmic Applications in Management. Cham: Springer, 2018: 268-280.
[15] LIU L, CHEN Y, DONG J, et al. Approximation algorithms for the three-machine proportionate mixed shop scheduling[J]. Theoretical Computer Science, 2020, 803: 57-70
[16] SHAKHLEVICH N V, SOTSKOV Y N. Scheduling two jobs with fixed and nonfixed routes[J]. Computing, 1994, 52(1): 17-30
[17] FERRELL W, SALE J, SAMS J, et al. Evaluating simple scheduling rules in a mixed shop environment[J]. Computers & Industrial Engineering, 2000, 38(1): 39-66
[18] LIU S Q, ONG H L. Metaheuristics for the mixed shop scheduling problem[J]. Asia-Pacific Journal of Operational Research, 2012, 21(1): 97-115
[19] NGUYEN V, BAO H P. An efficient solution to the mixed shop scheduling problem using a modified genetic algorithm[J]. Procedia Computer Science, 2016, 95: 475-482
[20] FAN K, ZHAI Y, LI X, et al. Review and classification of hybrid shop scheduling[J]. Production Engineering, 2018, 12(5): 597-609
[21] LENSTRA J K, AARTS E. The information about the Whizzkids’ 97 Contest[DB/OL]. (1997-09-06) [2019-12-12]. http://www.win.tue.nl/whizzkids/1997.
[22] BLUM C, SAMPELS M. Ant colony optimization for FOP shop scheduling: a case study on different pheromone representations[C/OL]. (2002-08-07) [2019-12-12]. https//ieeexplore.ieee.org/document/1004474?arnumber=1004474.
[23] BLUM C. ACO applied to group shop scheduling: a case study on intensification and diversification[C]//International Workshop on Ant Algorithms. Berlin, Heidelberg: Springer, 2002: 14-27.
[24] BLUM C, SAMPELS M. An ant colony optimization algorithm for shop scheduling problems[J]. Journal of Mathematical Modelling and Algorithms, 2004, 3(3): 285-308
[25] SAMPELS M, BLUM C, MASTROLILLI M, et al. Metaheuristics for group shop scheduling[C]//International Conference on Parallel Problem Solving from Nature. Berlin, Heidelberg: Springer, 2002: 631-640.
[26] LIU S Q, ONG H L, NG K M. A fast tabu search algorithm for the group shop scheduling problem[J]. Advances in Engineering Software, 2005, 36(8): 533-539
[27] AHMADIZAR F, GHAZANFARI M, GHOMI S M T F. Application of chance-constrained programming for stochastic group shop scheduling problem[J]. The International Journal of Advanced Manufacturing Technology, 2009, 42(3-4): 321-334
[28] AHMADIZAR F, GHAZANFARI M, GHOMI S M T F. Group shops scheduling with makespan criterion subject to random release dates and processing times[J]. Computers & Operations Research, 2010, 37(1): 152-162
[29] AHMADIZAR F, RABANIMOTLAGH A. Group shop scheduling with uncertain data and a general cost objective[J]. The International Journal of Advanced Manufacturing Technology, 2014, 70(5-8): 1313-1322
[30] AHMADIZAR F, SHAHMALEKI P. Group-shop scheduling with sequence-dependent set-up and transportation times[J]. Applied Mathematical Modelling, 2014, 38(21-22): 5080-5091
[31] AHMADIZAR F, RABANIMOTLAGH A, ARKAT J. Stochastic group shop scheduling with fuzzy due dates[J]. Journal of Intelligent & Fuzzy Systems, 2017, 33(4): 2075-2084
[32] KEMMOE-TCHOMTE S, FENIES P, LAMY D, et al. A multi-start multi-level ELS for the group-shop scheduling problem[C]//MACCHI M, MONOSTORI L, PINTO R. 16th IFAC Symposium on Information Control Problems in Manufacturing INCOM. Bergamo, Italy: IFAC PapersOnline, 2018, 51 (11): 1299-1304
[33] STRUSEVICH V A. Shop scheduling problems under precedence constraints[J]. Annals of Operations Research, 1997, 69(0): 351-377
[34] STRUSEVICH V A, DROBOUCHEVITCH I G, SHAKHLEVICH N V. Three-machine shop scheduling with partially ordered processing routes[J]. Journal of the Operational Research Society, 2002, 53(5): 574-582
[35] KIS T. Job-shop scheduling with processing alternatives[J]. European Journal of Operational Research, 2003, 151(2): 307-332
[36] SU L H, CHOU F D, TING W C. Minimizing makespan in a two-stage system with flowshop and open shop[J]. Computers & Industrial Engineering, 2005, 49(4): 520-536
[37] NASIRI M M, KIANFAR F. A GA/TS algorithm for the stage shop scheduling problem[J]. Computers and Industrial Engineering, 2011, 61(1): 161-170
[38] DONG J, HU J, CHEN Y. Minimizing makespan in a two-stage hybrid flow shop scheduling problem with open shop in one stage[J]. Applied Mathematics-A Journal of Chinese Universities, 2013, 28(3): 358-368
[39] NASIRI, MAHDI M. A modified ABC algorithm for the stage shop scheduling problem[J]. Applied Soft Computing, 2015, 28: 81-89
[40] MAYER S, ENDISCH C. Adaptive production control in a modular assembly system based on partial look-ahead scheduling[C]. 2019 IEEE International Conference on Mechatronics (ICM). Ilmenau, Germany: Institute of Electrical and Electronics Engineers Inc., 2019, 1: 293-300.
[41] GAN P Y, LEE K S. Scheduling of flexible-sequenced process plans in a mould manufacturing shop[J]. International Journal of Advanced Manufacturing Technology, 2002, 20(3): 214-222
[42] BEACH R, MUHLEMANN A P, PRICE D H R, et al. A review of manufacturing flexibility[J]. European Journal of Operational Research, 2000, 122(1): 41-57
[43] DING L, YONG Y, AHMET K, et al. Global optimization of a feature-based process sequence using GA and ANN techniques[J]. International Journal of Production Research, 2005, 43(15): 3247-3272
[44] ADENSO-DÍAZ B, GARCÍA-CARBAJAL S, GUPTA S M. A path-relinking approach for a bi-criteria disassembly sequencing problem[J]. Computers & Operations Research, 2008, 35(12): 3989-3997
[45] NASIRI M M, KIANFAR F. A hybrid scatter search for the partial job shop scheduling problem[J]. International Journal of Advanced Manufacturing Technology, 2011, 52(9-12): 1031-1038
[46] GO T F, WAHAB D A, RAHMAN M N A, et al. Genetically optimised disassembly sequence for automotive component reuse[J]. Expert Systems with Applications, 2012, 39(5): 5409-5417
[47] ZHU X, HU S J, KOREN Y, et al. A complexity model for sequence planning in mixed-model assembly lines[J]. Journal of Manufacturing Systems, 2012, 31(2): 121-130
[48] 黄学文, 马雪丽, 曹德弼. 工序顺序柔性的作业车间调度问题的改进遗传算法求解[J]. 运筹与管理, 2013, 22(1): 65-71
HUANG Xuewen, MA Xueli, CAO Debi. Improved genetic algorithm for job shop scheduling problem with process sequence flexibility[J]. Operations Research and Management Science, 2013, 22(1): 65-71
[49] BENTAHA M L, BATTA A O, DOLGUI A, et al. Dealing with uncertainty in disassembly line design[J]. CIRP Annals-Manufacturing Technology, 2014, 63(1): 21-24
[50] QUIBELL R, STRUSEVICH V A. An approximation algorithm for the three-machine scheduling problem with the routes given by the same partial order[J]. Computers & Industrial Engineering, 2014, 76: 347-359
[51] 黄学文, 孙娜, 孙榕, 等. 工序顺序柔性描述模型研究[J]. 计算机集成制造系统, 2016, 22(10): 2275-2283
HUANG Xuewen, SUN Na, SUN Rong, et al. Operation sequence flexibility description model[J]. Computer Integrated Manufacturing Systems, 2016, 22(10): 2275-2283
[52] ZUBARAN T K, RITT M. An effective heuristic algorithm for the partial shop scheduling problem[J]. Computers & Operations Research, 2018, 93: 51-65