Single machine scheduling problems involving job-dependent step-deterioration dates and job rejection

Baruch Mor ()
Additional contact information
Baruch Mor: Ariel University

Operational Research, 2023, vol. 23, issue 1, No 10, 19 pages

Abstract: Abstract This research focuses on scheduling problems with step-deteriorating job processing times. This phenomenon reflects various real-life settings where the processing time of the jobs, processed after their pre-determined and job-dependent deterioration date, is defined by a step function. A single machine setting is assumed, and optional job rejection is considered. The scheduling measure focused on in this study is makespan, and three variants of the basic problem are considered: (i) minimizing the sum of the scheduling measure and total rejection cost; (ii) minimizing the scheduling criterion, given an upper bound on the total rejection cost; and (iii) minimizing the total rejection cost, subject to a constraint on the scheduling measure. As minimizing the makespan on a single machine with step deterioration is known to be ordinary NP-hard, even if all jobs share a common deterioration date, all presented problems are NP-hard. For all problems, pseudo-polynomial time dynamic-programming (DP) algorithms are presented, establishing that they remain ordinary NP-hard. Furthermore, an extensive experimental study was conducted to determine the efficiency of the proposed algorithms.

Keywords: Single machine scheduling; Variable job processing times; Step deterioration; Job-dependent deterioration dates; Job rejection (search for similar items in EconPapers)
Date: 2023
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (2)

Downloads: (external link)
http://link.springer.com/10.1007/s12351-023-00754-0 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

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:spr:operea:v:23:y:2023:i:1:d:10.1007_s12351-023-00754-0

Ordering information: This journal article can be ordered from
https://www.springer ... search/journal/12351

DOI: 10.1007/s12351-023-00754-0

Access Statistics for this article

Operational Research is currently edited by Nikolaos F. Matsatsinis, John Psarras and Constantin Zopounidis

More articles in Operational Research from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().