Scheduling: Agreement graph vs resource constraints

Mohamed Bendraouche, Mourad Boudhar and Ammar Oulamara

European Journal of Operational Research, 2015, vol. 240, issue 2, 355-360

Abstract: We investigate two scheduling problems. The first is scheduling with agreements (SWA) that consists in scheduling a set of jobs non-preemptively on identical machines in a minimum time, subject to constraints that only some specific jobs can be scheduled concurrently. These constraints are represented by an agreement graph. We extend the NP-hardness of SWA with three distinct values of processing times to only two values and this definitely closes the complexity status of SWA on two machines with two fixed processing times. The second problem is the so-called resource-constrained scheduling. We prove that SWA is polynomially equivalent to a special case of the resource-constrained scheduling and deduce new complexity results of the latter.

Keywords: Scheduling; Complexity theory; Identical machines; Agreement graph; Resource constraints (search for similar items in EconPapers)
Date: 2015
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (4)

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0377221714005542
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:ejores:v:240:y:2015:i:2:p:355-360

DOI: 10.1016/j.ejor.2014.07.003

Access Statistics for this article

European Journal of Operational Research is currently edited by Roman Slowinski, Jesus Artalejo, Jean-Charles. Billaut, Robert Dyson and Lorenzo Peccati

More articles in European Journal of Operational Research from Elsevier
Bibliographic data for series maintained by Catherine Liu ().