Parallel machine scheduling with machine availability and eligibility constraints |
| |
Authors: | Lu-Wen Liao Gwo-Ji Sheen |
| |
Institution: | Institute of Industrial Management, National Central University, No. 300, Jhongda Rd., Jhongli City, Taoyuan County 32001, Taiwan, ROC |
| |
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. |
| |
Keywords: | Scheduling Parallel machines Network flows Availability constraint Eligibility constraint |
本文献已被 ScienceDirect 等数据库收录! |
|