簡易檢索 / 詳目顯示

回結果列表
研究生： 趙謙文
CHIEN-WEN CHAO
論文名稱： 平行機考量機器具限制之最佳完工時間排程
Minimizing Sum of Job Completion Times on Parallel Machines with Machine Restrictions
指導教授： 廖慶榮
Ching-Jong Liao
口試委員: 王孔政
Kung-Jeng Wang
鄭元杰
none
學位類別： 碩士
Master
系所名稱： 管理學院 - 工業管理系
Department of Industrial Management
論文出版年： 2007
畢業學年度： 95
語文別： 英文
論文頁數： 41
中文關鍵詞： 平行機 、受限時段 、分枝界限法 、機器合適度 、匈牙利演算法
外文關鍵詞： Parallel machine scheduling, Availability constraints, Branch and bound algorithm, Machine eligibility, Hungarian method
相關次數： 點閱：220  下載：2 
分享至:
查詢本校圖書館目錄 查詢臺灣博碩士論文知識加值系統 勘誤回報

    • 本論文旨在討論兩個平行機總完工時間最小化的問題。第一個問題是考慮加工過程有限制時段的情形。本論文將發展一個最佳化分枝界限法，並應用三個定理，包含計算上限及下限演算法以及一個洞悉條件。由各種題目大小和參數的實驗得知，此演算法對於所有問題都非常有效率，特別是最困難的問題亦可在0.1秒內執行100次。另外我們發現一個重要的現象：當工件數相當大時，我們所發展的上限演算法幾乎可直接求得最佳解。
    本論文所探討的第二個平行機問題是考慮機器與工件可分為高與低兩個等級的情況。每個工件只有當它的等級不低於機器的等級時，才能由該等級機器處理，此限制稱為機器合適度限制。機器合適度限制的問題為平行機問題中的一個特例，其可視為加權雙比對問題，並利用匈牙利演算法求得最佳解。針對此問題的特殊架構，本論文提出一個更有效率的演算法，並以大量的題目做實驗，證明所提出的演算法在執行時間上遠優於匈牙利演算法。

    The thesis studies two problems of parallel machines to minimize the sum of job completion times. The first problem is to schedule jobs on two identical parallel machines when a machine is available only in a specified time period. This thesis proposes an optimal branch-and-bound algorithm which employs three powerful elements, including an algorithm for computing upper bound, a lower bound algorithm, and a fathoming condition. The branch and bound algorithm was tested on problems of various sizes and parameters. The results show that the algorithm is quite efficient to solve all the test problems. In particular, the total computation time for the hardest problem is less than 0.1 second for a set of 100 problem instances. An important finding of the tests is that the upper bound algorithm can actually find optimal solutions to a quite large number of problems.
    The second problem considered in this thesis is a parallel machine problem in which machines and jobs can be classified into two levels: high and low levels. A high-level machine can process all jobs while a low-level machine can process only low-level jobs. This problem is a special case of the parallel machine problem with machine eligibility restriction, which can be formulated as a weighted bipartite matching problem and solved by the famous Hungarian method. By exploiting the special structure of the problem, we develop a special streamlined algorithm that achieves dramatic computational savings. Results of computational experiments show that the suggested algorithm outperforms the Hungarian method in solving the problem.

    CHINESE ABSTRACT....................................................i ENGLISH ABSTRACT....................................................ii ACKNOWLEDGE.........................................................iii CONTENTS............................................................iv LIST OF FIGURES.....................................................vi LIST OF TABLES......................................................vii Chapter 1 INTRODUCTION..............................................1 1.1. Research motivation and objectives.............................1 1.2. Research restrictions..........................................3 1.3. Organization...................................................4 Chapter 2 LITERATURE REVIEW.........................................5 2.1. Parallel machine with capacitated restrictions.................5 2.2. Parallel machine with eligibility restrictions.................6 Chapter 3 PARALLEL MACHINE WITH CAPACITATED RESTRICTIONS............8 3.1. Preliminaries..................................................8 3.2. Theorems and bounds............................................9 3.2.1. Upper bound computation......................................9 3.2.2. Lower bound computation......................................14 3.2.3. A fathoming condition........................................19 3.3. The branch and bound algorithm.................................20 3.4. Computational results..........................................22 Chapter 4 PARALLEL MACHINE WITH ELIGIBILITY RESTRICTIONS............27 4.1. Problem formulation............................................27 4.2. Hungarian Method...............................................28 4.3. Proposed algorithm.............................................29 4.4. Computational results..........................................36 Chapter 5 CONCLUSIONS AND FUTURE STUDIES............................38 5.1. Conclusions....................................................38 5.2. Future studies.................................................39 REFERENCES..........................................................40

    Alagoz, O., Azioglu, M. (2003). Rescheduling of identical parallel machines under machine eligibility constraints. European Journal of Operational Research, 149, 523-532.
    Centeno, G., Armacost, R. L. (1997). Parallel machine scheduling with release time and machine eligibility restrictions. Computer and Industrial Engineering, 33, 273-276.
    Centeno, G., Armacost, R. L. (2004). Minimizing makespan on parallel machines with release time and machine eligibility restrictions. International Journal of Production Research, 42, 1243-1256.
    Cormen, T., Leiserson, C., Rivest, R. (2001). Introduction to Algorithms. MIT Press: MA.
    Glass, C.A., Mills, H.R. (2006). Scheduling unit length jobs with parallel nested machine processing set restrictions. Computers & Operations Research, 33, 620-638.
    Hwang, H.C., Chang, S.Y., Lee, K. (2004). Parallel machine scheduling under a grade of service provision. Computer & Operations Research, 31, 2055-2061.
    Lee, C.Y., (1991). Parallel machine scheduling with nonsimultaneous machine available time. Discrete Applied Mathematics, 30, 53-61.
    Lee, C.Y., Chen, Z.L. (2000). Scheduling jobs and maintenance activities on parallel machines. Naval Research Logistics, 47, 145-165.
    Lee, C.Y., Liman, S.D. (1993). Capacitated two-parallel machines scheduling to minimize sum of job completion times. Discrete Applied Mathematics, 41, 211-222.
    Li, C.L. (2006). Scheduling unit-length jobs with machine eligibility restriction. European Journal of Operational Research, 174, 1325-1328.
    Liao, C.J., Lin, C.H. (2004). Makespan minimization subject to flowtime optimality on identical machines. Computers & Operations Research, 31, 1655-1666.
    Liao, C.J., Lin, C.H. (2003). Makespan minimization for two uniform parallel machines. International Journal of Production Economics, 85, 205-213.
    Lin, Y., Li, W. (2004). Parallel machines scheduling of machine-dependent jobs with unit-length. European Journal of Operational Research, 156, 261-266.
    Mosheiov, G. (1994). Minimizing the sum of job completion on capacitated parallel machines. Mathematical of Computer Modelling, 20, 91-99.
    Pinedo, M. (2002). Scheduling: Theory, Algorithms, and System. Second edition, Prentice-Hall: NJ.
    Salem, A., Anagnostopoulos, G.C., Rabadi, G. (2000). A branch-and-bound algorithm for parallel machine scheduling problems. Proceedings of the International Workshop on Harbour, Maritime & Multimodal Logistics Modeling and Simulation, Society for Computers & Simulation International, 88-93, Portofino, Italy.
    Schmidt, G. (1984). Scheduling on semi-identical processors. Zeitschrift für Operations Research, 28, 153-162.
    Schmidt, G. (1988). Scheduling independent tasks with deadlines on semi-identical processors. Journal of Operational Research Society, 39, 271-277.
    Schmidt, G. (2000). Scheduling with limited availability, European Journal of Operational Research, 121, 1-15.

    QR CODE