在機器可用時間及合適度和工作群組限制下平行機台求極小化最晚完工時間之排程問題 ; Parallel machine scheduling with machine availability, eligibility and job family constraints for optimizing minimum makespan

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

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

Title:	在機器可用時間及合適度和工作群組限制下平行機台求極小化最晚完工時間之排程問題;Parallel machine scheduling with machine availability, eligibility and job family constraints for optimizing minimum makespan
Authors:	徐嘉駿;Chia-Chun Hsu
Contributors:	工業管理研究所
Keywords:	機器合適度;工作群組;最大流量;排程;分支界限法;機器可用時間;平行機台;job family;eligibility constraint;availability constraint;parallel machine;branch and bound;maximum network flow;Scheduling
Date:	2010-07-19
Issue Date:	2010-12-08 14:46:06 (UTC+8)
Publisher:	國立中央大學
Abstract:	本研究主旨在考慮極小化最晚完工時間之排程問題，首先探討n個可切割的工作在m台平行機台的排程問題，其中機器受限於可用時間與合適度的限制條件，而工作之間也有工作群組的限制。接著將問題延伸到一般性的n個不可切割工作在m台平行機台之排程問題。其限制條件有，機台無法一直處於可接受處理的狀態，例如：機台的損壞、維修；每個工作擁有其專有的特性，所以每個工作只能被安排在特定的機台接受服務；某些特性相近的工作會屬於同一個工作群組，當屬於同一個工作群組的工作要在同一台機台的同一個可用時間內接收服務，則將只能選擇其中之一接受服務。我們首先提出結合最大流量法和二元搜尋法去求得在工作可切割的環境下的最佳解，接下來我們探討工作不可分割的情況下的延伸問題，首先將在工作可切割的環境下所得到的最佳解值，與我們所呈現的分支界限法每個節點所算出的下限值取較大者當分支界限法的下限值，再利用最大處理時間優先法則求得問題的上限值。最後我們提出三個優先法則來增加我們所提出的分支界限法的演算效率。從數值分析的結果中可以呈現出，我們所提出的優先法則有效率的刪除掉一些不必要產生的節點。我們所提出的演算法能用於7個工作、5台機台和3個工作群組的問題下求得最佳解。In this paper we first consider the scheduling problem of n preemptive jobs on m identical parallel machine with machine availability, eligibility and job family constraints when minimizing the maximum completion time. Then we extend the scheduling problem to n non-preemptive jobs. Each machine could not available all time such as machine breakdown or preventive maintenance. Each job has its own characteristics, so it could only be processed on specified machines. Some similar jobs belong to the same family, it means that only one job of the family can be processed on the same availability interval of machine. We propose a maximum network flow and a binary search algorithm to solve the preemptive problem, and use its solution to compare with each node of lower bound by our propose branch and bound algorithm, then we obtain the bigger one to be the lower bound of non-preemptive problem, and use the longest processing time first rule (LPT) to find an upper bound. Finally, we provide three dominance rules to increase the efficiency of the branch and bound algorithm. Computational analysis shows that dominance rules could effectively eliminate unnecessary nodes. Our algorithm could get the optimal solution for the problem with up to 7 jobs, 5 machines, and 3 job families effectively.
Appears in Collections:	[Graduate Institute of Industrial Management] Electronic Thesis & Dissertation

Files in This Item:

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

社群 sharing

Loading...