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

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

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

Title:	具機器可用時間與機器合適度限制之平行機台排程問題;Parallel Machine Scheduling with Machine Availability and Eligibility Constraints
Authors:	盧寶后;Baw-Ho Lu
Contributors:	工業管理研究所
Keywords:	Scheduling;branch and bound;network flows;par
Date:	2005-06-30
Issue Date:	2009-09-22 14:14:39 (UTC+8)
Publisher:	國立中央大學圖書館
Abstract:	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.
Appears in Collections:	[Graduate Institute of Industrial Management] Electronic Thesis & Dissertation

Files in This Item:

File	Size	Format

社群 sharing

Loading...