Heuristics for predictive hoist scheduling problems

In this paper, we consider hoist scheduling problems in a job shop environment. For each job several operations can be operated on tanks, and their processing times are bounded. The objective is to assign resources to both processing and transport operations and then to schedule those tasks on each resource, without storage, while minimising makespan. A disjunctive graph is used to model the problem. It contains processing nodes, transportation nodes, and arcs to represent lower and upper bounds on processing and transportation times. Then a modified shifting bottleneck algorithm with a simple repair is used for finding sequences on resources. It is coupled with a first heuristic which repairs some sequences of transportation tasks. A second heuristic assigns and schedules transportation tasks one by one while arbitrating disjunctions. Various experiments on benchmarks show that our model and method are able to provide satisfying results. [Received 15 June 2012; Revised 3 January 2013; Accepted 7 June 2013]