Loading...
|
Please use this identifier to cite or link to this item:
https://nccur.lib.nccu.edu.tw/handle/140.119/35258
|
| Title: | 數個瓶頸為基礎的啟發式法則求解彈性流程系統排程問題
BOTTLENECK-BASED HEURISTICS FOR FLEXIBLE FLOW LINE SCHEDULING PROBLEMS WITH A BOTTLENECK STAGE |
| Authors: | 陳俊龍
Chen,Chun Lung |
| Contributors: | 陳春龍
Chen,Chuen Lung
陳俊龍
Chen,Chun Lung |
| Keywords: | 瓶頸
彈性流程系統
非等效平行機
派工法則
啟發式方法 |
| Date: | 2006 |
| Issue Date: | 2009-09-18 14:34:20 (UTC+8) |
| Abstract: | In this research, we study flexible flow line scheduling problems with unrelated parallel machines and with a bottleneck stage. The measures of performances are to minimize makespan, to minimize the number of tardy jobs, and to minimize total tardiness, considered respectively. Several bottleneck-based heuristics are developed to solve these scheduling problems. A bottleneck-driven multiple insertion heuristic (BDMIH) is proposed to solve problems with makespan as the objective. The essential idea of BDMIH is that we think the scheduling of jobs at the bottleneck stage may affect the performance of a heuristic for scheduling jobs in all stages. Therefore, in this heuristic we let jobs entering the sequence at the first stage be driven by their sequence entering at the bottleneck stage. Given an FFL problem with a bottleneck stage, this heuristic first identifies the bottleneck stage, then generates an initial sequence of jobs by a variant of Johnson’s rule (SPT-LPT rule), and finally applies a multiple insertion heuristic to find the best schedule. Another heuristic, a bottleneck-based due-date decision heuristic (BBDDDH), is developed to solve problems with the number of tardy jobs as the objective. The heuristic consists of three steps: (1) Identifying the bottleneck stage, (2) Scheduling jobs at the bottleneck stage and the upstream stages ahead of the bottleneck stage, and (3) Using dispatching rules to schedule jobs at the downstream stages behind the bottleneck stage. A new approach is developed to find the arrival times of the jobs at the bottleneck stage, and two decision rules are developed to schedule jobs at bottleneck stage. This new approach neatly overcomes the difficulty of determining feasible arrival times of jobs at bottleneck stage. The last bottleneck-based heuristic, a bottleneck-driven adaptable multiple insertion heuristic (BDAMIH), is constructed to solve problems with total tardiness as the objective. The main idea of BDAMIH is combined with the ideas of BDMIH and BBDDDH. The main difference between BDAMIH and BDMIH is that BDMIH generates an initial sequence of jobs before performing the insertion heuristic; however, BDAMIH is adaptable to select a job within the process of the insertion heuristic. To evaluate the performance of the proposed heuristics, several well-known dispatching rules and heuristics are investigated for comparison purposes and computational experiments are performed on randomly generated test problems. Computational results show that the proposed heuristics significantly outperform all well-known dispatching rules or heuristics. Also, an analysis of the experimental factors is performed, and several interesting insights of the proposed heuristics are discovered. |
| Reference: | Adler, L., Fraiman, N., Kobacker, E., Pinedo, M., Plotnicoff, J. C., and Wu, T. P., BPSS: A scheduling support system for the packaging industry. Operations Research. 1993, 41, 641–648.
Agnetis, A., Pacifici, A., Rossi, F., Lucertini, M., Nicoletti, S., Nicolo, F., Oriolo, G., Pacciarelli, D., and Pesaro, E., Scheduling of flexible flow shop in an automobile assembly plant. European Journal of Operational Research, 1997, 97, 348–362.
Alisantoso, D., Khoo, L. P. and Jiang, P. Y., An immune algorithm approach to the scheduling of a flexible PCB flow shop. International Journal of Advanced Manufacturing Technology, 2003, 22, 819–827.
Azizoglu, M., Cakmak, E. and Kondakci, S., A flexible flowshop problem with total flow time minimization. European Journal of Operational Research, 2001, 132, 528–538.
Baker, K. R. and Bertrand, J. W., A dynamic priority rule for scheduling against due-dates. Journal of Operations Management, 1982, 3, 37–42.
Baker, K. R. and Kanet, J. J., Job shop scheduling with modified due-dates. Journal of Operations Management, 1983, 4, 11–22.
Bertel, S. and Billaut, J. C., A genetic algorithm for an industrial multiprocessor flow shop scheduling problem with recirculation. European Journal of Operational Research, 2004, 159, 651–662.
Brah, S. A., A comparative analysis of due date based job sequencing rules in a flow shop with multiple processors. Production Planning and Control, 1996, 7, 362–373.
Brah, S. A. and Loo, L. L., Heuristics for scheduling in a flow shop with multiple processors. European Journal of Operational Research, 1999, 113, 113–122.
Brah, S. A. and Wheeler, G. E., Comparison of scheduling rules in a flow shop with multiple processors: A simulation, Simulation, 1998, 71, 302–311.
Campbell, H. G., Dudek, R. A. and Smith, M. L., A heuristic algorithm for the n-job, m-machine sequencing problem. Management Science, 1970, 16, 630–637.
Chen, C. L., Usher, J. M., and Palanimuthu, N., A tabu search based heuristic for a flexible flow line with minimum flow time criterion. International Journal of Industrial Engineering, 1998, 5, 157–168.
Chen, Y. C. and Lee, C. E., Bottleneck-based group scheduling in a flow line cell. International Journal of Industrial Engineering-Applications and Practice, 1998, 5, 288–300.
Choi, S. W., Kim, Y. D. and Lee, G. C., Minimizing total tardiness of orders with reentrant lots in a hybrid flowshop. International Journal of Production Research, 2005, 43, 2149–2167.
Conway, R., Comments on an exposition of multiple constraint scheduling. Production and Operations Management, 1997, 6, 23–24.
Dannenbring, D. G., An evaluation of flow shop sequencing heuristics. Management Science, 1977, 23, 1174–1182.
Du, J. and Leung, J. Y., Minimizing total tardiness on one machine is NP-hard. Mathematics of Operations Research, 1990, 15, 483–495.
Feaminan, J. M., Gupta, J. N. D. and Leisten, R., A review and classification of heuristics for permutation flow-shop scheduling with makespan objective. Journal of the Operational Research Society, 2004, 55, 1243–1255.
Garey, M. R., Johnson, D. S. and Sahni, S., Fowshop and jobshop schedules: complexity and approximation. Mathematics of Operations Research, 1976, 1, 117–127.
Goldratt, E. and Fox, R., The Race. 1986 (North River Press: New York).
Goldratt, E. and Cox, J., The Goal: A Process of Ongoing Improvement. 1992 (North River Press: New York).
Guinet, A. G. P. and Solomon, M., Scheduling hybrid flowshops to minimize maximum tardiness or maximum completion time. International Journal of Production Research, 1996, 34, 1643–1654.
Gupta, J. N. D., A functional heuristic algorithm for the flow-shop scheduling problem. Operations Research Quarterly, 1971, 22, 39–47.
Gupta, J. N. D., A flowshop scheduling problem with two operations per job. International Journal of Production Research, 1997, 35, 2309–2325.
Hoogeveen, J. A., Lenstra, J. K. and Veltman, B., Preemption scheduling in a two-stage multiprocessor flowshop is NPhard. European Journal of Operational Research, 1996, 89, 172–175.
Hsieh, J. C., Chang, P. C. and Hsu, L. C., Scheduling of drilling operations in printed circuit board factory. Computers and Industrial Engineering, 2003, 44, 461–473.
Hunsucker, J. L., and Shah, J. R., Performance of priority rules in a due date flow shop. Omega, 1992, 20, 73-89.
Hunsucker, J. L. and Shah, J. R., Comparative performance analysis of priority rules in a constrained flow shop with multiple processors environment. European Journal of Operational Research, 1994, 72, 102–114.
Jayamohan, M. S. and Rajendran, C., A comparative analysis of two different approaches to scheduling in flexibile flow shops. Production Planning and Control, 2000, 11, 572–580.
Jenabi, M., Fatemi Ghomi, S. M. T., Torabi, S. A. and Karimi, B., Two hybrid meta-heuristics for the finite horizon ELSP in flexible flow lines with unrelated parallel machines. Applied Mathematics and Computation, 2007, 186, 230–245.
Jin, Z. H., Ohno, K., Ito, T. and Elmaghraby, S. E., Scheduling hybrid flowshops in printed circuit board assembly lines. Production and Operations Management, 2002, 11, 216–230.
Jin, Z. H., Yang, Z., and Ito, T., Metaheuristic algorithms for the multistage hybrid flowshop scheduling problem. International Journal of Production Economics, 2006, 100, 322–334.
Johnson, S. M., Optimal two- and three-stage production schedules with setup times included. Naval Research Logistics Quarterly, 1954, 1, 61–67.
Kadipasaoglu, S. N., Xiang, W. and Khumawala, B. M., A comparison of sequencing rules in static and dynamic hybrid flow systems. International Journal of Production Research, 1997, 35, 1359–1384.
Kim, D. W., Na, D. G. and Chen, F. F., Unrelated parallel machine scheduling with setup times and a total weighted tardiness objective. Robotics and Computer Integrated Manufacturing, 2003, 19, 173–181.
Kurz, M. E. and Askin. R. G., Comparing scheduling rules for flexible flow lines. International Journal of Production Economics, 2003, 85, 371–388.
Lee, G. C., Kim, Y. D., Kim, J. G. and Choi, S. H., A dispatching rule-based approach to production scheduling in a printed circuit board manufacturing system. Journal of the Operational Research Society, 2003, 54, 1038–1049.
Lee, G. C., Kim, Y. D. and Choi, S. W., Bottleneck-focused scheduling for a hybrid flowshop. International Journal of Production Research, 2004, 42, 165–181.
Lenstra, J. K., Rinnooy Kan, A. H. G. and Brucker, P., Complexity of machine scheduling problems. Annals of Discrete Mathematics, 1977, 1, 343-362.
Leon, V.J. and Ramamoorthy, B., An adaptable problemspace-based search method for flexible flow line scheduling. IIE Transactions, 1997, 29, 115–125.
Linn, R. and Zhang, W., Hybrid flow shop scheduling: A survey. Computer & Industrial Engineering, 1999, 37, 57–61.
Low, C. Y., Simulated annealing heuristic for flow shop scheduling problems with unrelated parallel machines. Computers and Operations Research, 2005, 32, 2013–2025.
Moore, J. M., Sequencing n jobs on one machine to minimize the number of tardy jobs. Management Science, 1968, 15, 102–109.
Nawaz, M., Enscore, E. E. and Ham, I., A heuristic algorithm for the m-Machine, n-Job flow-shop sequencing problem. OMEGA, 1983, 11, 91–95.
Palmer, D. S., Sequencing jobs through a multi-stage process in the minimum total time-A quick method of obtaining a near optimum. Operations Research Quarterly, 1965, 16, 101–107.
Park, Y. B., Pegden, C. D. and Enscore, E. E., A survey and evaluation of static flow shop scheduling heuristics. International Journal of Production Research, 1984, 22, 127–141.
Pinedo, M., Scheduling: Theory, Algorithms, and Systems. 2002 (Prentice-Hall, Upper Saddle River, New Jersey).
Quadt, D. and Kuhn, H., A taxonomy of flexible flow line scheduling procedures. European Journal of Operational Research, 2007, 178, 686–698.
Rajendran, C. and Alicke, K., Dispatching in flowshops with bottleneck machines. Computers and Industrial Engineering, 2007, 52, 89–106.
Ruiz, R. and Maroto, C., A genetic algorithm for hybrid flowshops with sequence dependent setup times and machine eligibility. European Journal of Operational Research, 2006, 169, 781–800.
Santos, D. L., Hunsucker, J. L. and Deal, D. E., Global lower bound for flow shops with multiple processors. European Journal of Operational Research, 1995, 80, 112–120.
Santos, D. L., Hunsucker, J. L. and Deal, D.E., An evaluation of sequencing heuristics in flow shops with multiple processors. Computers and Industrial Engineering, 1996, 30, 681–692.
Sawik, T., An exact approach for batch scheduling in flexible flow lines with limited intermediate buffers. Mathematical and Computer Modeling, 2002, 36, 461–471.
Sivrikaya Serifoglu, F. and Ulusoy, G., Multiprocessor task scheduling in multistage hybrid flow-shops: a genetic algorithm approach. Journal of the Operational Research Society, 2004, 55, 504–512.
Wardono, B. and Fathi, Y., A tabu search algorithm for the multi-stage parallel machine problem with limited buffer capacities. European Journal of Operational Research, 2004, 155, 380–401.
Wittrock, R.J., An adaptable scheduling algorithm for flexible flow lines. Operations Research, 1988, 36, 445–453.
Yang, T., Kuo, Y. and Chang, I., Tabu-search simulation optimization approach for flow-shop scheduling with multiple processors – a case study. International Journal of Production Research, 2004, 42, 4015–4030.
Yu, L., Shih, H. M., Pfund, M., Carlyle, W.M., and Fowler, J.W., Scheduling of unrelated parallel machines: an application to PWB manufacturing. IIE Transactions, 2002, 34, 921–931. |
| Description: | 博士
國立政治大學
資訊管理研究所
90356502
95 |
| Source URI: | http://thesis.lib.nccu.edu.tw/record/#G0903565021 |
| Data Type: | thesis |
| Appears in Collections: | [資訊管理學系] 學位論文
|
All items in 政大典藏 are protected by copyright, with all rights reserved.
|
