Filter-and-fan approaches for scheduling flexible job shops under workforce constraints

Abstract

This paper addresses a flexible job shop scheduling problem that takes account of workforce constraints and aims to minimise the makespan. The former constraints ensure that eligible workers that operate the machines and may be heterogeneously qualified, are assigned to the machines during the processing of operations. We develop different variants of filter-and-fan (F&F) based heuristic solution approaches that combine a local search procedure with a tree search procedure. The former procedure is used to obtain local optima, while the latter procedure generates compound transitions in order to explore larger neighbourhoods. In order to be able to adapt neighbourhood structures that have formerly shown to perform well when workforce restrictions are not considered, we decompose the problem into two components for decisions on machine allocation and sequencing and decisions on worker assignment, respectively. Based on this idea, we develop multiple definitions of neighbourhoods that are successively locked and unlocked during runtime of the F&F heuristics. In a computational study, we show that our solution approaches are competitive when compared with the use of a standard constraint programming solver and that they outperform state-of-the-art heuristic approaches on average.

Keywords:

• Scheduling
• flexible job shop
• workforce constraints
• filter-and-fan
• constraint programming

Disclosure statement

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

Additional information

Funding

David Müller has been supported by the European Union and the state North Rhine-Westphalia through the European Regional Development Fund, as this work was conducted as part of the project ‘EKPLO: Echtzeitnahes kollaboratives Planen und Optimieren’ (EFRE-0800463). This work has furthermore partially been supported by the German Research Foundation (DFG) through the grant ‘Sustainable Personnel Planning in Highly Customized Assembly Lines with Work Sharing’ (KR 4926/3-1, OT 500/4-1).

Notes on contributors

David Müller

David Müller is a research assistant and doctoral candidate at the Chair of Management Information Science at the University of Siegen, Germany, where he also received his Diploma Degree in Business Informatics. Before his affiliation with the University of Siegen, he worked at the FZI Research Center for Information Technology in the research division Information Process Engineering and at Deloitte Consulting with a focus on Information Management. His research is concerned with algorithms and machine learning approaches for scheduling problems in industrial production environments.

Dominik Kress

Dominik Kress is a full professor and the head of the chair of Business Administration, especially Procurement and Production, at the Helmut Schmidt University in Hamburg, Germany. He received his doctoral degree as well as his postdoctoral teaching and research qualification from the University of Siegen, Germany. His current research interests focus on optimisation and machine learning methods for scheduling problems, competitive facility location problems, and game theoretic problem settings arising in production and logistics. He is an associate editor of Omega, The International Journal of Management Science.