政大機構典藏-National Chengchi University Institutional Repository(NCCUR):Item 140.119/35258
English  |  正體中文  |  简体中文  |  Post-Print筆數 : 27 |  全文笔数/总笔数 : 113318/144297 (79%)
造访人次 : 51064185      在线人数 : 925
RC Version 6.0 © Powered By DSPACE, MIT. Enhanced by NTU Library IR team.
搜寻范围 查询小技巧：
  • 您可在西文检索词汇前后加上"双引号"，以获取较精准的检索结果
  • 若欲以作者姓名搜寻，建议至进阶搜寻限定作者字段，可获得较完整数据
    •  进阶搜寻
    政大機構典藏 > 商學院 > 資訊管理學系 > 學位論文 >  Item 140.119/35258


    请使用永久网址来引用或连结此文件: https://nccur.lib.nccu.edu.tw/handle/140.119/35258


    题名: 數個瓶頸為基礎的啟發式法則求解彈性流程系統排程問題
    BOTTLENECK-BASED HEURISTICS FOR FLEXIBLE FLOW LINE SCHEDULING PROBLEMS WITH A BOTTLENECK STAGE
    作者: 陳俊龍
    Chen,Chun Lung
    贡献者: 陳春龍
    Chen,Chuen Lung
    陳俊龍
    Chen,Chun Lung
    关键词: 瓶頸
    彈性流程系統
    非等效平行機
    派工法則
    啟發式方法
    日期: 2006
    上传时间: 2009-09-18 14:34:20 (UTC+8)
    摘要: 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.
    參考文獻: 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.
    描述: 博士
    國立政治大學
    資訊管理研究所
    90356502
    95
    資料來源: http://thesis.lib.nccu.edu.tw/record/#G0903565021
    数据类型: thesis
    显示于类别:[資訊管理學系] 學位論文

    文件中的档案:

    档案 描述 大小格式浏览次数
    56502101.pdf45KbAdobe PDF2772检视/开启
    56502102.pdf30KbAdobe PDF2823检视/开启
    56502103.pdf37KbAdobe PDF2885检视/开启
    56502104.pdf26KbAdobe PDF2853检视/开启
    56502105.pdf37KbAdobe PDF2995检视/开启
    56502106.pdf105KbAdobe PDF2742检视/开启
    56502107.pdf194KbAdobe PDF2770检视/开启
    56502108.pdf23KbAdobe PDF2846检视/开启
    56502109.pdf43KbAdobe PDF21191检视/开启


    在政大典藏中所有的数据项都受到原著作权保护.


    社群 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 ©   - 回馈