Two-agent parallel machine scheduling with a restricted number of overlapped reserved tasks

Byung-Cheon Choi and Myoung-Ju Park

European Journal of Operational Research, 2017, vol. 260, issue 2, 514-519

Abstract: We consider a two-agent scheduling problem on parallel machines such that each task of agent 2 has a given time window. Furthermore, we introduce a resource constraint under which the number of simultaneously processed tasks of agent 2 is restricted, although some machines are available. The objective is to minimize the total completion time for agent 1 while the total weight of the processed tasks for agent 2 is at or above a given threshold. Because the problem is known to be strongly NP-hard, we focus on the case with unit processing time. We analyze the computational complexity for its special cases, which have some restrictions on four parameters: the weight and the duration of agent 2, the number of machines, and the maximum number of simultaneously processed tasks of agent 2.

Keywords: Scheduling; Parallel machines; Competing agents; Complexity (search for similar items in EconPapers)
Date: 2017
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (2)

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0377221717300334
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:260:y:2017:i:2:p:514-519

DOI: 10.1016/j.ejor.2017.01.010

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 ().