Job shop scheduling to minimize makespan with explicit material handling considerations

Abstract

The efficient operation of a Flexible Manufacturing System (FMS) can be achieved by exploiting (i) Routing Flexibility and (ii) Scheduling Flexibility. Routing flexibility allows the selection of a machine on which an operation should be performed. Scheduling flexibility allows the determination of the processing sequence of jobs on a machine. Typically, the sequence of machines that a job has to visit is fixed and efficiencies can only be obtained by appropriate selection of machine schedules. The resulting problem requires sequencing of jobs on machines and the determination of routes for material handling vehicles. Traditionally, the machine sequences are determined independent of the vehicle routes. We demonstrate that, such a sequential approach often leads to suboptimal schedules. We study the problem of simultaneous scheduling of both the machines and the material handling system.

The difficulty of the simultaneous scheduling problem depends on the physical attributes of the FMS such as buffer sizes, travel distances, number of vehicles and their capacities. We present a classification scheme to categorize problems based on their physical attributes. We also show that the general problem is NP-Complete. Exact solution procedures for the problem must therefore be enumerative in nature. We present a binary integer linear programming formulation for the problem. We discuss the mathematical structure of the problem and show that there are two major sub-problems (i) A classical job-shop problem; and (ii) Routing of material handling vehicles. In the case of a single material handling vehicle, the second problem may be represented as an asymmetric traveling salesman problem with precedences and ready times (ATSP-PCRT). This variant of the ATSP has not thus far been addressed in literature. We develop a branch-and-bound procedure for its solution.

The overall problem is also solved exactly using a branch-and-bound approach. Because of the extreme difficulty of the problem exact solutions are obtained only for small problems (up to 3 machines and 6 jobs). For larger problems, we develop four heuristics. The first heuristic uses a sequential approach to scheduling of machines and the material handling system. The remaining three heuristics use a shifting bottleneck approach and differ in the treatment of the material handling vehicle. Both the exact procedure and the heuristics are extensively tested using randomly generated problems. Results of this computational testing are reported and discussed.