Journal Article

Lot scheduling involving completion time problems on identical parallel machines

Yitzhak, Schlissel, Nurit, Biber, Baruch, Mor, Dana, Shapira

2023

Overview

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≥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≥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.

• Publisher: Springer Nature B.V
• Subject: Algorithms / Approximation / Completion time / Dynamic programming / Functions (mathematics) / Operations research / Polynomials / Scheduling / Splitting