Time-flexible min completion time variance in a single machine by quadratic programming

Stefano Nasini and Rabia Nessah

European Journal of Operational Research, 2024, vol. 312, issue 2, 427-444

Abstract: In the context of job scheduling, the time required to complete a task is related not only to the intrinsic difficulty of the task, but also to the operator’s willingness to speed up (or slow down) its execution. In fact, service operators are sometimes authorized to flexibly calibrate job processing times when this is beneficial for the efficient design of services and production plans. In this paper, we show that some forms of time flexibility have major consequences on the operator’s ability to efficiently solve the problem of scheduling non-preemptive jobs to minimize the variance of their completion times. In fact, although this remains a challenging combinatorial problem, authorizing forms of processing time flexibility allows for solving it up to optimality by convex quadratic programming approaches, with a view to tackling large-scale instances, where no exact algorithm can be applied. Our contribution allows establishing a form of least flexibilization of job processing times while guaranteeing the solvability of the resulting problem by convex quadratic programming approaches. To this end, we provide novel bounding conditions for the characterization of an optimal sequence that strengthen and integrate state-of-the-art dominance properties. Our numerical tests indicate that this new methodology is capable of approaching the solution of the original min completion time variance problem with a max relative difference of about 0.05% (on average), with respect to the time-flexible solution.

Keywords: Scheduling; Time-flexibility; Completion time variance; Optimal sequence characterization; Lower bound (search for similar items in EconPapers)
Date: 2024
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0377221723005015
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:312:y:2024:i:2:p:427-444

DOI: 10.1016/j.ejor.2023.06.034

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