Abstract
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.
| Original language | English |
|---|---|
| Pages (from-to) | 74-82 |
| Number of pages | 9 |
| Journal | International Journal of Production Economics |
| Volume | 161 |
| DOIs | |
| Publication status | Published - 1 Jan 2015 |
Keywords
- Heuristic
- Identical parallel machines
- Scheduling
- Worst-case ratio bound
ASJC Scopus subject areas
- General Business,Management and Accounting
- Economics and Econometrics
- Management Science and Operations Research
- Industrial and Manufacturing Engineering