Please use this identifier to cite or link to this item: http://hdl.handle.net/10397/30607
Title: A heuristic for scheduling jobs on two identical parallel machines with a machine availability constraint
Authors: Wang, X
Cheng, TCE 
Keywords: Heuristic
Identical parallel machines
Scheduling
Worst-case ratio bound
Issue Date: 2015
Publisher: Elsevier
Source: International journal of production economics, 2015, v. 161, p. 74-82 How to cite?
Journal: International journal of production economics 
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.
URI: http://hdl.handle.net/10397/30607
ISSN: 0925-5273
DOI: 10.1016/j.ijpe.2014.12.001
Appears in Collections:Journal/Magazine Article

Access
View full-text via PolyU eLinks SFX Query
Show full item record

SCOPUSTM   
Citations

13
Last Week
0
Last month
0
Citations as of Nov 8, 2018

WEB OF SCIENCETM
Citations

9
Last Week
0
Last month
Citations as of Nov 9, 2018

Page view(s)

76
Last Week
1
Last month
Citations as of Nov 12, 2018

Google ScholarTM

Check

Altmetric


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.