Track: Operations Research

Abstract

In this study, we propose a heuristic method for obtaining a good approximate solution to job shop scheduling problems with bidirectional conveyance operations. In previous studies, there are heuristic solution methods and an exact solution method. The former are applicable only to problems with one way conveyance. The latter addresses problems with bidirectional transport, but it cannot solve medium to large scale problems in practical time. The objective is to minimize the makespan. The work order of jobs on each machine, crane assignment, and time to transfer job are determined.

We consider a job shop scheduling problem with two cranes located in a straight line. All jobs are transported by one of the cranes to the machine between the two yards. The two cranes must maintain a safety distance of at least one address to avoid collision. Crane interference is a case in which the crane transfer time is longer than the minimum to avoid a collision. We seek a schedule that prevents crane interference.

The unit time is a discrete value, which is the time it takes the crane to move one address. The positions of the yard, machine and crane are given by discrete addresses.

We obtain good approximate solutions in multiple steps. We derive approximate solutions based on the MTWR rule and an effective machine assignment method for the flexible job store scheduling problem. The MTWR rule is a rule to select the job with the largest total remaining work time and transfer time for each job.

In the first step, the work order of jobs on each machine is determined by selecting with a certain probability the MTWR rule and the random rule, respectively. Crane assignment is determined by selecting with a certain probability the CCFJ rule, the STTT rule, and the random rule, respectively. The CCFJ rule is a rule to select the closest crane from the job. The STTT rule is a rule to select the crane with the smallest total transfer time . If two jobs are to be transferred simultaneously, time to transfer job is determined by setting the time when both cranes transfer in the same direction. If the makespan is not updated T times, the process is terminated.

In the second and subsequent phases, time to transfer job is determined based on the job order at each machine and crane assignments obtained in the first phase. Each crane transfers the job at the earliest transfer start time. If the makespan is updated, the solution is saved. If all processes are completed at the earliest transfer start time, the solution is output．

Numerical experiments on several example problems have shown that the system successfully obtains good approximate solutions for some of the problems. In the future, we aim to construct a solution method that combines the proposed solution method and metaheuristics for medium and large scale problems.