Distributed scheduling for a job shop

This paper proposes a distributed scheduling approach to the job shop scheduling problem. Our basic idea is that by distributing the scheduling procedure among multiple computers, the computing time can be reduced even when we use some simple scheduling algorithm. To minimize the maximum completion time, the straightforward enumerative algorithm is used to generate all active schedules and the one-machine sequencing algorithm is adopted to obtain the lower boundary of the maximum completion time. The above procedure is implemented in multiple clients independently and one server coordinates the entire procedure. Each client receives the problem from the server, reserves the specified number of sub-problems, and then solves the remaining problem. One of the reserved sub-problems is transferred to the server as a new problem for the clients. The server also receives the current best solutions from the clients and the best value is sent to all clients immediately. Interruption of processing to generate a new problem is also activated if one or more clients enter the standby state. From numerical experiments using one server and up to nine clients, we have found that by increasing the number of clients, the computing time could be reduced greatly in some problems. In addition, three or more clients were required to solve some five-machine, twenty-job problems. However, in some cases, the computing time could not be reduced or the degree of reduction was not enough when the number of the computers was increased. The remaining research issues on distributed scheduling are also clarified.