Skip to main content
Search
Search
Quick Search anywhere
Quick Search anywhere
Quick Search anywhere
Quick Search anywhere
Quick Search anywhere
Quick Search anywhere
Advanced Search
Skip main navigation
No Access

Heuristics for predictive hoist scheduling problems

Published Online:November 17, 2014pp 695-715https://doi.org/10.1504/EJIE.2014.065732

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.

Keywords

hoist scheduling problem, HSP, bounded processing times, shifting bottleneck procedure, disjunctive graph

References

  • 1. J. Adams, E. Balas, D. Zawack, '‘The shifting bottleneck procedure for job shop scheduling’' Management Science (1988) Google Scholar
  • 2. P. Baptiste, B. Legeard, M-A. Manier, C. Varnier, '‘Résolution d’un probléme d’ordonnancement avec la PLC’' European Journal of Automation, Intelligence Artificielle et Automatique (RAIRO-APII-JESA) (1996) Google Scholar
  • 3. J. Blazewicz, E. Pesch, M. Sterna, '‘The disjunctive graph machine representation of the job shop scheduling problem’' European Journal of Operational Research (2000) Google Scholar
  • 4. C. Bloch, C. Varnier, P. Baptiste, '‘Applying stochastic methods to the real time hoist scheduling problem’' (1996) Google Scholar
  • 5. C. Bloch, C. Varnier, P. Baptiste, '‘Stochastic methods combined with a modified shifting bottleneck heuristic for solving a blocking scheduling problem with bounded processing times’' in Proceedings of the 15th Triennal Conference of the International Federation of Operational Research Societies IFORS ‘99 (1999) Google Scholar
  • 6. P. Bonhomme, P. Aygalinc, S. Calvez, '‘Control and performance evaluation using an enumerative approach’' in Proceedings of the 5th World Multi-Conference on Systemics, Cybernetics and Informatic, SCI (2001) Google Scholar
  • 7. C. Caux, G. Fleury, M. Gourgand, P. Kellert, '‘Couplage méthodes d’ordonnancement-simulation pour l’ordonnancement de systémes industriels de traitement de surface’' RAIRO. Recherche opérationnelle (1995) Google Scholar
  • 8. A. Che, C. Chu, '‘Cyclic hoist scheduling in large real-life electroplating lines’' OR Spectrum (2007) Google Scholar
  • 9. A. Che, Z. Zhou, C. Chu, H. Chen, '‘Multi-degree cyclic hoist scheduling with time window constraints’' International Journal of Production Research (2011) Google Scholar
  • 10. A. El Amraoui, M-A. Manier, A. El Moudni, M. Benrejeb, '‘Genetic algorithm for a cyclic hoist scheduling problem with time-window constraints and heterogeneous part jobs’' (2010a) Google Scholar
  • 11. A. El Amraoui, M-A. Manier, A. El Moudni, M. Benrejeb, '‘Hoist Scheduling for multi-part CHSP in complex lines’ configuration’' (2011) Google Scholar
  • 12. A. El Amraoui, M-A. Manier, A. El Moudni, M. Benrejeb, '‘Resolution of the two-part cyclic hoist scheduling problem with bounded processing times in complex lines’' European Journal of Industrial Engineering (EJIE) (2012) Google Scholar
  • 13. A. El Amraoui, M-A. Manier, A. El Moudni, M. Benrejeb, '‘Heuristique pour l’ordonnancement cyclique multi-produits des lignes de traitement de surface’' (2010b) Google Scholar
  • 14. G. Fleury, '‘Applications de méthodes stochastiques inspirées du recuit simulé á des problémes d’ordonnancement’' Automatique-productique informatique industrielle (1995) Google Scholar
  • 15. M. Gondran, M. Minoux, Graphes et algorithms (1985) Google Scholar
  • 16. R. Graham, E. Lawler, J. Lenstra, A. Kan, '‘Optimization and approximation in deterministic sequencing and scheduling: a survey’' Annals of Discrete Mathematics (1979) Google Scholar
  • 17. A. Hertz, Y. Mottet, Y. Rochat, '‘On a scheduling problem in a robotized analytical system’' Discrete Applied Mathematics (1996) Google Scholar
  • 18. K. Hindi, K. Fleszar, '‘A constraint propagation heuristic for the single-hoist, multiple-products scheduling problem’' Computers & Industrial Engineering (2004) Google Scholar
  • 19. J. Hurink, S. Knust, '‘Tabu search algorithms for job-shop problems with a single transport robot’' European Journal of Operational Research (2005) Google Scholar
  • 20. D. Jégou, P. Baptiste, K. lee, '‘Multiagent systems for the hoist scheduling problem’' (2001) Google Scholar
  • 21. D. Jégou, D-W. Kim, P. Baptiste, K.H. Lee, '‘A contract net based intelligent agent system for solving the reactive hoist scheduling problem’' Expert Systems with Applications (2006) Google Scholar
  • 22. V. Kats, L. Lei, E. Levner, '‘Minimizing the cycle time of multiple-product processing networks with a fixed operation sequence, setups and time-window constraints’' European Journal of Operational Research (2008) Google Scholar
  • 23. P. Lacomme, Optimisation des systémes industriels de production: méthodes stochastiques et approche multi-agents (1998) Google Scholar
  • 24. P. Lacomme, M. Larabi, N. Tchernev, '‘A disjunctive graph for the job-shop with several robots’' (2007) Google Scholar
  • 25. J. Lamothe, M. Correge, J. Delmas, '‘A dynamic heuristic for the real time hoist scheduling problem’' in Emerging Technologies and Factory Automation, ETFA ‘95, Proceedings, 1995 INRIA/IEEE Symposium on (1995) Google Scholar
  • 26. L. Lei, T. Wang, '‘The minimum common-cycle algorithm for cyclic scheduling of two material handling hoists with time window constraints’' Management Science (1991) Google Scholar
  • 27. L. Lei, T. Wang, '‘On the optimal cyclic schedules of single hoist electroplating processes’' IIE Transactions (1994) Google Scholar
  • 28. J. Liu, Y. Jiang, Z. Zhou, '‘Cyclic scheduling of a single hoist in extended electroplating lines: a comprehensive integer programming solution’' IIE Transactions (2002) Google Scholar
  • 29. F. Mangione, N. Brauner, B. Penz, '‘Three-tank hoist scheduling problem with unbounded or zero-width processing windows’' (2003) Google Scholar
  • 30. M-A. Manier, C. Bloch, '‘A classification for hoist scheduling problems’' International Journal of Flexible Manufacturing Systems (2003) Google Scholar
  • 31. M-A. Manier, S. Lamrous, '‘An evolutionary approach for the design and scheduling of electroplating facilities’' Journal of Mathematical Modelling and Algorithms (2008) Google Scholar
  • 32. M. Mateo, R. Companys, New Computational Experiences on the Hoist Scheduling Problem for Cyclic Manufacturing of Different Products (2007) Google Scholar
  • 33. H. Paul, C. Bierwirth, H. Kopfer, '‘A heuristic scheduling procedure for multi-item hoist production lines’' International Journal of Production Economics (2007) Google Scholar
  • 34. L. Phillips, P. Unger, '‘Mathematical programming solution of a hoist scheduling program’' AIIE Transactions (1976) Google Scholar
  • 35. D. Riera, N. Yorke-Smith, '‘An improved hybrid model for the generic hoist scheduling problem’' Annals of Operations Research (2002) Google Scholar
  • 36. G. Shapiro, H. Nuttle, '‘Hoist scheduling for a PCB electroplating facility’' IIE Transactions (1988) Google Scholar
  • 37. P. Spacek, M-A. Manier, A. El Moudni, '‘Control of an electroplating line in the max and min algebras’' International Journal of Systems Science (1999) Google Scholar
  • 38. P. Yan, A. Che, N. Yang, C. Chu, '‘A tabu search algorithm with solution space partition and repairing procedure for cyclic robotic cell scheduling problem’' International Journal of Production Research (2012) Google Scholar
  • 39. P. Yan, C. Chu, N. Yang, A. Che, '‘A branch and bound algorithm for optimal cyclic scheduling in a robotic cell with processing time windows’' International Journal of Production Research (2010) Google Scholar
  • 40. Q. Zhang, H. Manier, M-A. Manier, '‘A disjunctive graph and shifting bottleneckheuristics for multi hoists scheduling problem’' (2011) Google Scholar
  • 41. Q. Zhang, H. Manier, M-A. Manier, '‘A genetic algorithm with Tabu search procedure for flexible job shop scheduling with transportation constraints and bounded processing times’' Computers & Operations Research (2012) Google Scholar
Previous article
Next article