×

Scheduling the production of rolling ingots: industrial context, model, and solution method. (English) Zbl 1108.90315

Summary: We study a real-world scheduling problem arising in the context of a rolling ingots production. First we review the production process and discuss peculiarities that have to be observed when scheduling a given set of production orders on the production facilities. We then show how to model this scheduling problem using prescribed time lags between operations, different kinds of resources, and sequence-dependent changeovers. A branch-and-bound solution procedure is presented in the second part. The basic principle is to relax the resource constraints by assuming infinite resource availability. Resulting resource conflicts are then stepwise resolved by introducing precedence relationships among operations competing for the same resources. The algorithm has been implemented as a beam search heuristic enumerating alternative sets of precedence relationships.

MSC:

90B35 Deterministic scheduling theory in operations research
90B50 Management decision making, including multiple objectives
90C57 Polyhedral combinatorics, branch-and-bound, branch-and-cut
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Ahuja R., Network Flows (1993)
[2] Bartusch M., Annals of Operations Research 16 pp 201– (1988)
[3] Brucker P., Scheduling Algorithms (2001) · Zbl 1051.90011 · doi:10.1007/978-3-662-04550-3
[4] DOI: 10.1016/S0377-2217(98)00204-5 · Zbl 0937.90030 · doi:10.1016/S0377-2217(98)00204-5
[5] Fleischmann B., OR Spektrum 7 pp 175– (1985)
[6] K. Gentner, and N. Trautmann , 2002 . Scheduling der Produktion von Aluminiumwalzbarren mit SAP APO.Report WIOR-621, University of Karlsruhe.
[7] DOI: 10.1016/S0098-1354(01)00729-3 · doi:10.1016/S0098-1354(01)00729-3
[8] Kammer C., Aluminium Handbook Vol. 1: Fundamentals and Materials (1999)
[9] Kempf K.G., Journal of Manufacturing Systems 17 pp 37– (1998)
[10] Neumann K., Mathematical Methods of Operations Research 56 pp 513– (2002) · Zbl 1064.90018 · doi:10.1007/s001860200251
[11] Neumann K., Project Scheduling with Time Windows and Scarce Resources 508 (2001) · Zbl 0986.90013
[12] DOI: 10.1007/s00291-002-0100-8 · Zbl 1007.90505 · doi:10.1007/s00291-002-0100-8
[13] Pinedo M., Scheduling: Theory, Algorithms, and Systems (2001)
[14] DOI: 10.1016/S0377-2217(99)00153-8 · Zbl 0953.90028 · doi:10.1016/S0377-2217(99)00153-8
[15] DOI: 10.1007/s002910000042 · Zbl 0985.90042 · doi:10.1007/s002910000042
[16] N. Trautmann , 2001 . Anlagenbelegungsplanung in der Prozessindustrie. Gabler, Wiesbaden.
[17] Uzsoy R., International Journal of Production Research 33 pp 2685– (1995)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.