本研究主旨為探討一零工式排程問題，其作業間具有最小與最大時間延遲之限制，目標為使總完工時間最小化。最小延遲時間為作業與作業間必須間隔的等待時間，而最大延遲時間為作業與作業間至多的等待時間。 本研究主要是延伸沈國基與廖祿文(2007)所提出的研究結果，將具最小與最大時間延遲之單一機台排程問題擴展到零工式排程題。我們先以分離圖(disjunctive graph)來表示本研究的問題。接著，我們結合 Carlier 跟 Pinson (1989)所提出的“head and tail”概念以及沈國基與廖祿文(2007)所提出的分枝定界法來尋找這個排程問題的最佳解。首先，我們先研究並修改有關Carlier跟 Pinson (1989)所提出的“head and tail”概念。然後，我們將“head and tail”概念用於沈國基與廖祿文(2007)所提出的分枝定界法，將其修正來適用於決定零工式系統下的作業排程問題。 實驗的分析顯示，在分枝過程中的淘汰法則是有效率的並且在分枝定界法中只有非常小比例的節點被產生。本研究的分枝定界法能順利的求得此排程問題的最佳解，但是當作業與作業間的延遲時間間隔太逼近，會容易造成作業的開始時間範圍消失，並且得到不可行解。此分枝定界法能用於求解 10 台機器和 20 個工作的排程問題，並得到最佳解。 In this thesis,we study the problem of job-shop scheduling with minimum and maximum time lags when minimizing the makespan.This problem comes from industrial applications. Maximal time lags may be used to model situations when the delay between operations must not be too long in order to avoid deterioration of the products. Minimal time lags arise when waiting times between operations are imposed. Namely,each operation in job-shop system must be waiting for the lower bound of waiting time but do not exceed the upper bound of waiting time to perform the next operation. Besides, minimum and maximum time lags constraints on the starting time of each operation are also consider. We will extend the research from Sheen and Liao (2007) to solve this scheduling problem. We incorporate the concept of“head and tail”proposed by Carlier and Pinson (1989) and the branch and bound algorithm proposed by Sheen and Liao (2007) to solved the job-shop scheduling with minimum and maximum time lags problem. First,we modified the propositions of“head and tail”from Carlier and Pinson (1989).Second,we utilized these propositions improve the branching process which proposed by Sheen and Liao (2007) to find the input and output of a given clique and let the branch and bound algorithm to solve the sequence of operation on each machine in job-shop system for obtaining the optimal solution. Computational analysis shows that the propositions and rules for eliminating nodes during branching process is effective and very low percentage of nodes is generated by the branch and bound algorithm. The branch and bound algorithm could solve instances optimally. But,if the width of waiting time range be narrower between any pair of operations,it will easy to cause starting time interval of operation to become empty and make the infeasible result. The branch and bound algorithm can get the optimal solution for the problem with up to 10 machines and 20 jobs.
