Just-in-time scheduling problem with affine idleness cost

Zhen Tan and Guanqi Fu

European Journal of Operational Research, 2024, vol. 313, issue 3, 954-976

Abstract: We study a single-machine scheduling problem which minimizes total earliness, tardiness and idleness costs. In this problem, n jobs with job-specific due dates and processing times need to be processed in a non-preemptive fashion. We assume that when the idle time between two jobs is strictly positive, an idleness cost will be generated which is affine in the idle time. A hybrid solution approach is designed by integrating a tailored dynamic programming (TDP) algorithm for the exact timing solution and a customized Genetic Algorithm with restarts and early discarding (GARED) as the sequencing heuristic. By bounding the number of segments of the optimal cost function, we show that the proposed TDP algorithm has a low time complexity of O(n2) despite the non-convexity of the idleness cost function. In GARED, we utilize the monotonicity in the optimal cost in TDP to design a fast-screening scheme called Early Discarding which identifies and abandons an unpromising sequencing solution by evaluating only a short starting sub-sequence. Restarts are allowed to make the algorithm more robust in the case of premature local convergence of one evolutionary trial. Experimental results show that GARED significantly outperforms the basic elitist GA with or without restarts under most problems tested. Our hybrid method also scales well to large problem instances with n=300 and achieves similar or better performance compared to an exact algorithm in the literature, but the latter only applies to problems with integer-valued time parameters and no idleness cost in between the jobs.

Keywords: Scheduling; Earliness/tardiness cost; Idleness cost; Dynamic programming; Genetic algorithm (search for similar items in EconPapers)
Date: 2024
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0377221723006690
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:313:y:2024:i:3:p:954-976

DOI: 10.1016/j.ejor.2023.08.038

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