期刊
EUROPEAN JOURNAL OF OPERATIONAL RESEARCH
卷 184, 期 2, 页码 458-467出版社
ELSEVIER SCIENCE BV
DOI: 10.1016/j.ejor.2006.11.027
关键词
scheduling; parallel machines; network flows; availability constraint; eligibility constraint
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. (C) 2006 Elsevier B.V. All rights reserved.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据