A multi-machine scheduling solution for homogeneous processing: Asymptotic approximation and applications

Stefano Nasini and Rabia Nessah

International Journal of Production Economics, 2022, vol. 251, issue C

Abstract: In the context of job scheduling in parallel machines, we present a class of binary programs for the minimization of the τ-norm of completion time variances (a flexible measure of homogeneity in multi-machine job processing). Building on overlooked properties of the min completion time variance in a single machine and on an equivalent bilevel formulation, our approach provides asymptotic approximations (with quadratic convergence) in the form of lower and upper bounds. While resulting in almost identical solutions, these bounds can be computed more efficiently than the original τ-norm minimization problem. Further, dominance properties are enforced as linear constraints to improve the characterization of the exact solutions by these asymptotic approximations. On the empirical side, the proposed methodology is applied to three real contexts of processing services: nursing home management, IT troubleshooting service, and 311 call centers. Our numerical studies reveal that the proposed lower bound problem can be solved in less than one third of computation time, in comparison to the exact problem, while resulting in almost identical jobs sequences. Additionally, considering large-scale simulated instances with up to 450 jobs, our upper bound problem outperforms the state-of-the-art heuristic method in terms of solution quality in 100% of the analyzed instances.

Keywords: Multi-machine scheduling; Completion time variance; Homogeneous job processing; Bilevel optimization; Optimality bounds (search for similar items in EconPapers)
Date: 2022
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/S0925527322001487
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:proeco:v:251:y:2022:i:c:s0925527322001487

DOI: 10.1016/j.ijpe.2022.108555

Access Statistics for this article

International Journal of Production Economics is currently edited by Stefan Minner

More articles in International Journal of Production Economics from Elsevier
Bibliographic data for series maintained by Catherine Liu ().