具機器可用時間與機器合適度限制之平行機台排程問題; Parallel Machine Scheduling with Machine Availability and Eligibility Constraints

NCU Institutional Repository > 管理學院 > 工業管理研究所 > 博碩士論文 > Item 987654321/11133

請使用永久網址來引用或連結此文件: http://ir.lib.ncu.edu.tw/handle/987654321/11133

題名:	具機器可用時間與機器合適度限制之平行機台排程問題;Parallel Machine Scheduling with Machine Availability and Eligibility Constraints
作者:	盧寶后;Baw-Ho Lu
貢獻者:	工業管理研究所
關鍵詞:	Scheduling;branch and bound;network flows;par
日期:	2005-06-30
上傳時間:	2009-09-22 14:14:39 (UTC+8)
出版者:	國立中央大學圖書館
摘要:	In this paper we consider the problem of scheduling n non-preemptive jobs on m identical machines with availability and eligibility constraints for minimizing the maximum lateness. That is, each machine is not continuously available at all time and each job is only allows to be processed on specified machines. Each availability interval of machines has a specific service level, and each job has to be processed at availability intervals with the service level specified or higher one. We develop a branch-and-bound algorithm to solve this scheduling problem optimally. Firstly, we propose an algorithm based on the Least Flexible Job First/ Earliest Due Date First (LFJ/EDD) rule to find the upper bound. Network flow technique is used to model the scheduling problem of the preemptive jobs into a series of base problem that is equivalent to a maximum flow problem. Then, we propose a polynomial time algorithm that combines a maximum flow algorithm and binary search procedure to solve this scheduling problem optimally and use this result as our lower bound. Computational experiments are proposed to compare the validity with complete branching method and to test the efficiency of proposed branch and bound algorithm. According to the result of computational experiment, we find that the run time of our algorithm is acceptable.
顯示於類別:	[工業管理研究所 ] 博碩士論文

文件中的檔案:

檔案	大小	格式	瀏覽次數

在NCUIR中所有的資料項目都受到原著作權保護.

社群 sharing

資料載入中.....