Minimizing the weighted number of tardy jobs on a single machine: Strongly correlated instances

Lukáš Hejl, Přemysl Šůcha, Antonín Novák and Zdeněk Hanzálek

European Journal of Operational Research, 2022, vol. 298, issue 2, 413-424

Abstract: This paper addresses a single machine scheduling problem minimizing the weighted number of tardy jobs, where each job is characterized by processing time, due date, deadline, and weight. It is known from the existing literature that so-called strongly correlated instances, i.e., instances where each job has the weight equal to its processing time plus a constant, are significantly harder to solve compared to instances without this relation. In this work, we extend an exact algorithm proposed in Baptiste et al. (2010) with the aim of solving the strongly correlated instances significantly faster. The main improvement is the new integer linear programming model for strongly correlated instances utilizing a decomposition according to the number of tardy jobs. Other proposed improvements are tighter lower and upper bounds which can be applied to all types of instances. The best-known algorithm proposed in Baptiste et al. (2010) cannot solve all instances with 250 jobs to the optimum within an hour. On the same hardware, our relatively simple improvements implemented into the algorithm proposed by Baptiste et al. enable solving all examined strongly correlated instances to the optimum within an hour for up to 5,000 jobs and reduce the computational time on other instances as well.

Keywords: Scheduling; Single machine; Weighted number of tardy jobs; Strongly correlated instances (search for similar items in EconPapers)
Date: 2022
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S037722172100597X
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:298:y:2022:i:2:p:413-424

DOI: 10.1016/j.ejor.2021.07.002

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