Workforce rostering for decentrally controlled production systems: A simulation-based optimization framework using a genetic algorithm

Schwemmer, Julia; Günsel, Christian; Kühn, Mathias; Schmidt, Thorsten Article Workforce rostering for decentrally controlled production systems: A simulation-based optimization framework using a genetic algorithm Logistics Research Provided in Cooperation with: Bundesvereinigung Logistik (BVL) e.V., Bremen Suggested Citation: Schwemmer, Julia; Günsel, Christian; Kühn, Mathias; Schmidt, Thorsten (2023) : Workforce rostering for decentrally controlled production systems: A simulation-based optimization framework using a genetic algorithm, Logistics Research, ISSN 1865-0368, Bundesvereinigung Logistik (BVL), Bremen, Vol. 16, Iss. 1, pp. 1-26, https://doi.org/10.23773/2023_8 This Version is available at: https://hdl.handle.net/10419/297212 Standard-Nutzungsbedingungen: Die Dokumente auf EconStor dürfen zu eigenen wissenschaftlichen Zwecken und zum Privatgebrauch gespeichert und kopiert werden. Sie dürfen die Dokumente nicht für öffentliche oder kommerzielle Zwecke vervielfältigen, öffentlich ausstellen, öffentlich zugänglich machen, vertreiben oder anderweitig nutzen. Sofern die Verfasser die Dokumente unter Open-Content-Lizenzen (insbesondere CC-Lizenzen) zur Verfügung gestellt haben sollten, gelten abweichend von diesen Nutzungsbedingungen die in der dort genannten Lizenz gewährten Nutzungsrechte. Terms of use: Documents in EconStor may be saved and copied for your personal and scholarly purposes. You are not to copy documents for public or commercial purposes, to exhibit the documents publicly, to make them publicly available on the internet, or to distribute or otherwise use the documents in public. If the documents have been made available under an Open Content Licence (especially Creative Commons Licences), you may exercise further usage rights as specified in the indicated licence. https://creativecommons.org/licenses/by/4.0/ Received: 30 May 2022 / Accepted: 20 June 2023 / Published online: 19 July 2023 © The Author(s) 2023 This article is published with Open Access at www.bvl.de/lore ABSTRACT Decentral production control plays a crucial role within the paradigm of Industry 4.0. Due to the fast and flexible decisions on allocation and sequencing required by this type of control, there is no baseline production schedule in advance. This creates a dilemma for efficient staff deployment – typically worker deployment times must be planned at least a few days ahead. To solve this dilemma, we present a simulation-based genetic algorithm, which creates a roster with flexible deployment intervals without a rigid shift pattern based on the production system and job load. In accordance with the zeitgeist and Industry 5.0, we include flexible working time and desired working hours of production workers. For evaluation of the method, we consider worker attendance costs, job delay costs and a cost penalty of work scheduled outside of desired working hours. We forecast the decisions of the decentralized production system by solving a job shop scheduling problem (JSP) extended by manual operations. Our algorithm iteratively uses reasonable solutions of the JSP as basis for roster optimization. With this integrated approach, it is possible to balance job delay costs against worker attendance costs as well as cost for deviation from desired working hours. To ensure compliance with working time legislation, we include appropriate repair operators in the genetic algorithm. We demonstrate the efficiency of our heuristic approach by comparison to rigid shift systems and the best of a large number of randomly created rosters. KEYWORDS: Integrated workforce rostering and job shop scheduling problem · workforce requirement planning · decentral production control · Industry 4.0 · genetic algorithm with repair operators Logistics Research (2023) 16:8 DOI _ 10.23773/2023 _ 8 1 INTRODUCTION 1.1 Workforce Scheduling Dilemma in Industry 4.0 The concept of Industry 4.0 brings many technical and organizational changes. This does not stop at human resource planning and scheduling or at the nature of employee tasks either, as we have already discussed in [1]. However, a large part of the research community agrees that humans will continue to play a central role in the smart factory [2, 3]. In this contribution, we particularly focus on machine-dominated manufacturing environments. We do not refer to a mainly manually dominated project manufacturing like complex assembly processes, as described, e.g., in [4]. Especially in machine-dominated production environments, the nature of the tasks of the production workers will change [2, 3]. Within cyber-physical production systems (CPPS) humans will mainly have coordinating, controlling and directing tasks [2, 3]. Within the upcoming trend Industry 5.0 [5], the human-centric aspect becomes a new core issue. The progressive automation and digitalization will make simple tasks obsolete that are usually characterized by continuous time-requirements. Consequently, steady deployment continuity of manual tasks during the production process will decrease. This article is part of a focus collection on ‘‘Dynamics in Logistics – Models and Algorithms for Optimisation, Planning and Control.” Workforce Rostering for Decentrally Controlled Production Systems: A Simulation-based Optimization Framework using a Genetic Algorithm J. Schwemmer, C. Günsel, M. Kühn and T. Schmidt Julia Schwemmer Christian Günsel Mathias Kühn Thorsten Schmidt Chair of Material Handling and Logistics Engineering, TU Dresden, Germany, [email protected] telephone: +49 351 463 33492 fax: +49 351 463 35499 www.tu-dresden.de/ing/maschinenwesen/itla/tl 2 and predict the behavior of the decentral production control for single roster proposals. We use discreteevent simulation. Utilizing a specifically adapted genetic algorithm as optimization model, we search for efficient roster proposals to improve the overall performance of the production system. Against the background of variable working hours, we encode solution proposals in chromosomes of variable length. Thus, we enable differing numbers of working intervals (deployment intervals) for the workers in the solution finding process. We have specifically adapted the genetic operators, which are messy crossover, simulated binary crossover and Gaussian mutation. In addition, we have two purpose-built operators which can change the chromosome length. To deal with the fact that our problem is highly constrained due to working time legislation, we include a repair method consisting of five main repair operators. These are applied after the genetic operators and ensure that the legal requirements are met. To achieve overall optimization of the production system, the objective function consists of three main terms: cost of rostered worker attendance, deviation from desired working hours from the worker’s perspective and job delay. We evaluate the method by a comparison with classical two-shift and three-shift systems on the one hand and with the best of a large number of randomly generated rosters on the other hand. As problem case, we use the class of job shop scheduling problems (JSP) with the specification of time-windows (release and due dates) as well as multimode (varying parallel production schedule schemes). With regard to the manual tasks, a real-world application field is, for example, the production of medical implants (examples of manual tasks: visual inspection, insertion and removal of parts or performing non-standard production steps). We chose the JSP because it models machine-dominated production environments where manual tasks may still appear. Alternative problem cases, underlying workforce rostering, could be Line Balancing Problems or Resource Constrained Project Scheduling Problems (RCPSP) (see, e.g., [9]). However, it seems to us that these alternatives do not balance machine tasks and human tasks as well as the JSP. We do not attempt a novel optimization technique for the JSP. In order to take up the planning background of Industry 4.0, we solve the JSP by modelling a decentralized production control. The JSP solution is intended as a reasonable forecast of the decisions made by the decentralized production control. As for the solution method of our integrated rostering and scheduling problem, we are interested in a heuristic approach – in our case a GA – given the NP-hardness of the problem [10]. In Sect. 2, we give a rough overview of the state of the art that we have already presented in more detail in [11]. In Sect. 3, we precisely define our considered problem. Section 4 deals with a proposed solution The fourth industrial revolution will have impact on the organizational level of workforce scheduling. A basic element of Industry 4.0 is the decentralization of production control [6]. Thus, decisions on sequence and allocation of resources and orders will take place at lowest shop floor level. This will enable a high degree of flexibility and very rapid reactivity to process disturbances in production control. Decisions without long lead times will create a real-time control (as it is commonly called). There will be no (detailed) basic schedule for the production system. It will not be known (at least not in detail), which operation will be scheduled on which machine at what time. At this point, the dilemma of workforce scheduling in Industry 4.0 arises. In contrast to the production schedule, the staff roster has to be determined some days or weeks in advance so the workers have the opportunity for proper time management. In order to create an efficient roster by conventional methods, the information of the requirements from the production would have to be already available. However, with decentralized control, this information is not available due to the missing basic production schedule. This impedes efficient resource planning of the workforce. In addition to technical and organizational changes (see also “Work 4.0” [7]), there is a transformation in the attitude of work. This tendency is sometimes also referred to as New Work [8]. Both trends influence each other. Work-life balance is one key aspect increasingly coming to the fore [7]. This means that the balance between working time and free time gains higher relevance to employees. The main focus is no longer on career and salary. In contrast, compatibility of work and family or hobbies increases in importance. Companies must adapt to the changing wishes of their employees in order to be able to recruit and retain skilled personnel. Especially in highly specialized areas, a scarcity of skilled workers cannot be ruled out in the future [2]. 1.2 Scope and Solution Approach In this work, we are not going to completely solve the dilemma of intersection “scheduling vs. planning” in decentrally controlled production systems. However, we take a first step for the rostering of the workforce (“planning”-side) to enable an effective “scheduling”- side. We take advantage of flexible working hours and the rosters do not have to stick to fixed time grids of rigid shift systems. Flexible working hours may not only be beneficial from the employer’s perspective to adjust capacity supply to a volatile demand but also from the employee’s perspective to reach a better worklife balance when working at desired working hours. These requirements from both sides are not necessarily compatible, but we consider both and try to reach a compromise. The core idea of our solution approach is a simulation-based optimization model. Utilizing the simulation model, we can evaluate proposed rosters 3 Workforce Rostering for Decentrally Controlled Production Systems: A Simulation-based Optimization Framework using a Genetic Algorithm decentrally controlled production system is one main issue in our research area, we have limited the literature review to the application area of manufacturing and quantitative contributions since 2011. From the employees’ point of view, there is a trend with strong influence on the research topic, too. For several years, work-life balance has been gaining in importance, especially based on flexible working hours that can be influenced by the individual workers themselves. (see, e.g., [7, 17]). Related Problem Classes To get a general overview on the state of the art of the topic of staff scheduling and rostering, we recommend the three literature reviews [18–20]. Usually, the problem classes considered in these reviews only cover the staffing optimization component without taking into account the scheduling side of machine and job optimization [11]. For example, looking specifically at our described dilemma, the class of “EmployeeTimetabling” (see, e.g., [21–23]) is one of the first related problem classes. However, this class commonly only addresses human resource planning but not the machine shop problem [11]. Considering the transformation in the attitude of work as described at the end of Sect. 1.1, there is hardly any literature: Firstly, there are hardly any methods to roster workforce without rigid shift grid on the basis of time flexible working models [11]. Secondly, there are even less publications that include the aspect of employee-sided desired working [11]. So, on the one hand, there are publications dealing with workforce rostering [11]. On the other hand, there are publications dealing with the scheduling processes of machine operations and job sequences [11]. These are, for example, Job Shop Scheduling Problems (JSP/JSSP), Flow Shop Scheduling Problem (FSP/ FSSP), Flexible JSP (FJSP/FJSSP) or Line Balancing Problems [11]. Some of these problem classes have extensions where also human operations are to be scheduled (see, e.g., [24–29]) but they do not take into account the topic of workforce rostering in general or at least not at the same optimization level as the machine scheduling problem [11]. A class of scheduling problems constrained by machine capacity and by human capacity is commonly called dual resource constrained (DRC), where the term DRC is mainly used in the context of job shop scheduling problems. In DRC problems, the working hours are usually taken as a given and the rostering process is mostly not a subject of investigation [11]. Some of the DRC problems of the recent years are written in the context of Industry 4.0 (see, e.g., [24, 30]) and some do not take up the topic of Industry 4.0 (see, e.g., [25, 31]). Generally, in the field of workforce rostering or DRC scheduling problems, literature considering the background of a decentrally controlled production is rare [11]. Taking further facets of our considered issue into account, like the changed time requirements of the manual tasks, there are only very few publications that method which is based on the genetic algorithm adapted for the problem stated. In Sect. 5, we present some results of our optimization and simulation runs to evaluate the proposed algorithm. The paper ends with a short conclusion and planned extensions for the algorithm in Sect. 6. 2 STATE OF THE ART The human-centric aspect, to which our method of workforce rostering refers, is currently gaining importance and public interest. The new trend “Industry 5.0” [5] highlights exactly this human-centric perspective. A more general view of the topic of social sustainability in production planning is presented in the literature review of Trost et al. [12]. We have conducted a detailed literature review with focus on quantitative solution methods for roster optimization in [11], covering the following aspects: – parallel optimization of roster and machine plus workforce scheduling (i.e., job scheduling, staff rostering and staff assignment – see also [9]), – time-flexible working models, – consideration of working hours preferred by workers, – decentralized production control with short, sparse manual production tasks. Since publication of [11], there have not yet been any significant changes in the state of the art. So, we would like to refer to our paper [11] for more detailed information on the literature status. We give a short summary of the state of the art in this publication: Historical Development Flexible working time arrangements are not a new concept. Already at the turn of 2000, some concepts based on time accounts were introduced in the literature (see, e.g., [13]). These have primarily aimed at the adjustment of capacities to market fluctuations and thus realization of employer-side advantages. There was usually no inclusion of employee-side desired working hours. The workforce scheduling process was usually a second level optimization, optimized after finishing the machine sequencing and allocation (see, e.g., [14]). Therefore, it will not meet the described future requirements of Sect. 1.1. In 2011, Kagermann, Lukas and Wahlster [15] presented the concept of the fourth industrial revolution at the Hannover Fair the first time. From 2012 onwards, the German government also encouraged it (see, e.g., [6]) and the number of publications dealing with Industry 4.0 began to rise. Accordingly, corresponding concepts based on decentralized production control became more important. There are several research projects that deal with the technical collaboration of human and machine (e.g. see [16]). However, the organizational aspects of flexible shifting workforce in CPPS have hardly been considered [11]. As the 4 To give another example, the method of the research project “KapaflexCy” [38] requests available workers via a “shift doodle” app for additional shifts or shift extensions at short notice but only after the demand planning at machine level has been completed. Furthermore, the rostering system is based on a fixed rigid shift pattern. 3 PROBLEM STATEMENT The aim of our research project is to find a compromise between the predictability of workers’ working hours with sufficient lead time and the flexibility of decentralized control. The goal of our research is to determine an optimal workforce roster relative to a given job shop problem instance. We strive for an overall optimization that takes into account cost for worker attendance (labor cost) as well as cost for an understaffed production process. For the latter, we will use the target value of job delay that is caused by periods when less workers are available than required to finish the job in time. Our third criterion for optimization is to minimize the cost for the deviation of working time preferences of workers from actual worker deployment in the roster. Thus, we take into account the social tendency of the changing attitude of work. The concrete aim of this publication is only to create cost-efficient worker deployment rosters, not to determine schedules with sequence and allocation decisions for the underlying job shop problem. Fixing all dispatching decisions for the operative level of the production system would clash with the decentral production control, which makes dispatching decisions when they are due and does not need a fixed baseline schedule. In these terms, the deployment rosters only determine attendance times. The exact assignment of workers to tasks should finally take place in the short term by the decentralized production control. The operative level is still in the decision-making power of the decentralized control. However, in order to achieve an equivalent inclusion of the rostering and the machine level (as described in Sect. 1.1 and 2), it is essential to deal with the machine shop as well. The production runs carried out must also be included in the evaluation – even if they are not part of the solution – but they can be viewed as a forecast of the operative decisions made on the shop floor. For the detailed relationship between the both components, please see Sect. 3.1. 3.1 Relation of Workforce Roster to Job Shop Scheduling Problem (JSP) A workforce roster defines the attendance times (deployment intervals) of each staff member. Only if a worker is attendant in the production system, a manual task (part of the JSP) can be processed. In this way, the workforce roster (planning in advance) is covering model problem instances with the sort of sparse and short manual activities as described in Sect. 1.1 [11]. There are some contributions that do not assign their proposed model to a commonly known problem class. The phenomenon described above can also be observed here: either the publications are attributed to a pure personnel problem (see, e.g., [14]) or, if a machine problem is included, the rostering component is not taken into account (see, e.g., [32–35]). There are some publications that include the problem classes of job scheduling, staff rostering and staff assignment in an integrated problem class (see, e.g., [9, 10, 36, 37]). However, the problem conditions of these integrated problems differ from our requirements: For example, [10] consider a lexicographic objective function giving an order of the various objective functions. This in turn does not imply an optimization of the different problem classes (job + staff scheduling and staff rostering) on an equal optimization level. Mostly these integrated approaches do not include flexible shift planning but shifts have to be of the same length (see, e.g., [10, 36]). In general, we could not find any integrated staff rostering and scheduling problem that takes desired working time conditions from the employee’s side into account. To summarize, to the best of our knowledge, there are only publications dealing with related or reduced problems but there is no method handling exactly the dilemma described in Sect. 1.1 or more specifically within the scope of the research gap in the next paragraph. Furthermore, we did not find benchmark instances or problem model formulations for the precise research question we are interested in. Research Gap To summarize, the research gap our paper aims at (see also [11]) is characterized by a combination of the following requirements, which are to the best or our knowledge not sufficiently addressed by current research: – The production planning and control of machines, worker assignment and jobs as well as the roster generation for employees are merged on the same level of importance. There should be just one optimization level and no subsequent, “second-level” optimization for one of the components, – Both workers and machines are considered as separate but equally important and limited resources, – The planning of deployment times is completely independent of shift grids, – Working time preferences from production employees are included, and – The background of a decentrally controlled production system with changed processing time requirements of manual production tasks is considered. 5 Workforce Rostering for Decentrally Controlled Production Systems: A Simulation-based Optimization Framework using a Genetic Algorithm decentralized production control as given and model it on the basis of priority rules – “first-in-first-out” followed by “shortest processing time”. In the following subsections, we give more details of the extended JSP instance, the workforce roster, and the roster optimization problem. 3.2 Models for Extended JSP and Workforce Roster In the following, we specify the problem in a semiformal way. The following equations are an excerpt of the necessary mathematic modeling: 3.2.1 Model of the Extended JSP As starting point, we use the class of Job Shop Scheduling Problems (JSP) with specifications of multi-mode and time windows (MJSPTW). There are machines (or workstations) and jobs . Each job has a set of operations . There is a fixed sequence for the operations (predecessor/successor). Each operation has a set of modes . The modes in represent alternatives of operation , of which only one must be executed. A mode determines the required machine and the duration of the machine usage. Each machine can process only one operation at a time. Constraints for the JSP A valid solution of the JSP is characterized by the complete processing of all jobs, where for each operation of a job , exactly one operation mode has to be selected. These selected modes are determined by a start and end time such that . The start of the mode selected for the next operation of job must be after the end of the mode . In other words, modes selected for operations of the same job must not overlap. Each mode uses a concrete machine as defined in the JSP instance. The same machine may only be used by two different selected modes if the modes do not overlap in terms of their start and end. Extended JSP We extend this classic JSP by two aspects: Firstly, the standard JSP is extended by assigning to each job a planned release date and a required due date , which will be used to define delay cost. Secondly, for the workforce planning component of our use case, we have to extend the MJSPTW with manual activities (for a concrete example see Sect. 5.1). We do not distinguish between different qualifications of the workers; so, all workers are interchangeable (homogeneous qualification). The idea is, that each worker can perform every manual activity . However, a worker can perform only one manual activity at the same time. Thus, if an operation has already started on a machine the demand for the resource human of the production system (tasks included in the JSP on an operative level without lead time). To determine costs for a workforce roster and the instance of a job shop scheduling problem (JSP), the operations of the JSP instance must include manual activities which require the attendance of workers. A “solution” to this extended JSP (which in the sense of the problem description is not a solution of the optimization problem but only a forecast of a possible production run) consists in a concrete schedule in which the start and end of each job, operation, and manual activity is mapped onto the time axis. Any such forecast will take the availability of workers based on the given workforce roster into account and thus represent a valid production run, which fulfills the constraints of a JSP (see Sect. 3.2). In this way, the concrete timing of the start and end of jobs determined by the forecast will give rise to delay costs if a job ends after its due date. The attendance costs result from both perspectives – the roster (planned attendance time) and the forecasted production run (unplanned attendance time but scheduled in the forecast) – as our model allows to work extra hours to complete already started production tasks. In contrast to the delay costs and attendance costs, which depend on the JSP, the costs of deviation from preferred hours can be calculated only on the basis of the workforce roster itself. The forecasted production run estimates how the rostered working hours affect the processing of manual tasks (e.g., are adequate worker available) and thus the processing of jobs (e.g., waiting times of jobs or blocking times of machines). On this basis, the workforce roster can be prepared in advance. We do not attempt a novel optimization technique for the JSP. To achieve our aim of roster optimization, however, we need to assume and implement some solution of the JSP – as forecast of decentral production control – which does not need to be optimal but just reasonable. The flexibility on the side of decentral production control is to be modeled by using a multi-mode problem, in which there are alternative processing options for each production step. The processing options can vary in processing times and required resources (machine as well as human) and can differ for every job operation. Since resources are being shared, the scheduling of one job depends on the scheduling of other jobs. Accordingly, at almost every decision point in time, there are different parallel production schemes possible. Selecting one of them is the task of the decentral production control. Thus, the decentral production control determines allocation of resources and sequence of job operations, which will become the forecast of the production run. The scheduling logic of decentralized production control is typically either agent-based or priority rulebased. In this problem formulation, we consider the 6 A roster consists of a list of deployment intervals for each worker . The roster for worker is defined as: (1) where is a deployment interval of worker : (2) where is the start1of a deployment interval and is the end of the deployment interval . The roster for all workers is simply the set . 3.2.3 Model Connection of the Extended JSP and the Workforce Roster Problem The following constraint connects the extended JSP with the workforce roster: For each point in time , a manual activity may only start at , if there are more workers deployed at than there are active manual activities at . In this formulation, the number of workers deployed at is the number of workers for which there is a deployment interval such that . The start and end of a manual activity is fixed by the solution of the extended JSP. Thus, it is well defined at which times a manual activity is active, namely if . Thus, it is allowed to pass manual activities between workers, since the constraint does not require that individual workers are assigned to activities. Note that this constraint enforces that workforce rosters must have sufficiently many deployment intervals of sufficient lengths to allow the required assignment of start and end to all manual activities. It thus guarantees that all manual activities are completed. The forecasted solution of the extended JSP problem under the stated conditions implicitly also fixes the start and end time of each job that we refer to as and , respectively. On the basis of , we can define job delay costs by comparing it with . 3.2.4 Preferred Working Hours The labor flexibility on the worker side is to be implemented as follows: Workers can indicate preferred working hours that are not bound to any fixed shift pattern, but are simply the times at which they would like to work. These working hour requests are taken into account when creating the rosters but they are not obligatory. This means that the rosters do not necessarily cover the workers’ wishes exactly. Rostered working hours outside the desired working time window add costs to the target function value (e.g., 1Note that the start time and end time are integers, which refer to simulation time units used by our discrete-event simulation of job execution in a production system. In order to calculate hour-based costs, one has to interpret simulation time units in real time (e.g., 1 simulation time unit = 10 min, see Sect. 5.1) and then a worker is required due to a manual activity , the operation must be suspended until a worker is available. We will formulate this requirement as a constraint when connecting the extended JSP model with the roster model in Subsect. 3.2.3. We model the problem in such a way that manual activities do not occur alone, but a machine operation is always used as a basis. The machine remains occupied during the complete operation until the operation is finished. The idea is that a manual activity always needs an operating machine (or some workstation ). Manual activities can be shorter but not longer than their machine operation . By assigning rather short manual activities to a rather small subset of machine operations, we can model a situation as described in Sect. 1.1. Due to the extension of machine operations with manual activities, machine operations are no longer the smallest unit in the scheduling process – contrary to a standard JSP. Constraint for the Extended JSP A solution of the extended JSP assigns a start and end to all manual activities that belong to the selected operation modes such that . 3.2.2 Model of the Workforce Roster The concrete aim of the algorithm described in this publication is to create cost-efficient worker deployment rosters. We explicitly do not talk about schedules as solutions, since we only want to determine attendance times. The exact assignment of workers to tasks should finally take place in the short term through decentralized control and is not within the scope of our problem. For further considerations, we would like to define and distinguish the following terms: –Deployment interval: A period of time with a defined starting and end point. In this interval, a worker is present and ready to work in the company. The list of all deployment intervals thus forms the working hours of an employee. Technical and personal disruptions times (contingency allowance) may occur during the interval, but designated breaks are not included. –Break: A break separates deployment intervals (e.g., lunch break). Breaks have a certain minimum duration, but are not as long as rest periods. In practice, breaks are commonly between 0.5 – 2 hours long. –Rest period: A several hours long recovery time between shifts in which the employee has time for his/her personal needs (e.g., sleep time) and interests (e.g., family and hobbies). Shift: A shift consists of one or several deployment intervals and, if required, breaks. Two shifts are separated by a rest period, where the rest period is not part of the shift time. 7 Workforce Rostering for Decentrally Controlled Production Systems: A Simulation-based Optimization Framework using a Genetic Algorithm deployment intervals per day to <24. A mandatory rest period of 11 hours per day will further reduce this number. However, we do not assume a fixed number of deployment intervals, either per day or overall, within the time horizon. This means that there is no fixed number of decision variables, even for a given problem instance. Objective Function We measure all components of the objective function as cost (e.g., represented in €) to create better comparability between them. The total costs are to be minimized. The objective function consists of three parts: The costs for worker attendance (labor cost), costs for working hours deviating from the desired working hours and the costs for job delay . (3) A roster with minimal costs thus provides a compromise solution between the worker’s wishes, the requirements from the production system, and the costs from the worker deployments. In a real production scenario, fixing working hours in advance using such a minimal-cost roster creates planning reliability for workers while still optimizing for low labor cost and delay cost. Cost of Worker Attendance The cost of attendance (labor cost) is calculated as follows: (4) Here, is the partial duration of deployment interval that falls in the day time (e.g., 6:00 a.m. to 11:00 p.m.) and is the partial duration of in transfer to the real world, it can be interpreted as a bonus payment for the worker). We will denote the desired deployment intervals for each worker by 3.2.5 Overview of Time Dependent Variables According to the constraints, a worker can only perform a manual activity if the start of the activity is during his/her rostered working hours . So, a worker can start to work on a task during the rostered working hours . However, we allow that if the worker is not able to finish the already started activity within the rostered working hours and there is no free worker to hand over the task to, the worker will exceed his/her planned working hours and finish the task. Therefore, the rostered working hours and the effective working hours realized in the simulation can differ. So, there might be workers effectively deployed outside the times fixed for them in the roster. For this reason, we have to distinguish two to three versions of time dependent variables (see Table 1): plan, effective and, if applicable, wish. For example, each worker has preferred working hours but he/she has no preferred release date for job . 3.3 Decision Variables and Objective Function of the Optimization Problem Decision Variables The decision variables are the rostered attendance times of the workers . Due to the flexible setting of the working hours and the flexible time horizon, there is no explicit restriction to the number of deployment intervals , but other constraints (e.g., breaks and rest periods of legal restrictions) must be kept and they indirectly influence the number of feasible deployment intervals. For example, a minimum break length of one hour will limit the number of Table 1: The notation for the different versions of time dependent variables Plan Effective / simulated Wish (from the worker’s perspective) Set of all worker deployment intervals Single worker deployment interval Job release date – Job due date – 8 to protect workers. This makes the problem more complex (highly constrained) because the search space becomes more fragmented. We derive the main constraints from the German Working Time Act (e.g., maximal work load per day or minimal break length). The applied upper and lower bounds are in Table 2. The instantiation of constraints in the later test series will be on the specifications of this German law. However, these parameters can be set according to individual needs (e.g., country-specific or company-specific requirements). Once a worker has worked a certain amount of time (e.g., see ), a break should be taken. There are also specified minimum times for breaks. In the German Working Time Act this depends on the daily working time. For example, this is at least half an hour for more than one day’s work between 6 and 9 hours and a 45-minute break for longer working hours. To simplify matters, we set a minimum break value of 1h, as this means that all specifications are met using a single value. Smaller breaks (e.g., personal disruptions times as contingency allowance) should not be shown in an official work schedule of the worker (take in mind the level of workforce planning of HR). Smaller breaks fall into the personal distribution time of the contingency allowance (see definition in Sec. 1). We added to avoid scattering of working time across many short deployment intervals and breaks but this is not a legislative rule. The aim here is to avoid creating overly fragmented intervals of work that are impractical in real-world applications or generally in human resource planning. For example, a half-hour interval of working time is created, separated from breaks or even standing alone for that that falls in the night time (e.g., 11:00 p.m. to 6:00 a.m.). Both are measured in hours. stands for the labour costs per hour of worker . Note that, in the current stage of development, all are equal since workers do not have different qualifications. is the night work surcharge, e.g., 25% = 0.25. Cost of Desired Working Hours  || 󰇛 , 󰇜 (5) where is the overall amount of time in the intervals from that is outside all intervals from . This amount of time, which lies outside of the desired working hours, is measured in hours. is a percentage bonus surcharge factor applied to it. Cost of Job Delay If jobs are not completed by the due date , a penalty is paid, which is determined by a cost rate per hour (e.g., contract penalty). (6) Constraints due to Work-Hour Legislation In a staff rostering problem such as ours, numerous restrictions need to be taken into account that exist Table 2: Applied thresholds for the arrangement of working hours used configuration Minimal break duration (within a shift) 1h ** Minimal duration of a rest period between shifts 11h Minimal duration of a deployment interval 1h * Maximal duration of a deployment interval 6 h Maximal number of working hours per day 8 h Maximal number of working hours per shift 8 h * Maximal length of a shift (start of first deployment interval until end of last deployment interval in the shift) 13 h * * not directly given in the German Working Time Act ** simplified 15 Workforce Rostering for Decentrally Controlled Production Systems: A Simulation-based Optimization Framework using a Genetic Algorithm beginning and after each main operator to maintain a correct chromosome formulation. Each constraint is enforced individually for each worker section in the chromosome. All repair operators are applied within a worker section and independently from other worker sections. Auxiliary Repair Operator 1: Round & Sort This operator is the first step of maintaining a correct chromosome formulation and is only applied at the beginning of the repair algorithm. It guarantees the pre-condition for the remaining repair operators that all deployment intervals contain only integers and are sorted. For example, if one of the genetic operators produces a non-integer (in violation to our problem formulation), this operator corrects it to an integer. Additionally, the operator sorts the starting points of the deployment intervals within a worker section in ascending order. For example, the crossover operators can cause non-sorted deployment intervals. In particular, a random creation of the initial individuals needs the sorting process. Example: The two deployment intervals ([2, 6.9], [0.3, 5]) are replaced by ([0, 5], [2, 7]). This is not yet a correct chromosome representation as defined before. The description of the next auxiliary repair operator shows the missing modification. Auxiliary Repair Operator 2: Merge This second auxiliary operator keeps the representation of working time hours per worker unique and maintains a correct chromosome formulation. It is applied after the first auxiliary repair operator and after each main repair operator. It adjusts overlapping and “touching” deployment intervals within one worker section. With overlapping intervals, the end time of the first intervals is later than beginning of the next interval. With touching intervals, the end time of the first interval is the start point of the second interval. In both cases, the operator merges them into a single interval with start time of the first interval and end time of the second interval. A correct problem formulation does not contain any overlapping or “touching” intervals. The genetic operators and random generation of individuals, as well as the five main repair operators themselves can cause such situations of overlapping or “touching” intervals. Example: The two deployment intervals ([0, 5], [2, 7]) are replaced by the single deployment interval ([0, 7]). Main Repair Operator 1: Minimal Interval Duration This operator fixes violations of the constraint of minimal duration of a deployment interval (see Fig. 5). It does not consider the other constraints. Deployment intervals that are below a configurable threshold will be extended (see Fig. 5 case 1). The extension take place at the end of the interval, so the 4.6 Repair Mechanism Due to the many restrictions from working time legislation, our problem of finding an optimal roster is a highly constrained problem with a very fragmented search space of the decision variables. In fragmented solution spaces, the optimization strategy faces the difficulty of generating new solution proposals, which overcome the segment boundaries and lie in other solution space segments than the known solutions (e.g. the evaluated parent generations of the GA) (for further information see, e.g., [47]). In addition, in our case the constraints of a decision variable are not fixed but depend on the values of the other decision variables, at least within a worker section. Furthermore, there is no fixed number of decision variables at all. Accordingly, in the procedure of stochastic evolution, the probability is high that crossover and mutation operators violate constraints and thus the GA creates invalid child individuals. A key aspect in the development of our solution algorithm is therefore the question of how to deal with the constraints and/ or the constraint violations. In the literature, one can find different existing constraint-handling techniques for GA. These are, among others, especially penalty functions and repair mechanisms [48]. We do not want to have unacceptable solutions for the roster creation at the end of the optimization process, but want to be sure that the roster is definitively valid for all relevant labor time regulations (“hard constraints”). When using penalty functions, death penalty is a way to be sure of evolving generations with valid solutions. In this strategy, all invalid solutions receive such a high penalty that they are completely uninteresting for the further optimization process [48]. Given the large number of constraints, we assume that stochastic evolution does not produce a large number of valid individuals and the loss of too many individuals strongly affects the search mechanism of the GA within the solution space. Instead of rejecting invalid solutions by high penalty costs, we are going to repair them. This way we can be sure to always get valid solutions (=rosters) in the sense of the working time regulations. With our repair algorithm, we want to change the individuals as little as possible and we are only focusing on the constraints of working time restrictions. Due to the high number of solution proposals and function evaluations in connection with the high number of constraint violations we designed the repair algorithm to be fast and easy applicable. The developed repair algorithm consists of five main repair operators (MRO) with a fix application sequence and two auxiliary repair operators (ARO) (see Fig. 2). The mechanism ensures that all constraints are satisfied step by step. By applying the main repair operators one by one, there is one by one more constraint met. The main operators are designed in such a way that the established condition of constraint satisfaction of the previous operator is not violated. Each main repair operator needs to be applied only once per individual. The auxiliary repair operators are applied at the 16 Concretely, the operator works like this: If a break is too short, the start of the next deployment interval is moved to a later point in time (see Fig. 7 case 1). Then, if necessary, we have to remember our condition that we will not harm the already established constraints. If the following deployment interval gets too short, the operator will delete it completely (see Fig. 7 case 2). In our application, we set the lower bound . Fig. 7: Schematic illustration of MRO 3 (minimal break duration ) Main Repair Operator 4: Maximal Number of Working Hours per Shift , Maximal Span of Shift and Minimal Rest Period Duration This operator combines the observance of three constraints that have strong interdependencies between each other. These are the maximal amount of work within a shift, the length of a shift and the minimal rest period that divides two shifts (see definitions in Sect. 3). Therefore, it is the most complex repair operator which is modeled in a recursive way and uses two explicitly modeled global states in its algorithm. Repair operator 4 goes through the list of intervals of an individual and deletes or shortens intervals according to the following criteria. We explain the process on the base of our configured values (see Table 2): 1. The first deployment interval of the schedule of a worker starts a shift and the operator enters the state “in-shift”. This means that the next at most 13 h (max. shift length ) of the time line are interpreted as a shift. The shift might end earlier if the operator encounters a period without deployment intervals of at least 11h (minimal rest period ). 2. In the state “in-shift” the algorithm keeps track of the amount of work (the sum of the duration of deployment intervals) within the shift and handles the upcoming deployment intervals one by one. It distinguishes three cases: 2.1. The current deployment interval is completely within the considered shift, i.e. within the range of : If the deployment interval (potentially together with previous intervals of the same shift) exceeds the maximum amount of work (see Fig. end will be shifted towards the future. In this way, an interval can be merged with the following interval (see Fig. 5 case 2). This is the only main repair operator that extends the working hours of the workers. In our application, we set the lower bound . Fig. 5: Schematic illustration of MRO 1 (minimal interval duration ) Main Repair Operator 2: Maximal Interval Duration This operator manipulates the duration of the deployment intervals in view of a configurable upper limit of duration, after which the worker has to take a mandatory break. After the maximum time for a deployment interval , a break is inserted that lasts for the configurable minimum duration of breaks . This means that, if necessary, deployment intervals are split up (see Fig. 6 case 1). In order to avoid the destruction of the previously established minimum working times of the intervals by main repair operator 1, resulting intervals with a length below the minimum length are completely deleted (see Fig. 6 case 2). In our application, we set the upper bound to comply with the German Working Time Act. Fig. 6: Schematic illustration of MRO 2 (maximal interval duration ) Main Repair Operator 3: Minimal Break Duration Once the worker has worked a certain amount of time (e.g., see MRO 2), a break should be taken. At this point, we make a simplification for the algorithm. All designated breaks shall be of the specified minimum duration. That means we do not check whether we can piece together the necessary break time from several breaks (as would be OK with working time regulations), but make sure that each break is already long enough on its own for this shift.                                  17 Workforce Rostering for Decentrally Controlled Production Systems: A Simulation-based Optimization Framework using a Genetic Algorithm recursively with the current deployment interval (thereby processing the interval again but under a different state). 3.3. The current deployment interval overlaps the end of the rest period of duration : Here, the operator splits the interval at the edge of . Thus, the operator creates (like in step 2.3) a situation that allows for recursive resolution. The operator now handles both new deployment intervals recursively under the current state (“in-rest-period”) on the basis of steps 3.1 and 3.2. Main Repair Operator 5: Maximal Working Time per Day This operator ensures that the maximum allowed daily working time is not exceeded. After the configured threshold of working hours in a day, all further working hours on that day are cancelled (see Fig. 9 case 1). In other words, after summing up the working time with starting from the beginning of the day, a cut is made after the reached amount of the configured hours (in our case, e.g., 8 h). All later deployment intervals of that day are deleted. If the threshold is reached within a deployment interval, the interval will be shortened. If the threshold is reached within an interval whose end lies in the next day, the interval will be shorted until the new day starts but at least by a minimal break length. Generally, if a split or shortened deployment interval gets too short, the operator will delete this interval of too short duration (see Fig. 9 case 2). In our application, we set the upper bound . According to this concept, the realization of a weekly or longer limit is also conceivable. Summary of the Main Concept of the Repair Operators The auxiliary operators keep the correct format of the chromosomes. The main operators control the working time restrictions and modify the working hours, if necessary. They have a fixed application sequence. 8 case 1), it is truncated accordingly and the operator switches its state to “in-rest-period” (see step 3). Otherwise, the algorithm stays in the state “in-shift” and proceeds with the next deployment interval. 2.2. The current deployment interval is completely outside the considered shift, i.e. outside of the range of : This means that the end of the previous deployment interval has ended the shift and the next mandatory 11h ( ) rest period has already started then (see Fig. 8 case 3). The operator switches its state to “in-rest-period” (see step 3) and handles the unaltered current interval recursively under this new state. (The interval might lie within the rest period and has to be discarded completely or it might be so far in the future that it will constitute a new shift – the operator handles these cases recursively.) 2.3. The current deployment interval overlaps with the end of the considered shift, i.e. is partly inside and outside of the range of :In this case (see Fig. 8 case 3) the algorithm splits the deployment intervals in two at the edge of (“touching” deployment intervals are allowed during the application of this operator). Thus, the operator creates a situation in which step 2.1 and 2.2 can be applied. It handles both new deployment intervals recursively under the current state (“in-shift”) as described in step 2.1. and 2.2. 3. In the state “in-rest-period”, the operator will clear for an 11h ( ) rest period starting with the end of the deployment intervals that ended the previous shift. It again distinguishes three cases: 3.1. The current deployment interval is completely within the range of : This interval is simply discarded (see Fig. 8 case 2). 3.2. The current deployment interval is completely outside the range of : This interval starts a new shift. The operator changes its state to “in-shift” and proceeds Fig. 8: Schematic illustration of MRO 4 (restrictions regarding shift workload , shift span and rest period duration ) time in-shift s s ushift case 1 in-rest period in-shift s sushift in-rest periods ushiftspan lrest lrest ushiftspan case 2 case 3 before after 18 means that all jobs start at the same time . means that if every job were done in its shortest possible time directly at its release date, there would be no parallel jobs. . (9) For example, the due date factor means that the due date is so tight that the job can be finished in time only when the shortest operation mode is selected every time and there are no waiting processes. The extension with manual tasks is a random-based process. It is controlled by the parameter that is the probability that a machine operation is assigned a manual task. The exact start of the manual task within the machine operation and the duration is randomly generated, but is limited by the length of the machine operation. For example, the probability means that half of the machine operations receive a manual task. However, it does not mean that the workload of all manual task together is half the workload of all machine operations (due to the shorter duration of the manual tasks). We choose the number of workers in a way that with a common 2and 3-shift system the instances can be solved neither with much delay nor with a large staff surplus. As a final point of understanding the instances, the temporal interpretation must be clarified: Since we are creating rosters for workforce management, we will interpret the dimensionless time units of the instances to contain the workload for approximately one week (ca. 5-7 days). For our experiments, we use the instances Behnke & Geiger 60 [49], Brandimarte Mk15 [50], Dauzere 15a [51] and Fattahi 20 [52] with the modification parameters shown in Table 3. Applying one by one, we can be sure that there will be one more constraint met. Only the first repair operator will increase the working hours by extending deployment intervals. All other operators have a shortening effect on the working times by shrinking deployment intervals. Thus, operators 2-5 will keep the constraints automatically intact except for constraint of operator 1. In order to keep constraint of operator 1, intervals of too short duration will be discarded at the end of the application of every repair operator. 5 RESULTS In this section, we describe the used problem instances, followed by the results of the experiments. 5.1 Problem Instances To the best of our knowledge, there are no benchmark instances that fit our problem statement. We do not want to use completely new and unknown instances, but we will extend existing benchmarks. As basis, we choose well-known flexible job shop scheduling instances, which we extend for time windows and manual tasks. Release date and due date (the time window) are generated by two parameters, a concurrency factor and a due date factor , respectively. Both parameters calculate the respective time based on the shortest possible execution time of every job , i.e., the shortest possible path across the various operations: , (8) where the release date of the first job . For example, the concurrency factor Fig. 9: Schematic illustration of MRO 5 (maximal working time per day ) time 24 h within 1 day lbreak s s uday linterval linterval   24 h within 1 day s s uday linterval s s     19 Workforce Rostering for Decentrally Controlled Production Systems: A Simulation-based Optimization Framework using a Genetic Algorithm expresses the initial production plan of not beginning all jobs at once. The dark grey bars visualize the shortest possible execution time of the respective job, i.e., the case when for each operation the shortest mode Detailed Example: Brandimarte Mk15 Fig. 10 shows the 30 jobs of the Brandimarte MK15 in a Gantt-style diagram. The offset of the start times of the jobs results from the configured job concurrency and Table 3: Modification parameters of the used benchmark instances Behnke & Geiger 60 Time unit interpretation 0.2 2 0.5 4 5[min] Brandimarte Mk 15 Time unit interpretation 0.1 2.5 0.6 6 10 [min] Dauzere 15a Time unit interpretation 0 3 0.4 3 3[min] Fattahi 20 Time unit interpretation 0.05 3 0.8 5 4[min] Fig. 10: Release date due date and shortest possible execution time of job for test instance Brandimarte Mk15 20 number of workers is set in a way that the 2and 3-shift system can solve the instances neither with much delay nor with a large staff surplus (see Sect. 5.1). The randomly generated solutions are not completely blindly generated. We generate them in the same way we generated the start population (see Sect. 4.5) and guarantee their feasibility by applying the repair rules. The number of the randomly generated solutions is equal to the number of individuals (candidate rosters) of the proposed GA framework, so there will be the same number of objective function evaluations in both test runs. In the twoand three-shift systems, the workers are equally distributed over the shifts. If the number of workers is not divisible by the number of shifts, they are assigned to the morning shift and to the evening shift, if necessary. The shift times are as follows: 6:00 a.m. to 2:00 p.m. (morning shift), 2:00 p.m. to 10:00 p.m. (evening shift) and 10:00 p.m. to 6:00 a.m. (night shift). Accordingly, there is only one objective function evaluation for each test setup, as the roster is already fixed. The desired working times are the same for all experiments and are generated per worker for each day as an 9 h-interval (1 hour lunchbreak included), which is normally distributed with mean at 8:00 a.m. and with a standard deviation of 2 h. would be chosen. The light grey bars visualize the designated slack time until the due dates of the jobs. If a job finishes before its due date, there will not be any delay costs. Fig. 11 shows the same problem instance in more detail and without the due date information. Each of the 30 vertically arranged jobs consists of averagely three operation modes which are represented by the horizontal lines. The horizontal segmentation of a job in operations is visualized by the gaps in the horizontal lines – the longest mode of an operation determines the length of the line and the gaps appear for the modes with shorter duration. The dark line segments visualize manual activities of which each operation mode can have at most one. 5.2 Evaluation Since there are no existing benchmark results available from other publications, we will compare the performance of the developed algorithm to randomly generated solutions as well as to the twoand threeshift systems widely used in practice. All experiment runs are based on the same number of available workers in each respective instance. In this way, all compared rostering methods have the same upper bound of working hours capacity but differ in the arrangement of working hours (i.e., the roster). Keep in mind, that the Fig. 11: Illustration of the share of manual activities (in black) as well as alternative modes of the jobs for test instance Brandimarte Mk15 21 Workforce Rostering for Decentrally Controlled Production Systems: A Simulation-based Optimization Framework using a Genetic Algorithm utilization decreases until the end of the second shift. In the three-shift-system, there is a consistent supply of workers so that the backlog does not accumulate as in the two-shift system. However, on the one hand, it is not possible to respond to peaks of capacity demand due to rigid capacity supply. On the other hand, there are long waiting times without tasks for the workers that create periods of low worker capacity utilization. Accordingly, the rigid shift systems have clear disadvantages, which do not exist for our algorithm that supports flexible working hours and is adaptable to hourly volatile capacity demands. A detailed evaluation of the values shows that our proposed algorithm generally schedules less attendance time and the deployment intervals are better adapted to hourly volatile demands. Moreover, the rigid shift systems have both the most expensive costs in the objective function part of desired working hours of workers. Neither in the 2-shift nor in the 3-shift system, the rostering process is based on the inclusion of desired working times. The overlap between desired working times and actual working times is only by chance. The same applies to the randomly generated solutions. However, these perform significantly better in comparison; possibly, because they can also guess outside fixed shift system time grids. Our algorithm is on a similar level of costs for rostered non-desired working hours as the randomly generated solutions. Table 4 shows the applied parameter set for the evaluation process. In this experiment we used only one configuration. We have determined this parameter combination by a grid search in preliminary tests. This combination has shown good results in most experiments, although for single instances other parameter compositions can give better results. Fig. 12 shows the results of the comparison for the four selected instances. The randomly generated start population of the proposed algorithm is not yet necessarily better than the twoand three-shift operation and it takes some generations to achieve a better cost value. However, our developed algorithm achieves the best results in our test instances, provided the number of generations is high enough. The random solution generation (analogous to the start population generation) beats the rigid shift systems after a certain number of trials in three of the four cases. Table 5 shows the objective function evaluation broken down into the three main cost aspects and the penalty due to workers that have worked longer than rostered. The delay costs tend to be highest in the 2-shift system. A detailed analysis reveals that in the two-shift system, there is a backlog of manual task (and thus of jobs) at night. At the beginning of the morning shift the workers process the waiting task of the night and thus the worker capacity utilization is high. Then the Table 4: Applied parameter set for the evaluation process Parameter set of GA Parameter set of cost function Size of population Number of generations Stop after generation without min. improvement With minimal improvement [€] Tournament size Mating Probability Probability of messy crossover Probability of simulated binary crossover Eta of simulated binary crossover Mutation Probability Probability of Gaussian mutation Sigma of Gaussian mutation [minutes] Probability of mutation “inserting break” Probability of mutation “inserting interval” 100 200 100 1 5 0.8 0.5 0.5 2 0.1 0.05 120 0.05 0.05 Labor cost [€/h] Night hours [clock hours] Night work surcharge [%] Surcharge non-preferred working hours [%] Job delay cost [€/h] Penalties Unplanned work penalty [%] After-schedule work penalty [%] 25 [23, 6] 25 25 100 200 300 22 Fig. 12: Cost evaluation (fitness function including objective function and penalties) of developed algorithm in comparison to twoand three-shift system and randomly generated solutions for the test instances Table 5: Cost values of the best solution found [€] (rounded) [€] (rounded) [€] (rounded) [€] (rounded) [€] (rounded) [€] (rounded) 2-shift system Behnke & Geiger 60 8664 8651 3590 444 4617 13 Brandimarte Mk 15 7945 7541 6202 656 683 404 Dauzere 15a 4232 4127 3688 439 0 105 Fattahi 20 6675 5913 5436 477 0 762 3-shift system Behnke & Geiger 60 4341 4333 3629 446 258 8 Brandimarte Mk 15 6328 6328 5533 795 0 0 Dauzere 15a 4257 4257 3663 594 0 0 Fattahi 20 5816 5779 5116 663 0 37 By random Behnke & Geiger 60 5954 5773 2799 357 2617 181 Brandimarte Mk 15 5646 4986 4236 433 317 660 Dauzere 15a 3221 2813 2483 330 0 408 Fattahi 20 4119 3365 2992 373 0 754 Proposed algorithm Behnke & Geiger 60 2818 2801 2419 374 8 17 Brandimarte Mk 15 4907 4653 4093 560 0 254 Dauzere 15a 3057 2694 2410 284 0 363 Fattahi 20 2784 2526 2198 328 0 258 23 Workforce Rostering for Decentrally Controlled Production Systems: A Simulation-based Optimization Framework using a Genetic Algorithm for each of the four considered instances, so that on one CPU we can evaluate 20,000 individuals in a matter of minutes. There is of course potential for parallelization. Up to now, we have used parallelization only for grid search for GA parameter combinations. Accordingly, a scaling of the method to larger instances (more jobs / workers / machines) seems to be possible. However, to evaluate the method scientifically, correspondingly large benchmark instances will be needed. Detailed Example: Brandimarte Mk15 Fig. 13 displays information about the simulation run with the best individual, i.e., the best roster, found by the GA. The top chart shows the actual modes chosen for each job during the simulation and the time of their start and finish. The second chart visualizes the roster itself. It shows only the number of workers deployed at each time point. Note that the more detailed information which worker is deployed at which time can be read off the individual, see below. The third chart shows the actual time when workers were busy working. The We have set the initial time horizon for every experiment run as long as necessary so that in the best evaluation runs there are no costs for too short rosters . Accordingly, the penalty costs in Table 5 are the same as the penalty costs for unplanned working hours . A disadvantage of our algorithm in comparison to rigid shift systems is a higher expensiveness of workforce roster creation. The algorithm takes many target function evaluations (e.g., for a population size of 100 individuals evolving over 200 generations: 20,000 cost functions evaluations2). However, each cost function evaluation, which includes the simulation of the production system, takes only a fraction of a second 2Usually, in our framework, an objective function evaluation corresponds to a simulation run. However, in the optimization process of the GA, identical individuals can arise, for which we re-use the already known cost values without another simulation run. Thus, typically, the number of simulations is somewhat smaller than the number of created individuals. Fig. 13: Best solution proposal of our algorithm for test instance Brandimarte Mk15 (first four days) 24 we use well-known job shop instances which we have extended to the expected conditions since Industry 4.0. As our experiments show, the proposed algorithm achieves significantly better objective function values in comparison to ordinary two-shift and three-shift systems. We have evaluated problems with up to 60 machines, 100 jobs with 5 operations each, and 10 workers. In all our experiments we observed a convergence towards a (at least locally) optimal fitness value after approx. 80-180 generations, see Fig. 12. We did not encounter any non-linear behavior in run-time, which is plausible, given our implementation of JSP simulation and the GA. These results indicate that our heuristic approach indeed renders our optimization problem tractable. A key feature of our algorithm is that it supports the transition from rigid shift time grids towards flexible working hours. Accordingly, the supply of worker capacity (rostered attendance time) can be adjusted exactly to the capacity demands. Thus, a high working time efficiency is reached (not least against the background of sporadically occurring manual tasks in Industry 4.0). Moreover, the use of slack time with regard to delay costs helps to improve the other cost aspects (e.g., avoiding night work surcharge and employees working at undesired hours). Additionally, the developed algorithm meets the zeitgeist with regard to work-life balance as it takes into account preferred working hours of workers during the optimization process. We continue working on our framework. The main new features currently under development are the support for heterogeneous skill levels of the workers as well as for stochastic process duration and robustness for process disturbances. These topics are also of high importance as can be seen from Sect. 1.1. In the future, we would also like to solve large-scale problems in order to be able to create adequate solutions for large industrial production systems. Another open topic is synchronization of existing rosters in case of last-minute changes (e.g., sick leave) that can occur frequently in workforce management. Other useful extensions could be the assurance of minimum working hours for the workers or the detailed consideration of psychological and work science aspects. Legal aspects also need to be clarified and adapted to specific countries before using the methodology in companies. ACKNOWLEDGEMENTS We would especially like to thank the German Research Foundation / Deutsche Forschungsgemeinschaft (DFG), which is funding our project with the title “A simulation-based and flexi-time applying prediction model for scheduling personnel deployment times in the production planning process of cyber-physical systems” (project-id: 439188616). fourth chart shows the unsatisfied or open demand for workers, i.e., the number of manual tasks that are suspended for lack of available workers. The fifth chart provides more detailed information about the rostered deployment intervals for each worker as Gantt-Chart. The bottom chart shows the desired working hours of each worker per day. The solution generated by our algorithm (Fig. 13) shows that there may well be a backlog of manual task (and thus of jobs) during several hours (e.g., ca. day 1 at 6:00 p.m. until day 2 at 2:00 a.m. or day 3 at 8:00 p.m. until day 4 at 7:00 p.m.). In this example, three of four accumulated unsatisfied demand peaks are during the night. The scheduling of night work may be uninteresting for the algorithm for two reasons: The night work surcharge and penalty for undesired working hours (the desired working hours usually are during the day). It is cost efficient that the specified time window from job release to due date (and the resulting slack time) is used to improve the other two cost aspects. The algorithm seems to be able to use this effect. The second (the number of workers deployed in the roster) and third (the number of busy workers in the simulation) chart of Fig. 13 have a high coverage rate that report a high capacity utilization of the worker. In simple words: If workers have been rostered, they are usually needed for processing manual tasks in the simulation. 6 CONCLUSIONS The changed conditions related to Industry 4.0 as well as Industry 5.0 and Work 4.0 as well as the increased importance of work-life balance create a need for new methods for workforce rostering. For example, the integration of desired working hours of production employees is increasingly coming to the fore. Moreover, detailed baseline production schedules will become obsolete by the use of decentralized production control and can no longer be used as basis for conventional rostering methods. With the changed conditions in mind, we proposed a new algorithm for workforce rostering in decentrally controlled production systems taking into account the desired working hours of the workers. The schedules generated are no longer based on rigid shift systems, but take advantage of flexible working hours. The core idea of the proposed solution is a simulation-based optimization method that uses a discrete-event simulation of the execution of jobs in a given production system and a specifically tailored genetic algorithm to generate cost efficient rosters. Workforce planning problems are highly constrained due to legal requirements. We counter this fact by using specially developed repair operators that modify infeasible solutions to feasible ones. Moreover, our genetic algorithm works with a variable chromosome length since the number of decision variables may vary depending on the solution. For the evaluation,