政大機構典藏-National Chengchi University Institutional Repository(NCCUR):Item 140.119/35258
English  |  正體中文  |  简体中文  |  Post-Print筆數 : 27 |  Items with full text/Total items : 113160/144130 (79%)
Visitors : 50761381      Online Users : 702
RC Version 6.0 © Powered By DSPACE, MIT. Enhanced by NTU Library IR team.
Scope Tips:
  • please add "double quotation mark" for query phrases to get precise results
  • please goto advance search for comprehansive author search
    •  Adv. Search
    Home ‧ Login ‧ Upload ‧ Help ‧ About ‧ Administer Goto mobile version
    政大典藏 > College of Commerce > Department of MIS > Theses >  Item 140.119/35258


    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:[Department of MIS] Theses

    Files in This Item:

    File Description SizeFormat
    56502101.pdf45KbAdobe PDF2772View/Open
    56502102.pdf30KbAdobe PDF2823View/Open
    56502103.pdf37KbAdobe PDF2885View/Open
    56502104.pdf26KbAdobe PDF2853View/Open
    56502105.pdf37KbAdobe PDF2995View/Open
    56502106.pdf105KbAdobe PDF2742View/Open
    56502107.pdf194KbAdobe PDF2770View/Open
    56502108.pdf23KbAdobe PDF2846View/Open
    56502109.pdf43KbAdobe PDF21191View/Open


    All items in 政大典藏 are protected by copyright, with all rights reserved.


    社群 sharing

    著作權政策宣告 Copyright Announcement
    1.本網站之數位內容為國立政治大學所收錄之機構典藏，無償提供學術研究與公眾教育等公益性使用，惟仍請適度，合理使用本網站之內容，以尊重著作權人之權益。商業上之利用，則請先取得著作權人之授權。
    The digital content of this website is part of National Chengchi University Institutional Repository. It provides free access to academic research and public education for non-commercial use. Please utilize it in a proper and reasonable manner and respect the rights of copyright owners. For commercial use, please obtain authorization from the copyright owner in advance.

    2.本網站之製作，已盡力防止侵害著作權人之權益，如仍發現本網站之數位內容有侵害著作權人權益情事者，請權利人通知本網站維護人員(nccur@nccu.edu.tw)，維護人員將立即採取移除該數位著作等補救措施。
    NCCU Institutional Repository is made to protect the interests of copyright owners. If you believe that any material on the website infringes copyright, please contact our staff(nccur@nccu.edu.tw). We will remove the work from the repository and investigate your claim.
    DSpace Software Copyright © 2002-2004  MIT &  Hewlett-Packard  /   Enhanced by   NTU Library IR team Copyright ©   - Feedback