The crane problem : scheduling with sequence-dependent set-up and processing times.

Abstract

The problem of scheduling with sequence-dependent set-up times in a dynamic environment is investigated by studying how various dispatching rules perform when used to schedule two cranes. Motivated by a practical scheduling problem, the effect on production by delays due to the conflicts that result between cranes is examined. The problem is formalized, and it is shown that it can be classified as a problem of scheduling with both sequence-dependent set-up and processing times. The effectiveness of simple dispatching procedures that are used in machine scheduling and for the control of automated guided vehicles is studied, using a simulation of a crane aisle with jobs arriving dynamically. In addition, a dispatching rule, which explicitly uses information regarding the state of the second crane, is examined. The simulation results confirm the non-dominance of certain dispatching procedures, and show how performance is improved as the rules are provided more information regarding the state of the scheduling environment. It is shown that when there are sequence-dependent processing times, a scheduling heuristic that uses global information does significantly better than more commonly used local heuristics.