Scheduling step-deteriorating jobs on a single machine with multiple critical dates

Byung-Cheon Choi, Eun-Seok Kim and Jun-Ho Lee

Journal of the Operational Research Society, 2025, vol. 76, issue 8, 1553-1563

Abstract: This paper studies a scheduling problem with step-deteriorating jobs and multiple critical dates in a single machine environment, where each job’s processing time increases stepwise at each critical date as its start time is delayed. Our goal is to minimize the total weighted completion time. First, we prove that the problem is NP-hard when there is one critical date and that even the unweighted case with two critical dates remains NP-hard and has inapproximability. We further establish the strong NP-hardness for the unweighted case with an arbitrary number of critical dates. As solution approaches, we develop a mixed integer linear programming formulation and develop a heuristic based on the weighted shortest processing time rule. Finally, extensive numerical experiments were designed according to the level of difficulty in evaluating the performance of the proposed heuristic.

Date: 2025
References: Add references at CitEc
Citations:

Downloads: (external link)
http://hdl.handle.net/10.1080/01605682.2024.2419979 (text/html)
Access to full text is restricted to subscribers.

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:taf:tjorxx:v:76:y:2025:i:8:p:1553-1563

Ordering information: This journal article can be ordered from
http://www.tandfonline.com/pricing/journal/tjor20

DOI: 10.1080/01605682.2024.2419979

Access Statistics for this article

Journal of the Operational Research Society is currently edited by Tom Archibald

More articles in Journal of the Operational Research Society from Taylor & Francis Journals
Bibliographic data for series maintained by Chris Longhurst ().