期刊
INTERNATIONAL JOURNAL OF PRODUCTION ECONOMICS
卷 161, 期 -, 页码 74-82出版社
ELSEVIER SCIENCE BV
DOI: 10.1016/j.ijpe.2014.12.001
关键词
Scheduling; Identical parallel machines; Heuristic; Worst-case ratio bound
资金
- National Natural Science Foundation of China [71171114]
We study a two identical parallel-machine scheduling problem in which one machine is available to process jobs in a limited time interval while the other machine is always available over the scheduling horizon. The objective is to maximize the number of on-time jobs. As the problem is NP-hard, we develop a heuristic to tackle it by incorporating the backward adjusting and two-step look-ahead strategies into some existing heuristics for similar problems without the machine availability constraint. We show that our heuristic has a worst-case ratio bound of 4/3 and the bound is tight. (C) 2014 Elsevier B.V. All rights reserved.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据