On a Routing Open Shop Problem on Two Nodes with Unit Processing Times
- PDF / 525,482 Bytes
- 10 Pages / 612 x 792 pts (letter) Page_size
- 15 Downloads / 188 Views
a Routing Open Shop Problem on Two Nodes with Unit Processing Times M. O. Golovachev1* and A. V. Pyatkin2, 1** 1 2
Novosibirsk State University, ul. Pirogova 1, Novosibirsk, 630090 Russia
Sobolev Institute of Mathematics, pr. Akad. Koptyuga 4, Novosibirsk, 630090 Russia Received January 10, 2020; in final form, April 20, 2020; accepted May 25, 2020
Abstract—The Routing Open Shop Problem deals with n jobs located in the nodes of an edgeweighted graph G = (V, E) and m machines that are initially in a special node called depot. The machines must process all jobs in arbitrary order so that each machine processes at most one job at any one time and each job is processed by at most one machine at any one time. The goal is to minimize the makespan; i.e., the time when the last machine returns to the depot. This problem is known to be NP-hard even for the two machines and the graph containing only two nodes. In this article we consider the particular case of the problem with a 2-node graph, unit processing time of each job, and unit travel time between every two nodes. The conjecture is made that the problem is polynomially solvable in this case; i.e., the makespan depends only on the number of machines and the loads of the nodes and can be calculated in time O(log mn). We provide some new bounds on the makespan in the case of m = n depending on the loads distribution. DOI: 10.1134/S1990478920030060 Keywords: routing open shop problem, unit processing time, complexity, scheduling, polynomial time, makespan bound
INTRODUCTION The Open Shop Problem is one of the classical scheduling problems. There are given a set M of m machines and a set J of n jobs. For each machine i and job j the processing time pij of job j on machine i is known. It is required to find a schedule with the minimum makespan to process each job on every machine in an arbitrary order so that each machine processes at most one job at a time and each job is processed by at most one machine at any one time. Moreover, it is assumed that all jobs are located in one place; i.e., the switching times for changing jobs for each machine are assumed to be zero. In the Routing Open Shop Problem, this condition is changed; namely, the jobs are located in the nodes of an edge-weighted graph G = (V, E), where the weight of an edge is equal to the time spent by the machine on moving from one node to another (if two jobs are in the same node then the switching from one job to another occurs immediately). All machines at the beginning are in the special node called depot. The makespan in the Routing Open Shop Problem is equal to the time of return the last machine to the depot after processing all jobs (or at the time of completion of all jobs in the depot). So, the Routing Open Shop problem generalizes the two well-known NP-hard problems at once: the Open Shop Problem and the Metric Traveling Salesman Problem. The Open Shop problem was first considered in [1], where it was proved to be polynomially solvable for m = 2 and NP-hard for m ≥ 3. It is known that for an arbitrary
Data Loading...
