TY - JOUR

T1 - Irreducible bin packing and normality in routing open shop

AU - Chernykh, Ilya

AU - Pyatkin, Artem

N1 - Funding Information: This research was supported by the Russian Foundation for Basic Research, project 20-01-00045, and by the program of fundamental scientific researches of the SB RAS, project 0314-2019-0014. Publisher Copyright: © 2021, The Author(s), under exclusive licence to Springer Nature Switzerland AG.

PY - 2021/9

Y1 - 2021/9

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

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

KW - Computer-aided proof

KW - Irreducible bin packing

KW - Normality

KW - Optima localization

KW - Polynomially solvable subcases

KW - Routing open shop

UR - http://www.scopus.com/inward/record.url?scp=85108610492&partnerID=8YFLogxK

U2 - 10.1007/s10472-021-09759-x

DO - 10.1007/s10472-021-09759-x

M3 - Article

AN - SCOPUS:85108610492

VL - 89

SP - 899

EP - 918

JO - Annals of Mathematics and Artificial Intelligence

JF - Annals of Mathematics and Artificial Intelligence

SN - 1012-2443

IS - 8-9

ER -