Lot scheduling involving completion time problems on identical parallel machines

Biber Nurit (), Mor Baruch (), Schlissel Yitzhak () and Shapira Dana ()
Additional contact information
Biber Nurit: Ariel University
Mor Baruch: Ariel University
Schlissel Yitzhak: Ariel University
Shapira Dana: Ariel University

Operational Research, 2023, vol. 23, issue 1, No 12, 29 pages

Abstract: Abstract We address lot scheduling on m identical parallel machines, wherein lots contain one or several orders, potentially of different sizes, such that if the remaining portion of the lot is less than the size of the order, the order is split between lots. We consider two splitting models: consecutive splitting, in which the split order is assigned to several consecutive lots on the same machine; and parallel splitting, in which the order is split between the machines. Whereas the completion time of a non-split order is the makespan of the lot in which it is processed, we aim to minimize both the makespan and the total completion time for split orders. For the consecutive splitting model, we prove for $$m\,\ge \,2$$ m ≥ 2 that both objective functions can be solved in pseudo-polynomial time by introducing dynamic programming algorithm solutions. Additionally, for the makespan objective function, we provide a linear-time approximation algorithm in which the constant worst-case performance ratio is 2. For the parallel splitting model, we show for $$m\,\ge \,2$$ m ≥ 2 that the objective functions for both the makespan and the total completion time can be solved in polynomial time. Finally, we provide empirical results that support the efficiency of our dynamic programming solutions and approximation heuristic in practical scenarios. We demonstrate that these solutions run in microseconds for consecutive splitting and, even when faster performance is required, the values obtained from the approximation algorithm differ from the optimal solution by 2% at most.

Keywords: Lot scheduling; NP-hard; Dynamic programming (search for similar items in EconPapers)
Date: 2023
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s12351-023-00744-2 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:operea:v:23:y:2023:i:1:d:10.1007_s12351-023-00744-2

Ordering information: This journal article can be ordered from
https://www.springer ... search/journal/12351

DOI: 10.1007/s12351-023-00744-2

Access Statistics for this article

Operational Research is currently edited by Nikolaos F. Matsatsinis, John Psarras and Constantin Zopounidis

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