Single-machine common due date total earliness/tardiness scheduling with machine unavailability

Bülbül, Kerem and Kedad-Sidhoum, Safia and Şen, Halil (2019) Single-machine common due date total earliness/tardiness scheduling with machine unavailability. Journal of Scheduling, 22 (5). pp. 543-565. ISSN 1094-6136 (Print) 1099-1425 (Online)

This is the latest version of this item.

[thumbnail of ET-breaks.pdf] PDF
ET-breaks.pdf
Restricted to Repository staff only

Download (456kB) | Request a copy

Abstract

Research on non-regular performance measures is at best scarce in the deterministic machine scheduling literature with machine unavailability constraints. Moreover, almost all existing works in this area assume either that processing on jobs interrupted by an interval of machine unavailability may be resumed without any additional setup/processing or that all prior processing is lost. In this work, we intend to partially fill these gaps by studying the problem of scheduling a single machine so as to minimize the total deviation of the job completion times from an unrestrictive common due date when one or several fixed intervals of unavailability are present in the planning horizon. We also put serious effort into investigating models with semi-resumable jobs so that processing on a job interrupted by an interval of machine unavailability may later be resumed at the expense of some extra processing time. The conventional assumptions regarding resumability are also taken into account. Several interesting cases are identified and explored, depending on the resumability scheme and the location of the interval of machine unavailability with respect to the common due date. The focus of analysis is on structural properties and drawing the boundary between polynomially solvable and NP-complete cases. Pseudo-polynomial dynamic programming algorithms are devised for NP-complete variants in the ordinary sense.
Item Type: Article
Uncontrolled Keywords: single-machine; earliness/tardiness; common due date; unrestrictive; machine unavailability; maintenance; resumable; semi-resumable; non-resumable; NP−complete; dynamic programming.
Subjects: T Technology > T Technology (General) > T055.4-60.8 Industrial engineering. Management engineering
T Technology > T Technology (General) > T055.4-60.8 Industrial engineering. Management engineering > T57.6-57.97 Operations research. Systems analysis
Divisions: Faculty of Engineering and Natural Sciences > Academic programs > Industrial Engineering
Faculty of Engineering and Natural Sciences
Depositing User: Kerem Bülbül
Date Deposited: 14 Sep 2020 18:26
Last Modified: 15 Jun 2023 22:16
URI: https://research.sabanciuniv.edu/id/eprint/40093

Available Versions of this Item

Actions (login required)

View Item
View Item