Two- and three-machine open shop scheduling using LAPT-like rules. (July 2021) - Gawiejnowicz, Stanisław; Kolińska, Marta
Highlights: We consider two- and three-machine open shop scheduling problems. Operation processing times are fixed or proportionally deteriorating. The goal is to find a schedule with minimal makespan. We solve the problems using three LAPT-like scheduling rules. Abstract: In the paper, open shop scheduling problems with the objective to minimize the makespan and fixed or proportionally deteriorating operation processing times are considered. We solve the problems using three rules which are modifications of the Longest Alternate Processing Time (LAPT) rule that earlier was proved to be optimal for two-machine open shop scheduling problem with the same objective and fixed operation processing times. We prove that the first of the modified rules is optimal for two-machine open shop scheduling problem with proportionally deteriorating operation processing times. We also show, based on results of conducted numerical experiments, that the next two modified rules generate near-optimal schedules for three-machine open shop problems, regardless whether operation processing times are fixed or proportionally deteriorating.