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.
- Identical parallel machines
- Worst-case ratio bound
ASJC Scopus subject areas
- Business, Management and Accounting(all)
- Economics and Econometrics
- Management Science and Operations Research
- Industrial and Manufacturing Engineering