Modeling single machine preemptive scheduling problems for computational efficiency

Fernando Jaramillo (), Busra Keles () and Murat Erkoc ()
Additional contact information
Fernando Jaramillo: Euclidox Data Science Technologies
Busra Keles: Frostburg State University
Murat Erkoc: University of Miami

Annals of Operations Research, 2020, vol. 285, issue 1, No 9, 197-222

Abstract: Abstract We propose two modeling approaches to solve single machine preemptive scheduling problems with tardiness related objectives. Employing the conventional time-indexed formulation, we first build a model that explicitly identifies completion times of jobs with varying release times, due dates, and processing times. The second model adopts the aggregate planning view and eliminates binary constraints. Under this approach, each job is seen as a unit demand while its due date is mapped to a period where this unit is demanded. With this mapping, the periodic job allocation decisions are transformed into periodic production decisions that are measured by fraction of demand. Consequently, instead of explicit representation of the job completion times, this model tracks the amounts of production completed and backlogged via inventory and shortage variables and conservation of units constraints. We establish that the latter model provides tighter bounds and demonstrate that it provides a more efficient platform for optimization via computational analysis employing four commonly used tardiness related criteria and a case study from a real life application. Numerical computations reveal that aggregate planning view becomes more dominant in terms of computational performance as the problem size grows.

Keywords: Preemptive scheduling; Time-indexed formulation; Weighted tardiness; Weighted earliness; Weighted completion; Aggregate planning (search for similar items in EconPapers)
Date: 2020
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://link.springer.com/10.1007/s10479-019-03298-9 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

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:spr:annopr:v:285:y:2020:i:1:d:10.1007_s10479-019-03298-9

Ordering information: This journal article can be ordered from
http://www.springer.com/journal/10479

DOI: 10.1007/s10479-019-03298-9

Access Statistics for this article

Annals of Operations Research is currently edited by Endre Boros

More articles in Annals of Operations Research from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().