Title: Heuristics for predictive hoist scheduling problems

Authors: Qiao Zhang; Hervé Manier; Marie-Ange Manier; Christelle Bloch

Addresses: IRTES-SET, Université de Technologie de Belfort-Montbéliard, rue Thierry Mieg, 90010 Belfort Cedex, France ' IRTES-SET, Université de Technologie de Belfort-Montbéliard, rue Thierry Mieg, 90010 Belfort Cedex, France ' IRTES-SET, Université de Technologie de Belfort-Montbéliard, rue Thierry Mieg, 90010 Belfort Cedex, France ' Department of Computer Science and Complex Systems, Institut FEMTO-ST/Université de Franche-Comté, 1 Cours Leprince-Ringuet, 25201 Montbéliard, France

Abstract: 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]

Keywords: hoist scheduling problem; HSP; bounded processing times; shifting bottleneck procedure; disjunctive graph; heuristics; predictive scheduling; job shop scheduling; resource allocation; processing tasks; transport tasks.

DOI: 10.1504/EJIE.2014.065733

European Journal of Industrial Engineering, 2014 Vol.8 No.5, pp.695 - 715

Published online: 26 Nov 2014 *

Full-text access for editors Full-text access for subscribers Purchase this article Comment on this article