具等候時間窗口限制之零工式生產排程工作順序之決定

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

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

Title:	具等候時間窗口限制之零工式生產排程工作順序之決定
Authors:	何惠雯;Huan-Wen He
Contributors:	工業管理研究所
Keywords:	等候時間窗口;枝界法;零工式生產環境;第k長的最短路徑;time windows;branch and bound;job-shop;the k-th shortest path
Date:	2001-06-29
Issue Date:	2009-09-22 14:10:10 (UTC+8)
Publisher:	國立中央大學圖書館
Abstract:	本研究是探討在未給定操作順序下，branch and bound具等候時間窗口限制之零工式（job-shop）生產排程問題，發展一最佳演算法以決定作業之操作順序和極小化完成時間（Cmax）為目標。存在於任兩個作業間之等候時間窗口為一相依時間，此時間窗口影響當前一個作業操作完成後，在一定的時間窗口內必須進行下一個操作作業；目前學術上，大多出現於雙機流水線（two-machine flowshop）排程問題，但其結果並無法應用於現實環境中具等候時間窗口限制的零工式半導體製程，只有許淑芬（1998）做過此類問題，但其論文的主要架構是在給定一個操作順序下，判斷其可行性和極小化完成時間。本研究將此問題擴展至在未給定操作順序下，如何決定出以極小化完成時間為目標之作業操作順序的演算法。本研究首先探討單一機器排程問題，了解相依時間窗口限制之特性，並發展一演算法決定單機排程問題，爾後再將其結果擴展應用到多台機器問題上。在其求解單一機器排程問題之過程中，首先以分離圖建立模式，以分枝的方式展開可能的作業操作順序，計算各作業節點之可開始操作時間（release time）區間，將相依時間轉換成絕對時間，導入時間窗口一致性的概念，淘汰掉一些不可行的操作順序分枝，並以定界的方式儘早排除掉一些操作順序分枝；將單一機器問題之結果擴展應用到多台機器生產環境時，除了原有的相依時間窗口限制的特性外，還多了多台機器間相互的影響，如搶作業的情形發生，另外有個差異點，則是在多台機器生產環境中，為符合後續作業之等候時間窗口的限制，各工作未必接於時間點零開始操作，可經由延後某些作業的操作而使其為可行的操作順序，而在延後的過程中，本研究中每一個線段上之等候時間為整數（integer number），並把分離圖轉換成多機網圖，多機示意圖再轉成網圖，以融入the k-th shortest path演算法去做作業操作時間的調整，以尋找出最佳的操作順序及其完成時間。
Appears in Collections:	[Graduate Institute of Industrial Management] Electronic Thesis & Dissertation

Files in This Item:

File	Size	Format

社群 sharing

Loading...