利用半主動排程之搜尋求解具最小與最大時間延遲限制之零工式排程問題;Finding Semi-Active Schedules for Job Shop Scheduling Problem with Minimum and Maximum Time Lags

NCUIR > School of Management at National Central University > Graduate Institute of Industrial Management > Electronic Thesis & Dissertation > Item 987654321/64928

Please use this identifier to cite or link to this item: http://ir.lib.ncu.edu.tw/handle/987654321/64928

Title:	利用半主動排程之搜尋求解具最小與最大時間延遲限制之零工式排程問題;Finding Semi-Active Schedules for Job Shop Scheduling Problem with Minimum and Maximum Time Lags
Authors:	葉秩州;Yeh,Chih-chou
Contributors:	工業管理研究所
Keywords:	排程;零工式生產;最晚完工時間;分枝界線演算法;最小與最大時間延遲;Scheduling;Job shop;makespan;Branch and bound algorithm;minimum and maximum time lags
Date:	2014-07-28
Issue Date:	2014-10-15 14:34:17 (UTC+8)
Publisher:	國立中央大學
Abstract:	本論文主要探討具有最小與最大時間延遲限制之零工式 (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.
Appears in Collections:	[Graduate Institute of Industrial Management] Electronic Thesis & Dissertation

Files in This Item:

File	Description	Size	Format
index.html		0Kb	HTML	552	View/Open

社群 sharing

Loading...