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

Stefano Nasini and Rabia Nessah
Additional contact information
Stefano Nasini: LEM - Lille économie management - UMR 9221 - UA - Université d'Artois - UCL - Université catholique de Lille - Université de Lille - CNRS - Centre National de la Recherche Scientifique
Rabia Nessah: LEM - Lille économie management - UMR 9221 - UA - Université d'Artois - UCL - Université catholique de Lille - Université de Lille - CNRS - Centre National de la Recherche Scientifique

Post-Print from HAL

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.

Date: 2024-01-16
References: Add references at CitEc
Citations:

Published in European Journal of Operational Research, 2024, 312 (2), pp.427-444. ⟨10.1016/j.ejor.2023.06.034⟩

There are no downloads for this item, see the EconPapers FAQ for hints about obtaining it.

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:hal:journl:hal-04551081

DOI: 10.1016/j.ejor.2023.06.034

Access Statistics for this paper

More papers in Post-Print from HAL
Bibliographic data for series maintained by CCSD ().