具等候時間限制下極小化總延遲時間之雙機流水排程問題; Minimizing tardiness in a two-machine flows-shop with limited waiting time constraint

NCU Institutional Repository > 管理學院 > 工業管理研究所 > 博碩士論文 > Item 987654321/11041

請使用永久網址來引用或連結此文件: http://ir.lib.ncu.edu.tw/handle/987654321/11041

題名:	具等候時間限制下極小化總延遲時間之雙機流水排程問題;Minimizing tardiness in a two-machine flows-shop with limited waiting time constraint
作者:	李世銓;Shih-Chuan Lee
貢獻者:	工業管理研究所
關鍵詞:	延遲時間;等候時間限制;排程問題;雙機流水排程;Scheduling;Limited waiting time constraint;Tardiness;Two-machine flow-shop
日期:	2003-06-27
上傳時間:	2009-09-22 14:12:40 (UTC+8)
出版者:	國立中央大學圖書館
摘要:	本論文研究具等候時間限制之雙機流水排程中極小化總延遲時間之問題，等候時間限制為工作在第一台機器上之等候時間不能違背所給定的上限值，在以往延遲時間的相關研究中尚未考慮到工作本身的等候時間限制，在實務上，這樣的問題存在於食品、鋼鐵、和化學製造業上。本研究以分支界限法求解求得一最佳解，發展的支配定理用來刪除不可能的工作排列順序，問題的下界採用由前往後的方式建立。在實驗部分，設定相關參數驗證演算法之正確性和適用性。依據實驗結果，證明發展之演算法的執行時間是可接受的，除此之外，支配定理和下界刪除分支的節點情況亦如我們所預期的。 We consider a two-machine flow-shop sequencing problem with limited waiting time constraints. Limited waiting time constraint means that for each job the waiting time between two machines can’t be greater than a given upper bound. The objective is to minimize the total tardiness. Relative research of tardiness has not yet considered waiting time constraint. In practice, such problem exists in food, steel, or chemical manufacturing process. Dominance criteria are developed to establish the priority of jobs in an optimal schedule. A lower bound on the total tardiness of the problem is derived by constructing the sequence of jobs forward. A branch-and-bound algorithm is built based on propositions and theorems found for the optimal sequence searching. Computational experiments are proposed to compare the validity with some special cases and to test the efficiency of proposed algorithm, where the parameters of processing time, due date and limited waiting time constraint are considered. According to the result of computational experiment, we find that the running time of our algorithm is acceptable. Besides, we prove that the dominance criteria and our bounding schema efficiently prune branching nodes as we expect.
顯示於類別:	[工業管理研究所 ] 博碩士論文

文件中的檔案:

檔案	大小	格式	瀏覽次數

在NCUIR中所有的資料項目都受到原著作權保護.

社群 sharing

資料載入中.....