Scheduling parallel serial-batch processing machines with incompatible job families, sequence-dependent setup times and arbitrary sizes

ABSTRACT

The scheduling of (parallel) serial-batch processing machines is a task arising in many industrial sectors. In the metal-processing industry for instance, cutting operations are necessary to fabricate varying metal pieces out of large base slides. Here, the (cutting) jobs have individual, arbitrary base slide capacity requirements (sizes), individual processing times and due dates, and specific material requirements (i.e. each job belongs to one specific job family, whereby jobs of different families cannot be processed within the same batch and thus are incompatible). In addition, switching of base metal slides and material dependent adjustments of machine parameters cause sequence-dependent setup times. All these conditions need to be considered while minimising total weighted tardiness. For solving the scheduling problem, a mixed-integer program and several tailor-made construction heuristics (enhanced by local search mechanisms) are presented. The experimental results show that problem instances with up to five machines and 60 jobs can be tackled using the optimisation model. The experiments on small and large problem instances (with up to 400 jobs) show that a purposefully used batch capacity limitation improves the solution quality remarkably. Applying the best heuristic to the data of two real-world application cases shows its huge potential to increase delivery reliability.

KEYWORDS:

• Serial batching
• incompatible job families
• sequence-dependent setup times
• arbitrary sizes
• total weighted tardiness
• mixed-integer linear programme

Disclosure statement

No potential conflict of interest was reported by the author(s).

Additional information

Notes on contributors

Christian Gahm

PD Christian Gahm (Dr., Dipl.-Inf.), born in 1979, studied Computer Science at the University of Augsburg with a focus on software engineering and programming languages. Since November 2006 he is a research assistant at the Chair of Production & Supply Chain Management. Since his doctorate in 2010, Mr. Gahm is head of the research group ‘Production Management’ and completed his habilitation in business administration in June 2021. His research interests are energy-aware and serial-batch scheduling as well as production planning concepts and advanced planning systems for special purpose machinery. In addition to courses in the areas of Supply Chain Management and Operations Management, he is responsible for the courses on ERP systems (SAP) at the Institute of Business Administration. The knowledge transfer of research results and of the latest methods into business practice is of great importance to him and has already led to great success in many practical projects.

Stefan Wahl

Stefan Wahl (M.Sc.), born in 1991, studied Industrial Engineering at the University of Augsburg with a focus on materials resource management and sustainability. Since April 2017 he is a research assistant and doctoral candidate at the Chair of Production & Supply Chain Management and concerned with serial-batch scheduling and production planning.

In teaching, Mr. Wahl imparts content from Operations Management, Discrete Event Simulation and ERP systems (SAP).

Axel Tuma

Professor Dr. Axel Tuma, born in 1963, graduated as an industrial engineer from the University of Karlsruhe in 1991. He worked there as a research assistant at the Institute of Industrial Management and Industrial Production until his doctorate in 1994 on the use of ‘artificial intelligence’ methods for emission-oriented production control. Following his doctorate, Tuma moved to the University of Bremen as a research assistant, where he completed his habilitation in business administration in February 2000. Until his move to the University of Augsburg, he worked there as a university lecturer in the field of sustainable ERP systems. Since 2001, Mr. Tuma holds the Chair of Production & Supply Chain Management at the Institute of Business Administration (University of Augsburg).