Scheduling two agents on a single machine: A parameterized analysis of NP-hard problems

Danny Hermelin, Judith-Madeleine Kubitza, Dvir Shabtay, Nimrod Talmon and Gerhard J. Woeginger

Omega, 2019, vol. 83, issue C, 275-286

Abstract: Scheduling theory is a well-established area in combinatorial optimization, whereas the much younger area of parameterized complexity has only recently gained the attention of the scheduling community. Our aim is to bring these two fields closer together by studying the parameterized complexity of a class of two-agent single-machine scheduling problems. Our analysis focuses on the case where the number of jobs belonging to the second agent is considerably smaller than the number of jobs belonging to the first agent and thus can be considered as a fixed parameter k. We study a variety of combinations of scheduling criteria for the two agents and for each such combination we determine its parameterized complexity with respect to the parameter k. The scheduling criteria that we analyze include the total weighted completion time, the total weighted number of tardy jobs, and the total weighted number of just-in-time jobs. Our analysis determines the border between tractable and intractable variants of these problems.

Date: 2019
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (8)

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0305048317304152
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:83:y:2019:i:c:p:275-286

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.2018.08.001

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