Two heuristics for the deterministic, single operator, multiple machine, multiple run cyclic scheduling problem

The semiautomatic nature of machinery often makes it economical to assign more than one machine to a single operator. Multi-machine assignments are common in the textile, tooling and molding industries. They are also found where numerically controlled (NC) machinery are used and, more recently, where flexible manufacturing systems (FMS) are employed. Previous work on deterministic cyclic scheduling models has focused on determining the optimal number of usually identical machines with single runs to assign to an operator. In practice, the schedules are represented by man/machine charts. When, due to production requirements, we mix different types of runs with known times on non-identical machines, we have the deterministic, single operator, multiple machine, multiple run, cyclic scheduling problem. We present two heuristics for solving this more realistic generalization of earlier problems. For the nonidentical, multiple run case, the scheduling of the runs is crucial in minimizing the cycle time of the system. The integer programming formulation of small problems is large, and solving it directly could require excessive computation time on a large mainframe computer. Heuristic 1 selects the next machine run to schedule by minimizing the total immediate waiting cost of the operator and machines. The hourly machine costs reflect the relative merit of utilizing certain machines over others. Heuristic 2 first schedules the machine with the longest automatic processing time of run one. It then follows Heuristic 1 until the long processing time of the first run has ended. The next available run with the longest automatic processing time is then scheduled, and the process repeats. The underlying notion is that many short runs may be performed during the long automatic run of a machine. The heuristics are polynomially bounded, can be easily implemented on a mini- or micro-computer and in practice should be much faster than integer programming methods. In addition to the heuristics, we compute a lower bound on the cycle time. We use this bound as a measure of the effectiveness of a solution. If for a given schedule, the cycle time equals its lower bound, then the solution is optimal. Both heuristics were coded in FORTRAN on a CDC-6600 computer. An interactive version was also developed for a DEC PDP11/70. A detailed computational study is presented. In it, both heuristics solved 50 machine, 5 run problems in less than 10 CPU seconds on the CDC-6600. Computational experience indicates that the heuristics are efficient and often first schedules which have cycle times within 10% the lower bound.