Optimal policies for minimizing total job completion times and deviations from common due dates in unrelated parallel machine scheduling

Oğuzhan Ahmet Arık ()
Additional contact information
Oğuzhan Ahmet Arık: Erciyes University

OPSEARCH, 2024, vol. 61, issue 3, No 22, 1654-1680

Abstract: Abstract This paper considers an unrelated parallel machine scheduling problem with a common due date where the objective is to minimize the sum of completion times, earliness, and tardiness durations of the jobs. This paper discovers some properties of the considered problem for restricted and unrestricted common due dates. By using these properties, the paper shows the existence of some optimal policies for the problem. Furthermore, optimal policies for the problem are found. According to our main findings, optimal policies for the problem are to increase the number of early jobs, to use the shortest processing time dispatching rule for tardy jobs, and to distribute tardy jobs on machines with tardy workloads that differ from each other as much as possible. These strategies for the problem are new to the literature and the problem has the potential to be extended. Using these strategies, the paper presents a novel heuristic algorithm for the problem that is rarely studied in the literature. Furthermore, the proposed heuristic is compared with two existing algorithms by generating some test instances for experimental study. The experimental study shows that the proposed heuristic outperforms other algorithms. Furthermore, the paper discusses which components of our proposed solution approach have impacts on the solution quality.

Keywords: Unrelated parallel machine; Common due date; Earliness; Tardiness; The sum of completion times; Optimal policy; 90B35; 90C59 (search for similar items in EconPapers)
Date: 2024
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s12597-024-00750-8 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:opsear:v:61:y:2024:i:3:d:10.1007_s12597-024-00750-8

Ordering information: This journal article can be ordered from
http://www.springer. ... search/journal/12597

DOI: 10.1007/s12597-024-00750-8

Access Statistics for this article

OPSEARCH is currently edited by Birendra Mandal

More articles in OPSEARCH from Springer, Operational Research Society of India
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().