簡易檢索 / 詳目顯示
| 研究生： |
陳俊龍 Chen,Chun Lung |
|---|---|
| 論文名稱： |
數個瓶頸為基礎的啟發式法則求解彈性流程系統排程問題 BOTTLENECK-BASED HEURISTICS FOR FLEXIBLE FLOW LINE SCHEDULING PROBLEMS WITH A BOTTLENECK STAGE |
| 指導教授： |
陳春龍
Chen,Chuen Lung |
| 學位類別： |
博士
Doctor |
| 系所名稱： |
商學院 - 資訊管理學系 Department of Management Information System |
| 論文出版年： | 2007 |
| 畢業學年度： | 95 |
| 語文別： | 英文 |
| 論文頁數： | 94 |
| 中文關鍵詞： | 瓶頸 、彈性流程系統 、非等效平行機 、派工法則 、啟發式方法 |
| 相關次數： | 點閱：101 下載：69 |
| 分享至: |
| 查詢本校圖書館目錄 查詢臺灣博碩士論文知識加值系統 勘誤回報 |
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.
LIST OF TABLES iv
LIST OF FIGURES vii
LIST OF ABBREVIATIONS viii
CHAPTER 1
INTRODUCTION 1
1.1 Introduction 1
1.2 Objective of the Study 5
CHAPTRR 2
LITERATURE REVIEW 7
2.1 The Classification of Approaches for FFL Scheduling Problems 7
2.2 Heuristics for FFL Problems with Identical Parallel Machines 11
2.3 Heuristics for FFL Problems with Unrelated Parallel Machines 15
2.4 Summary 16
CHAPTER 3
HEURISTICS FOR FLEXIBLE FLOW LINE SCHEDULING PROBLEMS 17
3.1 Nations and Assumptions 18
3.1.1 Nations 18
3.1.2 Assumptions 19
3.2 Proposed Heuristics to Minimize Makespan 20
3.2.1 Bottleneck-Driven Multiple Insertion Heuristic (BDMIH) 21
3.3 Proposed Heuristics to Minimize Number of Tardy Jobs 25
3.3.1 Bottleneck-Based Due Date Decision Heuristic (BBDDDH) 25
3.4 Proposed Heuristics to Minimize Total Tardiness 32
3.4.1 Bottleneck-Driven Adaptable Multiple Insertion Heuristic (BDAMIH) 33
CHAPTER 4
COMPUTATIONAL EXPERIMENTS 36
4.1 Conducting an Experiment for Minimizing Makespan Problems 41
4.1.1 Conducting an Experiment for Minimizing Makespan Problems in Unrelated Parallel Machine Environments 41
4.1.2 Conducting an Experiment for Minimizing Makespan Problems in Identical Parallel Machine Environments 50
4.2 Conducting an Experiment for Minimizing the Number of Tardy Job Problems 54
4.2.1 Conducting an Experiment for Minimizing the Number of Tardy Job Problems in Unrelated Parallel Machine Environments 54
4.2.2 Conducting an Experiment for Minimizing the Number of Tardy Job Problems in Identical Parallel Machine Environments 65
4.3 Conducting an Experiment for Minimizing Total Tardiness Problems 70
4.3.1 Conducting an Experiment for Minimizing Total Tardiness Problems in Unrelated Parallel Machine Environments 71
4.3.2 Conducting an Experiment for Minimizing Total Tardiness Problems in Identical Parallel Machine Environments 80
CHAPTER 5
CONCLUSIONS 85
REFERENCES 90
LIST OF TABLES
TABLES
TABLE 4.1 Experimental Design for Generating Minimizing Makespan Test Problems 39
TABLE 4.2 Experimental Design for Generating Minimizing the Number of Tardy Jobs and Total Tardiness Test Problems 40
TABLE 4.1.1.1 Performance Comparisons of the Proposed Heuristics and the Dispatching Rules (in terms of average RPD, average makespan (AM), and number of best solutions (NBS)) 45
TABLE 4.1.1.2 Analysis of Variance to Test the Significance of the Machine Selection Rules 46
TABLE 4.1.1.3 Results of LSD Test for Machine Selection Rules 46
TABLE 4.1.1.4 Analysis of Variance to Test the Significance of the Algorithms when ECALLM Is Used 47
TABLE 4.1.1.5 Results of LSD Test for Bottleneck-based Heuristics 48
TABLE 4.1.1.6 Effect of the Experimental Factors on the BDMIH/ECALLM (in terms of average RPD) 48
TABLE 4.1.1.7 Average Computational Time Required for the Heuristics 48
TABLE 4.1.2.1 Performance Comparisons of the Proposed Heuristics and the Dispatching Rules (in terms of average RPD, average makespan(AM), and number of best solutions (NBS)) 53
TABLE 4.1.2.2 Analysis of Variance to Test the Significance of the Algorithms 53
TABLE 4.1.2.3 Results of LSD Test for Bottleneck-based Heuristics 53
TABLE 4.1.2.4 Effect of the Experimental Factors on the BDMIH (in terms of average RPD) 54
TABLE 4.2.1.1 Performance Comparisons of the Proposed Heuristics and the Dispatching Rules (in terms of average RDI, average number of total tardy jobs (ATJ), and number of best solutions (NBS)) 59
TABLE 4.2.1.2 Analysis of Variance to Test the Significance of the Machine Selection Rules 59
TABLE 4.2.1.3 Results of LSD Test for Machine Selection Rules 59
TABLE 4.2.1.4 Analysis of Variance to Test the Significance of the Algorithms when ECALLM Is Used 60
TABLE 4.2.1.5 Results of LSD Test for Bottleneck-based Heuristics 60
TABLE 4.2.1.6 Effect of the Experimental Factors on the BODD+ATC/ECALLM (in terms of average RDI) 64
TABLE 4.2.1.7 Average Computational Time Required for the Heuristics 65
TABLE 4.2.2.1 Performance Comparisons of the Proposed Heuristics and the Dispatching Rules (in terms of average RDI, average number of total tardy jobs (ATJ), and number of best solutions (NBS)) 67
TABLE 4.2.2.2 Analysis of Variance to Test the Significance of the Algorithms 67
TABLE 4.2.2.3 Results of LSD Test for Bottleneck-based Heuristics 69
TABLE 4.2.2.4 Effect of the Experimental Factors on the BODD (in terms of average RDI) 69
TABLE 4.3.1.1 Performance Comparisons of the Proposed heuristics, the Dispatching Rules, and the SMIH (in terms of average RDI, average total tardiness (ATT), and number of best solutions (NBS)) 73
TABLE 4.3.1.2 Analysis of Variance to Test the Significance of the Machine Selection Rules 73
TABLE 4.3.1.3 Results of LSD Test for Machine Selection Rules 74
TABLE 4.3.1.4 Analysis of Variance to Test the Significance of the Algorithms when ECALLM Is Used 74
TABLE 4.3.1.5 Results of LSD Test for Bottleneck-based Heuristics 74
TABLE 4.3.1.6 Effect of the Experimental Factors on the BDAMIH/ECALLM (in terms of average RDI) 77
TABLE 4.3.1.7 Average Computational Time Required for the Heuristics 79
TABLE 4.3.2.1 Performance Comparisons of the Proposed Heuristics and the Dispatching Rules (in terms of average RDI, average total tardiness (ATT), and number of best solutions (NBS)) 83
TABLE 4.3.2.2 Analysis of Variance to Test the Significance of the Algorithms 83
TABLE 4.3.2.3 Results of LSD Test for Bottleneck-based Heuristics 84
TABLE 4.3.2.4 Effect of the Experimental Factors on the BDAMIH (in terms of average RDI) 84
LIST OF FIGURES
FIGURES
FIGURE 1.1 An example of a flexible flow line 2
FIGURE 1.2 Overview of the taxonomy 9
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.