本論文研究具等候時間限制之雙機流水排程中極小化總延遲時間之問題，等候時間限制為工作在第一台機器上之等候時間不能違背所給定的上限值，在以往延遲時間的相關研究中尚未考慮到工作本身的等候時間限制，在實務上，這樣的問題存在於食品、鋼鐵、和化學製造業上。 本研究以分支界限法求解求得一最佳解，發展的支配定理用來刪除不可能的工作排列順序，問題的下界採用由前往後的方式建立。 在實驗部分，設定相關參數驗證演算法之正確性和適用性。依據實驗結果，證明發展之演算法的執行時間是可接受的，除此之外，支配定理和下界刪除分支的節點情況亦如我們所預期的。 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.
