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

Danny Hermelin (Corresponding author), Judith Madeleine Kubitza (Corresponding author), Dvir Shabtay (Corresponding author), Nimrod Talmon (Corresponding author), Gerhard J. Woeginger (Corresponding author)

Onderzoeksoutput: Bijdrage aan tijdschriftTijdschriftartikelAcademicpeer review

2 Citaten (Scopus)
1 Downloads (Pure)

Samenvatting

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.

Originele taal-2Engels
Pagina's (van-tot)275-286
Aantal pagina's12
TijdschriftOmega : The International Journal of Management Science
Volume83
DOI's
StatusGepubliceerd - 1 mrt 2019

Vingerafdruk Duik in de onderzoeksthema's van 'Scheduling two agents on a single machine: A parameterized analysis of NP-hard problems'. Samen vormen ze een unieke vingerafdruk.

  • Citeer dit