Two machine scheduling subject to arbitrary machine availability constraint

Yumei Huo and Hairong Zhao

Omega, 2018, vol. 76, issue C, 128-136

Abstract: We study two machine scheduling subject to arbitrary machine availability constraint. Each machine can have multiple unavailable intervals, and both machines can be unavailable at the same time. The jobs can be resumed after being preempted by another job or interrupted by the unavailable intervals. We consider both the single criterion and the bi-criteria problems concerning two most common criteria: makespan and the total completion time. If makespan is the single criterion to optimize, Liu and Sanlaville (1995) have shown that the optimal schedule can be found in polynomial time. If total completion time is the single criterion, the existing algorithm can only find the optimal schedules for some special cases; however, the complexity of the problem with arbitrary machine availability constraint remains open. For two bi-criteria problems, i.e., the problem of minimizing the total completion time subject to the constraint that the makespan is minimum, and the problem of minimizing makespan subject to the constraint that total completion time is minimum, their computational complexity are also open. In this paper, we show all these three open problems are in P by giving optimal algorithms that run in polynomial time. An interesting finding in this research is that these three problems are closely related to each other and thus the algorithms also rely on one another.

Keywords: Arbitrary availability constraint; Bi-criteria optimization; Optimal algorithms (search for similar items in EconPapers)
Date: 2018
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (3)

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0305048317300737
Full text for ScienceDirect subscribers only

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:eee:jomega:v:76:y:2018:i:c:p:128-136

Ordering information: This journal article can be ordered from
http://www.elsevier.com/wps/find/supportfaq.cws_home/regional
https://shop.elsevie ... _01_ooc_1&version=01

DOI: 10.1016/j.omega.2017.05.004

Access Statistics for this article

Omega is currently edited by B. Lev

More articles in Omega from Elsevier
Bibliographic data for series maintained by Catherine Liu ().