The crane problem : scheduling with sequence-dependent set-up and processing times.
Date
1998
Authors
Clark, David, Dominic
Journal Title
Journal ISSN
Volume Title
Publisher
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.
Description
A research project submitted to the Faculty of Science, University of the
Witwatersrand, Johannesburg, in partial fulfillment of the requirements for the
degree of Master of Science.
Keywords
Production scheduling., Cranes, derricks, etc.