钢铁企业炉机匹配问题的研究
|
摘要
排序问题,即在一定条件下,寻找给定工件在一台或多台机器上安排加工的时间表,使其满足一定需要。本文以钢铁企业生产中的炉机匹配问题为背景,研究了一类特殊的柔性流水作业排序问题:工件需要在炼钢炉和铸机上顺序加工,在加工过程中工件不允许等待,并且在第二个阶段,铸机的生产不能中断。
本文首先证明了2台炼钢炉以上的炉机匹配可行解判定问题为强NP-hard,然后根据实际背景对工件的加工时间做了进一步限制,在证明目标函数为最大完工时间的情况下问题复杂性为NP-hard后,给出了启发式算法BMLPT,对该算法进行了界估计,并通过模拟计算与已有算法MLPT进行比较。
Scheduling is a form of decision making to find a schedule for a set of jobs on some machines under certain conditions. This paper considers a two-stage flexible flow shop scheduling problem arisen from steel and iron production, where no wait between two sequential operations of a job is allowed and there is no idle time between two consecutive processed jobs on machines of the second stage.
In this paper, firstly we prove that verifying the existence of a feasible scheduling is strong NP-hard for more than two machines in the first stage. Based on some further restrictions on the processing time according to the actual background, we show its complexity and present a heuristic algorithm BMLPT with asymptotically error bounds. Furthermore, BMLPT and MLPT are compared by computer simulation.
本文首先证明了2台炼钢炉以上的炉机匹配可行解判定问题为强NP-hard,然后根据实际背景对工件的加工时间做了进一步限制,在证明目标函数为最大完工时间的情况下问题复杂性为NP-hard后,给出了启发式算法BMLPT,对该算法进行了界估计,并通过模拟计算与已有算法MLPT进行比较。
Scheduling is a form of decision making to find a schedule for a set of jobs on some machines under certain conditions. This paper considers a two-stage flexible flow shop scheduling problem arisen from steel and iron production, where no wait between two sequential operations of a job is allowed and there is no idle time between two consecutive processed jobs on machines of the second stage.
In this paper, firstly we prove that verifying the existence of a feasible scheduling is strong NP-hard for more than two machines in the first stage. Based on some further restrictions on the processing time according to the actual background, we show its complexity and present a heuristic algorithm BMLPT with asymptotically error bounds. Furthermore, BMLPT and MLPT are compared by computer simulation.
引文
[1] Z. Wang, W. Xing and F. Bai. No-wait flexible flowshop scheduling with no-idle machines. Operations Research Letters. 2005, 33:609-614
[2] K. Giaro. NP-hardness of compact scheduling in simplified open and flow shops. European Journal of Operational Research. 2001, 130:90-98
[3] P.C. Gilmore and R.E. Gomory. Sequencing a one state variable machine: A solvable case of the traveling salesman problem. Operations Research. 1964, 12:655–679
[4] I. Adiri and D. Pohoryles. Flow-shop/no-idle or no-wait scheduling to minimise the sum of completion times. Naval Research Logistics Quarterly. 1982, 29: 495–504
[5] S.M. Johnson. Optimal two- and three-stage production schedules with setup times included. Naval Research Logistics Quarterly. 1954, 1: 61–68
[6] H. R?ck. The three machine no-wait flowshop problem is NP-complete. Journal of the Association for Computing Machinery. 1984, 31:336–345
[7] P. Baptiste, K.H. Lee. A branch and bound algorithm for the Fno-idleCmax, in: International Conference on Industrial Engineering and Production Management (IEPM’97), Lyon. 1997
[8] J. Grabowski and J. Pempera. Some local search algorithms for no-wait flow-shop problem with makespan criterion. Computers and Operations Research. 2005, 32: 2197–2212
[9] H. Saadani, A. Guinet and M. Moalla. Three stage no-idle flow-shops. Computers and Industrial Engineering. 2003, 44: 425–434
[10] T.S. Arthanari and K.G. Ramamurthy. An extension of two machines sequencing problem. Opsearch. 1971, 8:10– 22
[11] M.S. Salvador. A solution to a special case of flow shop scheduling problems, in Symposium of the Theory of Scheduling and Applications, S.E. Elmaghraby (ed.). Springer, New York. 1973
[12] M.R. Garey and D.S. Johnson. Computers and Intractability: A Guide to the Theory of NP-Completeness. Freeman, San Francisco. 1979
[13] M. Pinedo. Scheduling: Theory, Algorithms, and Systems. Springer, New York. 1995
[14] S.A. Brah and J.L. Hunsucker. Branch and bound algorithm for the flow shop with multiple processors. European Journal of Operational Research. 1991, 51: 88– 99
[15] M.C. Portmann. A. Vignier, D. Dardihac and D. Dezalay. Branch and bound crossed with GA to solve hybrid flowshops. European Journal of Operational Research. 1998, 107(2) :389– 400
[16] E. Néron, P. Baptiste and J.N.D. Gupta. Solving hybrid flow shop problem using energetic reasoning and global operations. Omega. 2001, 29 (6): 501– 511
[17] C. Rajendran and D. Chaudhuri. A multi-stage parallel-processor flowshop problem with minimum flowtime. European Journal of Operational Research. 1992, 57:111– 122
[18] C. Rajendran and D. Chaudhuri. Scheduling in n-job, m-stage flowshop with parallel processors to minimize makespan. International Journal of Production Economics. 1992, 27: 137– 143
[19] J.N.D. Gupta and E.A. Tunc. Scheduling a two-stage hybrid flowshop with separable setup and removal times. European Journal of Operational Research. 1994, 77: 415– 428
[20] J.N.D. Gupta, K. Krüger, V. Lauff, F. Werner and Y.N. Sotskov. Heuristics for hybrid flow shops with controllable processing times and assignable due dates. Computers and Operations Research. 2002, 29 (10): 1417– 1439
[21] F.Y. Ding and D. Kittichartphayak. Heuristics for scheduling flexible flow lines. Computers and Industrial Engineering. 1994, 26: 27–34
[22] S.C. Chang and D.Y. Liao. Scheduling flexible flow shops with no setup effects. IEEE Transactions on Robotics and Automation. 1994, 10 (2): 112– 122
[23] C.Y. Liu and S.C. Chang. Scheduling flexible flow shops with sequence-dependent setup effects. IEEE Transactions on Robotics and Automation. 2000, 16 (4):408– 419
[24] H. Allaoui and A. Artiba. Scheduling two-stage hybrid flow shop with availability constraints. Computers and Operations Research. 2006, 33(5):1399-1419
[25] E. Nowicki and C. Smutnicki. The flow shop with parallel machines: a tabu search approach. European Journal of Operational Research. 1998, 106 (2–3):226– 253
[26] L. Wang and D. Li . A scheduling algorithm for flexible flow shop problem, Proceedings of the 4th World Congress on Intelligent Control and Automation. New York: IEEE. 2002, 4: 3106– 3108
[27] H. Wang, V. Jacob and E. Rolland. Design of efficient hybrid neural networks for flexible flow shop scheduling. Expert Systems. 2003, 20 (4):208– 231
[28] J. Xie, W. Xing, Z. Liu and J. Dong. Minimum Deviation Algorithm for Two-Stage No-Wait Flowshops with Parallel Machines. Computers and Mathematics with Applications. 2004, 47:1857-1863
[29]顾飞,李建国,刘哲.武钢二炼钢厂炉机匹配系统算法研究.冶金自动化. 2005, 6:15-19
[30] R.L. Graham. Bounds on Multiprocessing Timing Anomalies. SIAM J. Appl. Math. 1969, 17: 416–429
[31] R.M. Karp. Reducibility among combinatorial problems, in:R.E. Miller, J.W. Thather (Eds.), Complexity of Computer Computations. Plenum, New York. 1972
[2] K. Giaro. NP-hardness of compact scheduling in simplified open and flow shops. European Journal of Operational Research. 2001, 130:90-98
[3] P.C. Gilmore and R.E. Gomory. Sequencing a one state variable machine: A solvable case of the traveling salesman problem. Operations Research. 1964, 12:655–679
[4] I. Adiri and D. Pohoryles. Flow-shop/no-idle or no-wait scheduling to minimise the sum of completion times. Naval Research Logistics Quarterly. 1982, 29: 495–504
[5] S.M. Johnson. Optimal two- and three-stage production schedules with setup times included. Naval Research Logistics Quarterly. 1954, 1: 61–68
[6] H. R?ck. The three machine no-wait flowshop problem is NP-complete. Journal of the Association for Computing Machinery. 1984, 31:336–345
[7] P. Baptiste, K.H. Lee. A branch and bound algorithm for the Fno-idleCmax, in: International Conference on Industrial Engineering and Production Management (IEPM’97), Lyon. 1997
[8] J. Grabowski and J. Pempera. Some local search algorithms for no-wait flow-shop problem with makespan criterion. Computers and Operations Research. 2005, 32: 2197–2212
[9] H. Saadani, A. Guinet and M. Moalla. Three stage no-idle flow-shops. Computers and Industrial Engineering. 2003, 44: 425–434
[10] T.S. Arthanari and K.G. Ramamurthy. An extension of two machines sequencing problem. Opsearch. 1971, 8:10– 22
[11] M.S. Salvador. A solution to a special case of flow shop scheduling problems, in Symposium of the Theory of Scheduling and Applications, S.E. Elmaghraby (ed.). Springer, New York. 1973
[12] M.R. Garey and D.S. Johnson. Computers and Intractability: A Guide to the Theory of NP-Completeness. Freeman, San Francisco. 1979
[13] M. Pinedo. Scheduling: Theory, Algorithms, and Systems. Springer, New York. 1995
[14] S.A. Brah and J.L. Hunsucker. Branch and bound algorithm for the flow shop with multiple processors. European Journal of Operational Research. 1991, 51: 88– 99
[15] M.C. Portmann. A. Vignier, D. Dardihac and D. Dezalay. Branch and bound crossed with GA to solve hybrid flowshops. European Journal of Operational Research. 1998, 107(2) :389– 400
[16] E. Néron, P. Baptiste and J.N.D. Gupta. Solving hybrid flow shop problem using energetic reasoning and global operations. Omega. 2001, 29 (6): 501– 511
[17] C. Rajendran and D. Chaudhuri. A multi-stage parallel-processor flowshop problem with minimum flowtime. European Journal of Operational Research. 1992, 57:111– 122
[18] C. Rajendran and D. Chaudhuri. Scheduling in n-job, m-stage flowshop with parallel processors to minimize makespan. International Journal of Production Economics. 1992, 27: 137– 143
[19] J.N.D. Gupta and E.A. Tunc. Scheduling a two-stage hybrid flowshop with separable setup and removal times. European Journal of Operational Research. 1994, 77: 415– 428
[20] J.N.D. Gupta, K. Krüger, V. Lauff, F. Werner and Y.N. Sotskov. Heuristics for hybrid flow shops with controllable processing times and assignable due dates. Computers and Operations Research. 2002, 29 (10): 1417– 1439
[21] F.Y. Ding and D. Kittichartphayak. Heuristics for scheduling flexible flow lines. Computers and Industrial Engineering. 1994, 26: 27–34
[22] S.C. Chang and D.Y. Liao. Scheduling flexible flow shops with no setup effects. IEEE Transactions on Robotics and Automation. 1994, 10 (2): 112– 122
[23] C.Y. Liu and S.C. Chang. Scheduling flexible flow shops with sequence-dependent setup effects. IEEE Transactions on Robotics and Automation. 2000, 16 (4):408– 419
[24] H. Allaoui and A. Artiba. Scheduling two-stage hybrid flow shop with availability constraints. Computers and Operations Research. 2006, 33(5):1399-1419
[25] E. Nowicki and C. Smutnicki. The flow shop with parallel machines: a tabu search approach. European Journal of Operational Research. 1998, 106 (2–3):226– 253
[26] L. Wang and D. Li . A scheduling algorithm for flexible flow shop problem, Proceedings of the 4th World Congress on Intelligent Control and Automation. New York: IEEE. 2002, 4: 3106– 3108
[27] H. Wang, V. Jacob and E. Rolland. Design of efficient hybrid neural networks for flexible flow shop scheduling. Expert Systems. 2003, 20 (4):208– 231
[28] J. Xie, W. Xing, Z. Liu and J. Dong. Minimum Deviation Algorithm for Two-Stage No-Wait Flowshops with Parallel Machines. Computers and Mathematics with Applications. 2004, 47:1857-1863
[29]顾飞,李建国,刘哲.武钢二炼钢厂炉机匹配系统算法研究.冶金自动化. 2005, 6:15-19
[30] R.L. Graham. Bounds on Multiprocessing Timing Anomalies. SIAM J. Appl. Math. 1969, 17: 416–429
[31] R.M. Karp. Reducibility among combinatorial problems, in:R.E. Miller, J.W. Thather (Eds.), Complexity of Computer Computations. Plenum, New York. 1972