利用半主動排程之搜尋求解具最小與最大時間延遲限制之零工式排程問題

Finding Semi-Active Schedules for Job Shop Scheduling Problem with Minimum and Maximum Time Lags

葉秩州(Chih-chou Yeh)

指導教授 ： 沈國基

國立中央大學/管理學院/工業管理研究所/碩士(2014年)

摘要

本論文主要探討具有最小與最大時間延遲限制之零工式 (job shop) 排程問題，此類時間限制常見於實務上生產製造，例如：化學產業的鍍鎳製程、半導體產業的曝光製程等等，在此零工式排程問題中，作業與作業的開始時間之間有一最小與最大的時間延遲，使得作業必須等候一段時間後才能開始，也必須在一特定時間內完成，在此問題中我們的目標為最小化最晚完工時間。
針對此一排程問題，我們發展一分枝界線演算法來求解此問題，在此演算法中，我們引用及修改了 Carlier and Pinson (1989)及Sheen and Liao (2007)的proposition來增加演算法的效率，在分枝的方法上，我們結合了Giffler and Thompson (1960)及Carlier and Pinson (1989)的分枝方式。

關鍵字

排程 ； 零工式生產 ； 最晚完工時間 ； 分枝界線演算法 ； 最小與最大時間延遲

並列摘要

We consider the job shop scheduling problem with minimum and maximum time lags while minimizing the makespan. This problem typically arises in a manufacturing environment where the next operation has to be carried out within a specific time range after the completion of the immediately preceding operation. This type of temporal constraints occurs in practical applications such food production, chemical production and steel production. We describe a branch and bound algorithm, based on the input and output of given clique, a concept first proposed by Carlier and Pinson (1989), and the relevant propositions adopted from Sheen and Liao (2007), for finding the optimal waiting times. For enumerating the solutions efficiently, we incorporate the branching scheme form Giffler and Thompson (1960) and Carlier and Pinson (1989) to generate semi-active schedules for the job shop scheduling problem with minimum and maximum time lags. In the computational experiments, we generate scenarios to showing we can either find an optimal schedule or establish the infeasibility in different waiting time ranges.

並列關鍵字

Scheduling ； Job shop ； makespan ； Branch and bound algorithm ； minimum and maximum time lags

參考文獻

- Adams, J., Balas, E., Zawack, D. (1988). The shifting bottleneck procedure for job shop scheduling. Management Science, 34, 391-401.

- Armstrong, R., Lei, L., Gu, S. (1994). A bounding scheme for deriving the minimal cycle time of a single-transporter N-stage process with time-window constraint. European Journal of Operational Research, 78, 130-140.

- Baker, K. R. (1974). Introduction to Sequencing and Scheduling. Wiley, New York.

- Balas, E., Christofides, N. (1981). A restricted Lagrangean approach to the traveling salesman problem. Mathematical Programming, 21, 19-46.

- Balas, E., Lenstra, J. K., Vazacopoulos, A. (1995). The one-machine problem with delayed precedence constraints and its use in job shop scheduling. Management Science, 41(1), 94-109.