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

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

jsp.display-item.identifier=請使用永久網址來引用或連結此文件: 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

数据加载中.....