Article ID Journal Published Year Pages File Type
478931 European Journal of Operational Research 2008 10 Pages PDF
Abstract

In this paper we consider the problem of scheduling n independent jobs on m identical machines incorporating machine availability and eligibility constraints while minimizing the makespan. Each machine is not continuously available at all times and each job can only be processed on specified machines. A network flow approach is used to formulate this scheduling problem into a series of maximum flow problems. We propose a polynomial time binary search algorithm to either verify the infeasibility of the problem or solve it optimally if a feasible schedule exists.

Related Topics
Physical Sciences and Engineering Computer Science Computer Science (General)
Authors
, ,