Irreducible bin packing and normality in routing open shop

• Published in: Annals of mathematics and artificial intelligence 2021-09, Vol.89 (8-9), p.899-918
• Main Authors: Chernykh, Ilya, Pyatkin, Artem
• Format: Article
• Language: English
• Subjects: Artificial Intelligence; Complex Systems; Computer Science; Lower bounds; Management science; Mathematics; Schedules; Scheduling; Transportation networks; Traveling salesman problem
• ISSN: 1012-2443; 1573-7470
• DOI: 10.1007/s10472-021-09759-x

The open shop is a classical scheduling problem known since 1976, which can be described as follows. A number of jobs have to be processed by a given set of machines, each machine should perform an operation on every job, and the processing times of all the operations are given. One has to construct a schedule to perform all the operations to minimize finish time also known as the makespan. The open shop problem is known to be NP-hard for three and more machines, while is polynomially solvable in the case of two machines. We consider the routing open shop problem, being a generalization of both the open shop problem and the metric traveling salesman problem. In this setting, jobs are located at nodes of a transportation network and have to be processed by mobile machines, initially located at a predefined depot. Machines have to process all the jobs and return to the depot to minimize makespan. A feasible schedule is referred to as normal if its makespan coincides with the standard lower bound. We introduce the Irreducible Bin Packing decision problem, use it to describe new sufficient conditions of normality for the two machine problem, and discuss the possibility to extend these results on the problem with three and more machines. To that end, we present two new computer-aided optima localization results.