Assessing the potential of decentralised scheduling: An experimental study for the job shop case

IFAC PapersOnLine 55-10 (2022) 2617–2622 ScienceDirect ScienceDirect Available online at www.sciencedirect.com 2405-8963 Copyright © 2022 The Authors. This is an open access article under the CC BY-NC-ND license . Peer review under responsibility of International Federation of Automatic Control. 10.1016/j.ifacol.2022.10.104 10.1016/j.ifacol.2022.10.104 2405-8963 Copyright © 2022 The Authors. This is an open access article under the CC BY-NC-ND license ( https://creativecommons.org/licenses/by-nc-nd/4.0/ ) Assessing the potential of decentralised scheduling: An experimental study for the job shop case ⋆ Jose M Framinan ∗Paz Perez-Gonzalez ∗∗ Victor Fernandez-Viagas ∗∗ Victoria Gonzalez ∗∗ ∗Industrial Management Research Group and the Laboratory of Engineering for Energy and Environmental Sustainability, Universidad de Sevilla, 41092 Seville, Spain (e-mail: [email protected]). ∗∗ Industrial Management Research Group, Universidad de Sevilla, 41092 Seville, Spain (e-mail: {pazperez,vfernandezviagas,vicgonrol}@us.es). Abstract: In this paper we investigate how decentralised scheduling approaches can be used to improve manufacturing scheduling. In view of the potential shown by some of these novel decentralised approaches, we conduct a series of experiments on a set of job shop instances subject to different degrees of variability in their processing times, and compare the performance of different scoring methods under the Contract Net Protocol proposed by Guizzi et al. (2019) with the objective of minimizing the expected makespan. We also compare the performance of the optimal (centralised and deterministic) solution in the stochastic setting, as well as a hybrid centralised-decentralised approach. Despite some limitations in the experiments, the results show the excellent performance of the decentralised approach if its operating parameters are optimized, and that the hybrid approach serves to overcome some of the problems of both centralised and decentralised approaches. Copyright ©2022 The Authors. Keywords: Job and activity scheduling, Modeling of manufacturing operations, Intelligent manufacturing systems, Multiagent systems, Modelling and decision making in complex systems. 1. INTRODUCTION Recent advances in digital technology and the deployment of new connected smart devices in the manufacturing context have provided factories with a massive amount of data and, as a consequence, a variety of unexplored possibilities during the execution of manufacturing processes. This integrated process data generated on the shop floor has become an invaluable source of information in business levels and in manufacturing optimisation tasks (Givehchi et al., 2017). Furthermore, since the advent of Industry 4.0. concepts such as Cyber-Physical Systems (CPS), the flow of information in today’s industry is not necessarily concentrated at the enterprise level. Instead, tangible assets such as machines or materials could establish a collaborative communication network in which each node can exchange operational information and act accordingly. CPS are defined as mechatronic units with computation capabilities that continuously interact in a system composed of physical ⋆This research was supported in part by Agencia Estatal de Investigaci´on (AEI)–Spain under Grant PID2019-108756RB-I00 (Project ASSORT) and in part by the Regional Council of Economy and Knowledge of Andalucia under Grants P18-FR-1149 (Project DEMAND) and AT17 5920 USE (Project IBSOS). elements (Riedl et al., 2014). In this manner, multiple CPS can exchange information and perform collaborative tasks belonging to an inter-network of physical and embedded devices, commonly referred to as the Internet of Things (IoT) (Guizzi et al., 2017). These changes have a profound reflection on the scheduling function (Rossit et al., 2019b) since, in a typical mass production case where production is stable and repeatable, there is usually enough time to create an optimized schedule with the best combination of physical assets over time. In contrast, during short series manufacturing, various changing conditions such as rapid changes in process organization or machinery adjustments could make it difficult to obtain an optimized scheduling (Cupek et al., 2016). The aforementioned manufacturing scenario has led to a growing interest in decentralised scheduling approaches where the different CPS in the shop can negotiate a feasible, efficient schedule. A pioneering work in this regard is Guizzi et al. (2019), who highlighted the promising results that can be obtained by the usage of a decentralised scheduling approach for a case of open shop scheduling. However, this work was limited to a single case study and comparisons among centralised vs decentralised scheduling methods were not conducted. Our intention in this paper is to contribute in the area of decentralised scheduling by Assessing the potential of decentralised scheduling: An experimental study for the job shop case ⋆ Jose M Framinan ∗Paz Perez-Gonzalez ∗∗ Victor Fernandez-Viagas ∗∗ Victoria Gonzalez ∗∗ ∗Industrial Management Research Group and the Laboratory of Engineering for Energy and Environmental Sustainability, Universidad de Sevilla, 41092 Seville, Spain (e-mail: [email protected]). ∗∗ Industrial Management Research Group, Universidad de Sevilla, 41092 Seville, Spain (e-mail: {pazperez,vfernandezviagas,vicgonrol}@us.es). Abstract: In this paper we investigate how decentralised scheduling approaches can be used to improve manufacturing scheduling. In view of the potential shown by some of these novel decentralised approaches, we conduct a series of experiments on a set of job shop instances subject to different degrees of variability in their processing times, and compare the performance of different scoring methods under the Contract Net Protocol proposed by Guizzi et al. (2019) with the objective of minimizing the expected makespan. We also compare the performance of the optimal (centralised and deterministic) solution in the stochastic setting, as well as a hybrid centralised-decentralised approach. Despite some limitations in the experiments, the results show the excellent performance of the decentralised approach if its operating parameters are optimized, and that the hybrid approach serves to overcome some of the problems of both centralised and decentralised approaches. Copyright ©2022 The Authors. Keywords: Job and activity scheduling, Modeling of manufacturing operations, Intelligent manufacturing systems, Multiagent systems, Modelling and decision making in complex systems. 1. INTRODUCTION Recent advances in digital technology and the deployment of new connected smart devices in the manufacturing context have provided factories with a massive amount of data and, as a consequence, a variety of unexplored possibilities during the execution of manufacturing processes. This integrated process data generated on the shop floor has become an invaluable source of information in business levels and in manufacturing optimisation tasks (Givehchi et al., 2017). Furthermore, since the advent of Industry 4.0. concepts such as Cyber-Physical Systems (CPS), the flow of information in today’s industry is not necessarily concentrated at the enterprise level. Instead, tangible assets such as machines or materials could establish a collaborative communication network in which each node can exchange operational information and act accordingly. CPS are defined as mechatronic units with computation capabilities that continuously interact in a system composed of physical ⋆This research was supported in part by Agencia Estatal de Investigaci´on (AEI)–Spain under Grant PID2019-108756RB-I00 (Project ASSORT) and in part by the Regional Council of Economy and Knowledge of Andalucia under Grants P18-FR-1149 (Project DEMAND) and AT17 5920 USE (Project IBSOS). elements (Riedl et al., 2014). In this manner, multiple CPS can exchange information and perform collaborative tasks belonging to an inter-network of physical and embedded devices, commonly referred to as the Internet of Things (IoT) (Guizzi et al., 2017). These changes have a profound reflection on the scheduling function (Rossit et al., 2019b) since, in a typical mass production case where production is stable and repeatable, there is usually enough time to create an optimized schedule with the best combination of physical assets over time. In contrast, during short series manufacturing, various changing conditions such as rapid changes in process organization or machinery adjustments could make it difficult to obtain an optimized scheduling (Cupek et al., 2016). The aforementioned manufacturing scenario has led to a growing interest in decentralised scheduling approaches where the different CPS in the shop can negotiate a feasible, efficient schedule. A pioneering work in this regard is Guizzi et al. (2019), who highlighted the promising results that can be obtained by the usage of a decentralised scheduling approach for a case of open shop scheduling. However, this work was limited to a single case study and comparisons among centralised vs decentralised scheduling methods were not conducted. Our intention in this paper is to contribute in the area of decentralised scheduling by Assessing the potential of decentralised scheduling: An experimental study for the job shop case ⋆ Jose M Framinan ∗Paz Perez-Gonzalez ∗∗ Victor Fernandez-Viagas ∗∗ Victoria Gonzalez ∗∗ ∗Industrial Management Research Group and the Laboratory of Engineering for Energy and Environmental Sustainability, Universidad de Sevilla, 41092 Seville, Spain (e-mail: fr[email protected]). ∗∗ Industrial Management Research Group, Universidad de Sevilla, 41092 Seville, Spain (e-mail: {pazperez,vfernandezviagas,vicgonrol}@us.es). Abstract: In this paper we investigate how decentralised scheduling approaches can be used to improve manufacturing scheduling. In view of the potential shown by some of these novel decentralised approaches, we conduct a series of experiments on a set of job shop instances subject to different degrees of variability in their processing times, and compare the performance of different scoring methods under the Contract Net Protocol proposed by Guizzi et al. (2019) with the objective of minimizing the expected makespan. We also compare the performance of the optimal (centralised and deterministic) solution in the stochastic setting, as well as a hybrid centralised-decentralised approach. Despite some limitations in the experiments, the results show the excellent performance of the decentralised approach if its operating parameters are optimized, and that the hybrid approach serves to overcome some of the problems of both centralised and decentralised approaches. Copyright ©2022 The Authors. Keywords: Job and activity scheduling, Modeling of manufacturing operations, Intelligent manufacturing systems, Multiagent systems, Modelling and decision making in complex systems. 1. INTRODUCTION Recent advances in digital technology and the deployment of new connected smart devices in the manufacturing context have provided factories with a massive amount of data and, as a consequence, a variety of unexplored possibilities during the execution of manufacturing processes. This integrated process data generated on the shop floor has become an invaluable source of information in business levels and in manufacturing optimisation tasks (Givehchi et al., 2017). Furthermore, since the advent of Industry 4.0. concepts such as Cyber-Physical Systems (CPS), the flow of information in today’s industry is not necessarily concentrated at the enterprise level. Instead, tangible assets such as machines or materials could establish a collaborative communication network in which each node can exchange operational information and act accordingly. CPS are defined as mechatronic units with computation capabilities that continuously interact in a system composed of physical ⋆This research was supported in part by Agencia Estatal de Investigaci´on (AEI)–Spain under Grant PID2019-108756RB-I00 (Project ASSORT) and in part by the Regional Council of Economy and Knowledge of Andalucia under Grants P18-FR-1149 (Project DEMAND) and AT17 5920 USE (Project IBSOS). elements (Riedl et al., 2014). In this manner, multiple CPS can exchange information and perform collaborative tasks belonging to an inter-network of physical and embedded devices, commonly referred to as the Internet of Things (IoT) (Guizzi et al., 2017). These changes have a profound reflection on the scheduling function (Rossit et al., 2019b) since, in a typical mass production case where production is stable and repeatable, there is usually enough time to create an optimized schedule with the best combination of physical assets over time. In contrast, during short series manufacturing, various changing conditions such as rapid changes in process organization or machinery adjustments could make it difficult to obtain an optimized scheduling (Cupek et al., 2016). The aforementioned manufacturing scenario has led to a growing interest in decentralised scheduling approaches where the different CPS in the shop can negotiate a feasible, efficient schedule. A pioneering work in this regard is Guizzi et al. (2019), who highlighted the promising results that can be obtained by the usage of a decentralised scheduling approach for a case of open shop scheduling. However, this work was limited to a single case study and comparisons among centralised vs decentralised scheduling methods were not conducted. Our intention in this paper is to contribute in the area of decentralised scheduling by Assessing the potential of decentralised scheduling: An experimental study for the job shop case ⋆ Jose M Framinan ∗Paz Perez-Gonzalez ∗∗ Victor Fernandez-Viagas ∗∗ Victoria Gonzalez ∗∗ ∗Industrial Management Research Group and the Laboratory of Engineering for Energy and Environmental Sustainability, Universidad de Sevilla, 41092 Seville, Spain (e-mail: [email protected]). ∗∗ Industrial Management Research Group, Universidad de Sevilla, 41092 Seville, Spain (e-mail: {pazperez,vfernandezviagas,vicgonrol}@us.es). Abstract: In this paper we investigate how decentralised scheduling approaches can be used to improve manufacturing scheduling. In view of the potential shown by some of these novel decentralised approaches, we conduct a series of experiments on a set of job shop instances subject to different degrees of variability in their processing times, and compare the performance of different scoring methods under the Contract Net Protocol proposed by Guizzi et al. (2019) with the objective of minimizing the expected makespan. We also compare the performance of the optimal (centralised and deterministic) solution in the stochastic setting, as well as a hybrid centralised-decentralised approach. Despite some limitations in the experiments, the results show the excellent performance of the decentralised approach if its operating parameters are optimized, and that the hybrid approach serves to overcome some of the problems of both centralised and decentralised approaches. Copyright ©2022 The Authors. Keywords: Job and activity scheduling, Modeling of manufacturing operations, Intelligent manufacturing systems, Multiagent systems, Modelling and decision making in complex systems. 1. INTRODUCTION Recent advances in digital technology and the deployment of new connected smart devices in the manufacturing context have provided factories with a massive amount of data and, as a consequence, a variety of unexplored possibilities during the execution of manufacturing processes. This integrated process data generated on the shop floor has become an invaluable source of information in business levels and in manufacturing optimisation tasks (Givehchi et al., 2017). Furthermore, since the advent of Industry 4.0. concepts such as Cyber-Physical Systems (CPS), the flow of information in today’s industry is not necessarily concentrated at the enterprise level. Instead, tangible assets such as machines or materials could establish a collaborative communication network in which each node can exchange operational information and act accordingly. CPS are defined as mechatronic units with computation capabilities that continuously interact in a system composed of physical ⋆This research was supported in part by Agencia Estatal de Investigaci´on (AEI)–Spain under Grant PID2019-108756RB-I00 (Project ASSORT) and in part by the Regional Council of Economy and Knowledge of Andalucia under Grants P18-FR-1149 (Project DEMAND) and AT17 5920 USE (Project IBSOS). elements (Riedl et al., 2014). In this manner, multiple CPS can exchange information and perform collaborative tasks belonging to an inter-network of physical and embedded devices, commonly referred to as the Internet of Things (IoT) (Guizzi et al., 2017). These changes have a profound reflection on the scheduling function (Rossit et al., 2019b) since, in a typical mass production case where production is stable and repeatable, there is usually enough time to create an optimized schedule with the best combination of physical assets over time. In contrast, during short series manufacturing, various changing conditions such as rapid changes in process organization or machinery adjustments could make it difficult to obtain an optimized scheduling (Cupek et al., 2016). The aforementioned manufacturing scenario has led to a growing interest in decentralised scheduling approaches where the different CPS in the shop can negotiate a feasible, efficient schedule. A pioneering work in this regard is Guizzi et al. (2019), who highlighted the promising results that can be obtained by the usage of a decentralised scheduling approach for a case of open shop scheduling. However, this work was limited to a single case study and comparisons among centralised vs decentralised scheduling methods were not conducted. Our intention in this paper is to contribute in the area of decentralised scheduling by 2618 Jose M Framinan et al. / IFAC PapersOnLine 55-10 (2022) 2617–2622 extending the results obtained so far into the job shop layout and by presenting a comparison with the traditional (i.e. centralised) scheduling architecture where a static (or proactive) factory-wide schedule is generated by high-level company systems. Furthermore, we explore the potential of a hybrid approach that uses a centralised static solution in addition to the decentralised approach. The remainder of the paper is as follows: in Section 2 we present the problem and the related contributions, whereas in Section 3 we detail the experimentation carried out. The results are discussed in Section 4 while the conclusions and future research lines are presented in Section 5. 2. PROBLEM DESCRIPTION AND BACKGROUND Scheduling is often cited as one of the decision-making processes that could benefit most from Industry 4.0 (Rossit et al., 2019b) since, in real-world scheduling, the data required for this decision problem is often subject to uncertainty and can change over time (Larsen and Pranzo, 2019). Although contributions in the field of scheduling in the Industry 4.0 context have the common theme of analysing how the availability of real-time, accurate data can be used to improve manufacturing scheduling decisions (Rossit et al., 2019a), these can be classified into several streams: a) work that analyses how the information obtained in an Industry 4.0 context can be used in a centralised manner e.g. to carry out a rescheduling process in order to cope with uncertainties occurring on the shop floor level, and b) work that investigates the possibilities of using these data at CPS level by conducting a decentralised scheduling via machine-to-machine interaction. Regarding the first research stream, an early reference on this topic is Sabuncuoglu and Bayiz (2000), who compare two specific predictive and reactive approaches in a dynamic deterministic job shop scheduling problem with and without machine breakdowns. Larsen and Pranzo (2019) propose a framework combining optimization to address a dynamic job shop scheduling problem. Framinan et al. (2019) investigate the appropriate triggers to conduct rescheduling in a flow shop layout where the processing times are subject to uncertainty. Similarly, Ghaleb et al. (2020) investigate the utilization of real-time data in a flexible job shop where the sources of uncertainty are given by the unexpected arrival of new jobs and the availability of the machines. Note that the aforementioned papers focus on the internal sources of variability in the shop (i.e. processing times, jobs arrivals or machine breakdowns), but not on the variability caused by upstream and downstream manufacturing processes. This aspect is addressed by Fernandez-Viagas and Framinan (2022) in the context of a flow shop layout. Despite the differences in the experimental settings among these works, a common conclusion is that 1) while there are potential benefits in using realtime information to reschedule the jobs, this strategy does not seem to convey tangible benefits if the shop floor variability is high, and 2) good (optimal or nearly-optimal) solutions for the deterministic problem perform relatively well for scenarios with limited uncertainty, a fact in line also with earlier works on stochastic scheduling such as Framinan and Perez-Gonzalez (2015). Regarding the second stream of papers, Guizzi et al. (2019) present a case study of a scheduling a small open shop using a modified Contract Net Interaction Protocol (CNP) based negotiation protocol (FIPA, 2002). The main CNP structure is shown in Figure 1, and includes four phases: (1) An initiator agent sends a CFP (Call For Proposals) to the participant agent(s) in order to request the execution of a task. (2) Each participant analyses the CFP a makes a proposal to the initiator (or refuses the CFP). (3) The initiator chooses the best offer among the proposal received, and assigns the contract to the corresponding participant. (4) The initiator rejects the rest of the proposals. In the implementation of the protocol for scheduling, two types of agents are considered, i.e. Resource Agent (representing each machine in the shop) and Job Agent (representing each job to be processed). Each machine plays the role of initiator agent, and once its state becomes “available” (i.e. the machine is idle as it has finished processing another job) sends a CFP to all “available” jobs (i.e. all jobs that are ready to be processed in this machine), which assume the role of participants in the protocol. The CFP represents indeed a service request issued by the machine indicating its availability to process one of the available jobs. If there is no available job (i.e. no job requires immediate processing in this machine), the machine waits for a fixed period of time before trying to send a new CFP. The machine then enters into a “waiting” state as it waits for the replies from the available jobs. The response (proposal) from the available jobs includes information regarding the job that is employed by the machine to choose the best offer (typically the job type to be processed and its required processing time in the machine and in the remaining machines). In the final step of the protocol, the proposals from the jobs are collected and evaluated by the machine, and the machine accepts the proposal with the highest score. In Guizzi et al. (2019), such score is a composite dispatching rule that weights three aspects, i.e. the remaining processing time of the job, the estimated processing time of the job in the machine, and the waiting time of the job before it can be processed in the machine. The protocol is implemented using Agent Based Simulation (ABS) and its performance compared with that of a similar composite dispatching rule by Nasiri et al. (2017) (see Section 3 for details on this rule) in terms of the mean waiting time of the jobs in the system and its throughput. The corresponding weights are optimised using simulationoptimization, and the results show that the FIPA-CNP protocol outperforms the approach by Nasiri et al. (2017) in terms of mean waiting time of the jobs, but not in terms of the throughput. As it can be seen from the literature background, there is an increasing interest in investigating scheduling in the Industry 4.0 context. Although a number of contributions have been produced regarding the use of information to improve rescheduling in a centralised manner and the potential of decentralised scheduling, a number of issues are still open: Fig. 1. FIPA Contract Net Interaction Protocol (FIPA, 2002) •Regarding decentralised scheduling, the potential of novel approaches such as the one by Guizzi et al. (2019) has been illustrated via one case study, but no extensive experimentation has been conducted so far using a sizeable instance test bed. Particularly, as it is well-known that different degrees of variability in the manufacturing scenario greatly impact the performance of scheduling/rescheduling methods, it would be interesting that the analysis covers different degrees of variability. Furthermore, other (composite) dispatching rules to score the proposals could be devised. •The potential of hybrid approaches (i.e. combining centralised and decentralised scheduling) has, to the best of our knowledge, not been investigated. Particularly, the integration of optimal or nearly-optimal solutions (obtained in a centralised manner) into a decentralised approach can ideally bring the best of the two worlds, as optimal deterministic scheduling has shown to perform very well in scenarios with limited variability whereas its performance quickly deteriorates as the variability increases. Our contribution is aimed towards advancing in these two areas, first by conducting a series of experiments to assess the decentralised approach by Guizzi et al. (2019), and second by incorporating in this approach hybrid rules that contain information on the optimal (centralised) solution of the (deterministic) scheduling problem. These elements are discussed in the next section. 3. METHODOLOGICAL DESIGN In our experiments, we focus on the job shop scheduling problem 1, which is both an industrially- and academicallyrelevant scheduling environment. In the classical version of the job shop scheduling problem, each one of the n job must visit all the mmachines of the shop in a jobspecific order (routing) with the objective of minimizing the maximum completion time or makespan. The problem is known to be NP-hard when there are more than 2 machines and it has attracted a great deal of researchers since its formalisation in the 50’s (Johnson, 1954). These traditional approaches for job-shop scheduling are centralised ones (Liaqait et al., 2021), but in view of its importance in the Industry 4.0 context, some authors have advocated that decentralised approaches are needed (Zhang et al., 2019). Among the classical testbeds available in the literature for job shop scheduling problems (see e.g. Adams et al., 1988; Applegate and Cook, 1991), we have chosen that from Lawrence (1984), which is the most extensive among those widely available. Since we intend to compare the solutions obtained by the different approaches with the optimal ones, we are restricted to small instances where the optimal solution can be found in reasonable time. Therefore, the instances selected are those labelled la01-la20 in the library, where machines and jobs are in the range {5× 10,10×10}. For each instance, four different scenarios with various degrees of variability in the processing times have been generated, each one assuming that pij the processing time of job jon machine ifollows a lognormal distribution with mean the processing time described in the classical instances and a coefficient of variation cv ∈{0,0.25,0.5,1}. The assumption of the lognormal distribution of the processing times has widely used in stochastic scheduling to simulate different variability scenarios (see e.g. Framinan and Perez-Gonzalez, 2015 or Framinan et al., 2019), and the range of variability of the cv has been chosen in order to capture scenarios with low, medium, and high variability according to Hopp and Spearman (2008). Note also that the variability in the processing times may serve to model different situations beyond the inherent variation of the processing times, including the possibility of breakdowns, reprocessing due to quality problems, or setups among others (see e.g. Buzacott and Shanthikumar, 1993.) For each instance and scenario, several methods have been employed to give a score of each job for the available machine, thus guiding the selection of the jobs to be scheduled in the machines. The implemented scores are the following: •The optimal solution obtained by solving the MILP formulation of the (deterministic) problem due to Manne (1960). The models have been implemented using the Python-MIP package (Python-MIP, 2022) and solved using Gurobi (Gurobi Optimization, LLC, 2022). Instead of feeding the solution to the ABS model, the optimal solution has been integrated as 1We have also conducted similar experiments on the flowshop environment using Taillard’s testbed (Taillard, 1993) but, due to space reasons, we do not include them here. In any case, the main conclusions presented in Section 5 for the job shop layout do not differ substantially from those obtained for the flowshop environment. Jose M Framinan et al. / IFAC PapersOnLine 55-10 (2022) 2617–2622 2619 Fig. 1. FIPA Contract Net Interaction Protocol (FIPA, 2002) •Regarding decentralised scheduling, the potential of novel approaches such as the one by Guizzi et al. (2019) has been illustrated via one case study, but no extensive experimentation has been conducted so far using a sizeable instance test bed. Particularly, as it is well-known that different degrees of variability in the manufacturing scenario greatly impact the performance of scheduling/rescheduling methods, it would be interesting that the analysis covers different degrees of variability. Furthermore, other (composite) dispatching rules to score the proposals could be devised. •The potential of hybrid approaches (i.e. combining centralised and decentralised scheduling) has, to the best of our knowledge, not been investigated. Particularly, the integration of optimal or nearly-optimal solutions (obtained in a centralised manner) into a decentralised approach can ideally bring the best of the two worlds, as optimal deterministic scheduling has shown to perform very well in scenarios with limited variability whereas its performance quickly deteriorates as the variability increases. Our contribution is aimed towards advancing in these two areas, first by conducting a series of experiments to assess the decentralised approach by Guizzi et al. (2019), and second by incorporating in this approach hybrid rules that contain information on the optimal (centralised) solution of the (deterministic) scheduling problem. These elements are discussed in the next section. 3. METHODOLOGICAL DESIGN In our experiments, we focus on the job shop scheduling problem 1, which is both an industrially- and academicallyrelevant scheduling environment. In the classical version of the job shop scheduling problem, each one of the n job must visit all the mmachines of the shop in a jobspecific order (routing) with the objective of minimizing the maximum completion time or makespan. The problem is known to be NP-hard when there are more than 2 machines and it has attracted a great deal of researchers since its formalisation in the 50’s (Johnson, 1954). These traditional approaches for job-shop scheduling are centralised ones (Liaqait et al., 2021), but in view of its importance in the Industry 4.0 context, some authors have advocated that decentralised approaches are needed (Zhang et al., 2019). Among the classical testbeds available in the literature for job shop scheduling problems (see e.g. Adams et al., 1988; Applegate and Cook, 1991), we have chosen that from Lawrence (1984), which is the most extensive among those widely available. Since we intend to compare the solutions obtained by the different approaches with the optimal ones, we are restricted to small instances where the optimal solution can be found in reasonable time. Therefore, the instances selected are those labelled la01-la20 in the library, where machines and jobs are in the range {5× 10,10×10}. For each instance, four different scenarios with various degrees of variability in the processing times have been generated, each one assuming that pij the processing time of job jon machine ifollows a lognormal distribution with mean the processing time described in the classical instances and a coefficient of variation cv ∈{0,0.25,0.5,1}. The assumption of the lognormal distribution of the processing times has widely used in stochastic scheduling to simulate different variability scenarios (see e.g. Framinan and Perez-Gonzalez, 2015 or Framinan et al., 2019), and the range of variability of the cv has been chosen in order to capture scenarios with low, medium, and high variability according to Hopp and Spearman (2008). Note also that the variability in the processing times may serve to model different situations beyond the inherent variation of the processing times, including the possibility of breakdowns, reprocessing due to quality problems, or setups among others (see e.g. Buzacott and Shanthikumar, 1993.) For each instance and scenario, several methods have been employed to give a score of each job for the available machine, thus guiding the selection of the jobs to be scheduled in the machines. The implemented scores are the following: •The optimal solution obtained by solving the MILP formulation of the (deterministic) problem due to Manne (1960). The models have been implemented using the Python-MIP package (Python-MIP, 2022) and solved using Gurobi (Gurobi Optimization, LLC, 2022). Instead of feeding the solution to the ABS model, the optimal solution has been integrated as 1We have also conducted similar experiments on the flowshop environment using Taillard’s testbed (Taillard, 1993) but, due to space reasons, we do not include them here. In any case, the main conclusions presented in Section 5 for the job shop layout do not differ substantially from those obtained for the flowshop environment. 2620 Jose M Framinan et al. / IFAC PapersOnLine 55-10 (2022) 2617–2622 a score rule in the CNP described in Section 2. Note that forcing the optimal solution to be strictly followed instead of using it as an indicator would imply that, if the job is not available due to the variability in the processing times, the machine has to wait instead of processing a different available job, which ultimately results in a poor performance of the schedule for non deterministic settings. As a result, each Resource agent (machine i) selects the proposal from job jthat has the highest score so ij as follows: so ij =1−Oij Ui(1) where Oij is the order in which job jis scheduled in machine iaccording to the optimal solution, while Uiis the number of unscheduled jobs in machine i at the time of the proposal. This method is labelled OPTIMAL in the following. •The composite rule proposed by Nasiri et al. (2017). According to the CNP, once machine ibecomes idle, it computes sn ij for each one of the available jobs j according to Eq. (2): sn ij =w1·Rij kpkj +w2·Kij m +w3·1−pij kpkj (2) where Rij is the remaining processing time of job jafter machine i, i.e. the sum of the processing times of the jobs in the remaining machines and Kij is the remaining number of machines for job jafter machine i. Each one of these aspects is considered in the score with a weight wi∈(0,1),i =1,2,3. This method is denoted in the following as NYJ. Note that we do not have implemented the score from Guizzi et al. (2019), since this implementation was not clear outside the open shop layout for which it was proposed. Furthermore, as already discussed in Section 2, the results obtained by this score weren’t significantly different from those by the composite rule by Nasiri et al. (2017) for the throughput indicator, which is known to be aligned with the makespan (Framinan and Leisten, 2019). Therefore, we believe that the results obtained by NYJ would be similar to those using the score by Guizzi et al. (2019). •A modification of the method by Nasiri et al. (2017) in order to take into account the remaining time of the available jobs in the remaining machines with a weight w4, see Eq. (3): sn+ ij =w1·Rij kpkj +w2·Kij m +w3·1−pij kpkj  +w4·1−pij lkpkl  (3) This score was found to yield slightly better results than the original NYJ for scenarios with low variability. It is denoted in the following as NYJ+ •A hybrid approach where the term of Eq (1) in OPTIMAL is introduced with an additional weight (w5) in Eq (3) of NYJ+, i.e.: sn+ ij =w1·Rij kpkj +w2·Kij m +w3·1−pij kpkj +w4·1−pij lkpkl  +w5·1−Oij Ui (4) In this manner, the score is composed of local (decentralised) information and of global (centralised) information provided by the optimal solution of the deterministic problem. This approach is labelled HY BRID in the following. •The FIFO (First-In-First-Out) has been also modelled. According to these rule, the jobs are scheduled in their availability order (breaking ties at random in case some of them have the same availability). This method is denoted FIFO in the following and it has been used as a reference method equivalent to not performing any (non naive) scheduling. Therefore, for each combination of scenario, instance and scoring method, an ABS model as in Guizzi et al. (2019) has been built using Anylogic®(we refer the reader to Guizzi et al., 2019 for details on the construction of the simulation model). The best combination of values of the weights of each method (note that the number of weights is method-dependent) has been obtained by using the OptQuest optimization algorithm by OptTEK®, which is included within Anylogic®. More specifically, for each combination of instance, variability scenario and ranking method, we have obtained the weights for which the best average makespan values are yielded after 500 iterations of OptQuest, each one composed of 30 replications of the experiment to reduce the variability of the simulation. For the so-obtained best combination of weights, the average makespan has been recorded. To evaluate the quality of the solutions provided by each method mwe measure the Relative Percentage Deviation (RPD) of each instance i, as defined in Eq. (5): RPDim =Cim max −Cir max Cir max ·100 (5) where Cim max is the makespan obtained by solving instance iusing method m, and Cir max is a reference value for the makespan in instance i. These results will be presented in an aggregated manner (ARPD or Average RPD) across the 20 instances. Regarding the reference value, we have at least two options: On the one hand, we can use the optimal solution found by the MILP model assuming fully deterministic processing times, or we can use the minimum value of the makespan obtained for instance iamong the set of methods tested for a given cv. The experiments carried out show that, although the ARPD values are quite different, the conclusions presented in Section 5 are essentially the same, henceforth we solely present the results using the optimal solution, which will allow us also to compare the solutions obtained for different cvs. Fig. 2. Evolution of the different methods with cv 4. RESULTS The aggregate results of the experiments presented in Section 3 are summarised in Table 1 and in Figure 2, the latter with the exception of FIFO due to its relatively bad performance. Although we here only present the aggregate results, these are rather homogeneous across the instances considered in the testbed. In view of the results, the following comments can be done: •The results across the different cv speak for the substantial differences between conducting some type of scheduling as compared to not scheduling at all (i.e. using the FIFO rule as scheduling method). •As a whole, the decentralised approaches can be considered to yield competitive results, as they obtain very good solutions when compared with the optimal solution for the deterministic case. Note however that this excellent performance has been obtained after a process of optimizing the weights for each instance and therefore, these are not comparable to that of some centralised, sophisticated approximate methods for job shop scheduling that are instanceindependent. •As a rule, using the optimal solution to guide the CNP (i.e. OPTIMAL) yields better results for scenario with limited variability whereas the opposite occurs for the scenarios with higher variability. This result is foreseeable and in line with existing literature on the topic. •NYJ+ obtains slightly better results than NYJ, which speaks for the interest in developing more complex scoring methods, particularly if different sources of uncertainty are considered. •The hybrid score seems to be a suitable manner to establish a trade-off between the different performance of NYJ+ (which improves as cv increases) and OP T IMAL (which deteriorates as cv increases), Table 1. Aggregate results (ARPD) Coefficient of variation 0 0.25 0.5 1 Average FIFO 20.517 20.549 23.990 33.888 24.736 NYJ 3.390 4.792 9.121 19.718 9.255 NYJ+ 3.237 4.461 8.818 19.702 9.054 OPTIMAL 0.000 4.067 9.445 21.880 8.848 HYBRID 1.872 4.067 8.669 20.115 8.680 yielding the best or close-second best results across all the scenarios. 5. CONCLUSIONS AND FUTURE RESEARCH In this paper we have conducted a series of experiments aimed at assessing the potential of decentralised scheduling approaches in the job shop setting. A set of instances and scenarios characterised by different degrees of variability in the processing times have been modelled, and several methods to score the jobs in the CNP protocol by Guizzi et al. (2019) have been tested. The weights of these scoring methods have been optimized so the best possible combination of weights has been obtained. Despite the limitations in the experiments, in view of the results, the following conclusions and suggestions for future research can be done: •In relative terms, finding a good schedule becomes more important with the variability of the scenario, as the deviation with respect to the best possible (deterministic) solution increases with the cv.Itwouldbe of interest to extend the experimentation to a wider range of instances and scenarios to generalise this conclusion. •The incorporation of the optimal (deterministic) solution as a part of the decentralised rules (HY BRID approach) seem to yield overall excellent results, outperforming the rest of the decentralised rules for scenarios with low variability, and performing similarly to them (or even slightly better) for scenarios with higher variability. Of course, for big instances it might be not possible to obtain the optimal solution, so an interesting opportunity would be to investigate if fast (although approximate) procedures also serve to obtain similar results to the ones obtained with the optimal solution. •The experiments reveal that there is a high potential in the usage of decentralised scheduling methods, at least as long as the weights of these methods are optimised. This fact opens several avenues worth of future research, including the following: ·To analyse the sensitivity of the rules to the weights of these methods, as –at least in theory– it could be possible to obtain a good performance without customising the weights for the instances. In this regard, it could be perhaps interesting to review sophisticated, high-performing dispatching rules and try to integrate them into decentralised approaches. This is a key issue to advance in the goal of implementing decentralised scheduling in a real industrial context. ·Self-tuning of the parameters. Other elements present in Industry 4.0 such as the usage of Artificial Intelligence (AI), Machine Learning (ML) or Digital Twins among others, could be integrated into a framework where scheduling in the physical system is guided by the results obtained by optimizing the parameters of the CNP in its corresponding digital twin, possibly reducing the simulation effort by the smart use of low-fidelity models to discard non promising solutions, or ML tools to provide accurate estimates of the simulation results. Jose M Framinan et al. / IFAC PapersOnLine 55-10 (2022) 2617–2622 2621 Fig. 2. Evolution of the different methods with cv 4. RESULTS The aggregate results of the experiments presented in Section 3 are summarised in Table 1 and in Figure 2, the latter with the exception of FIFO due to its relatively bad performance. Although we here only present the aggregate results, these are rather homogeneous across the instances considered in the testbed. In view of the results, the following comments can be done: •The results across the different cv speak for the substantial differences between conducting some type of scheduling as compared to not scheduling at all (i.e. using the FIFO rule as scheduling method). •As a whole, the decentralised approaches can be considered to yield competitive results, as they obtain very good solutions when compared with the optimal solution for the deterministic case. Note however that this excellent performance has been obtained after a process of optimizing the weights for each instance and therefore, these are not comparable to that of some centralised, sophisticated approximate methods for job shop scheduling that are instanceindependent. •As a rule, using the optimal solution to guide the CNP (i.e. OPTIMAL) yields better results for scenario with limited variability whereas the opposite occurs for the scenarios with higher variability. This result is foreseeable and in line with existing literature on the topic. •NYJ+ obtains slightly better results than NYJ, which speaks for the interest in developing more complex scoring methods, particularly if different sources of uncertainty are considered. •The hybrid score seems to be a suitable manner to establish a trade-off between the different performance of NYJ+ (which improves as cv increases) and OP T IMAL (which deteriorates as cv increases), Table 1. Aggregate results (ARPD) Coefficient of variation 0 0.25 0.5 1 Average FIFO 20.517 20.549 23.990 33.888 24.736 NYJ 3.390 4.792 9.121 19.718 9.255 NYJ+ 3.237 4.461 8.818 19.702 9.054 OPTIMAL 0.000 4.067 9.445 21.880 8.848 HYBRID 1.872 4.067 8.669 20.115 8.680 yielding the best or close-second best results across all the scenarios. 5. CONCLUSIONS AND FUTURE RESEARCH In this paper we have conducted a series of experiments aimed at assessing the potential of decentralised scheduling approaches in the job shop setting. A set of instances and scenarios characterised by different degrees of variability in the processing times have been modelled, and several methods to score the jobs in the CNP protocol by Guizzi et al. (2019) have been tested. The weights of these scoring methods have been optimized so the best possible combination of weights has been obtained. Despite the limitations in the experiments, in view of the results, the following conclusions and suggestions for future research can be done: •In relative terms, finding a good schedule becomes more important with the variability of the scenario, as the deviation with respect to the best possible (deterministic) solution increases with the cv.Itwouldbe of interest to extend the experimentation to a wider range of instances and scenarios to generalise this conclusion. •The incorporation of the optimal (deterministic) solution as a part of the decentralised rules (HY BRID approach) seem to yield overall excellent results, outperforming the rest of the decentralised rules for scenarios with low variability, and performing similarly to them (or even slightly better) for scenarios with higher variability. Of course, for big instances it might be not possible to obtain the optimal solution, so an interesting opportunity would be to investigate if fast (although approximate) procedures also serve to obtain similar results to the ones obtained with the optimal solution. •The experiments reveal that there is a high potential in the usage of decentralised scheduling methods, at least as long as the weights of these methods are optimised. This fact opens several avenues worth of future research, including the following: ·To analyse the sensitivity of the rules to the weights of these methods, as –at least in theory– it could be possible to obtain a good performance without customising the weights for the instances. In this regard, it could be perhaps interesting to review sophisticated, high-performing dispatching rules and try to integrate them into decentralised approaches. This is a key issue to advance in the goal of implementing decentralised scheduling in a real industrial context. ·Self-tuning of the parameters. Other elements present in Industry 4.0 such as the usage of Artificial Intelligence (AI), Machine Learning (ML) or Digital Twins among others, could be integrated into a framework where scheduling in the physical system is guided by the results obtained by optimizing the parameters of the CNP in its corresponding digital twin, possibly reducing the simulation effort by the smart use of low-fidelity models to discard non promising solutions, or ML tools to provide accurate estimates of the simulation results. 2622 Jose M Framinan et al. / IFAC PapersOnLine 55-10 (2022) 2617–2622 ·In view of the promising results obtained by the hybrid approach, it would be perhaps interesting to extend the CNP to make it less greedy (i.e. locally-centered) and to integrate another machines in the negotiation protocol. •It has to be noted that the analysis carried out does not include the comparison of the decentralised approaches with centralised proactive-reactive ones (i.e. robust scheduling, rescheduling or smart scheduling, see Rossit et al., 2019c), which are known to be efficient under certain circumstances. This also constitutes another interesting research avenue. ACKNOWLEDGEMENTS The authors of the paper would like to thank Miguel Navas, who worked for the IBSOS project under Grant AT17 5920 USE for his help in the research. REFERENCES Adams, J., Balas, E., and Zawack, D. (1988). Shifting bottleneck procedure for job shop scheduling. Management Science, 34(3), 391–401. Applegate, D. and Cook, W. (1991). Computational study of the job-shop scheduling problem. ORSA journal on computing, 3(2), 149–156. Buzacott, J. and Shanthikumar, J. (1993). Stochastic Models of Manufacturing Systems. Prentice-Hall international series in industrial and systems engineering. Prentice Hall. Cupek, R., Ziebinski, A., Huczala, L., and Erdogan, H. (2016). Agent-based manufacturing execution systems for short-series production scheduling. Computers in Industry, 82, 245 – 258. Fernandez-Viagas, V. and Framinan, J. (2022). Exploring the benefits of scheduling with advanced and real-time information integration in industry 4.0: A computational study. Journal of Industrial Information Integration. FIPA (2002). Contract net interaction protocol specification. URL http://www.fipa.org/specs/fipa00029/SC00029H.html. Framinan, J., Fernandez-Viagas, V., and Perez-Gonzalez, P. (2019). Using real-time information to reschedule jobs in a flowshop with variable processing times. Computers and Industrial Engineering, 129, 113–125. Framinan, J. and Leisten, R. (2019). Linking scheduling criteria to shop floor performance in permutation flowshops. Algorithms, 12(2). Framinan, J. and Perez-Gonzalez, P. (2015). On heuristic solutions for the stochastic flow shop scheduling problem. European Journal of Operational Research, 246(2), 413 – 420. Ghaleb, M., Zolfagharinia, H., and Taghipour, S. (2020). Real-time production scheduling in the industry-4.0 context: Addressing uncertainties in job arrivals and machine breakdowns. Computers and Operations Research, 123. Givehchi, O., Landsdorf, K., Simoens, P., and A. W., C. (2017). Interoperability for industrial cyber-physical systems: An approach for legacy systems. IEEE Transactions on Industrial Informatics, 13(2), 3370–3378. Guizzi, G., Revetria, R., Vanacore, G., and Vespoli, S. (2019). On the open job-shop scheduling problem: a decentralized multi-agent approach for the manufacturing system performance optimization. Procedia CIRP, 79, 192 – 197. Guizzi, G., Vespoli, S., and Santini, S. (2017). On the architecture scheduling problem of industry 4.0. CIISE. doi:http://ceur-ws.org/Vol-2010/paper13.pdf. Gurobi Optimization, LLC (2022). Gurobi Optimizer Reference Manual. URL https://www.gurobi.com. Hopp, W. and Spearman, M. (2008). Factory physics (3rded.). Waveland Press, Chicago. Johnson, S.M. (1954). Optimal two- and three-stage production schedules with setup times included. Naval Research Logistics Quarterly, 1(1), 61–68. Larsen, R. and Pranzo, M. (2019). A framework for dynamic rescheduling problems. International Journal of Production Research, 57(1), 16–33. Lawrence, S. (1984). Resource constrained project scheduling: An experimental investigation of heuristic scheduling techniques (supplement). Technical report, Graduate School of Industrial Administration,Carnegie- Mellon University, Pittsburgh, Pennsylvania. Liaqait, R.A., Hamid, S., Warsi, S.S., and Khalid, A. (2021). A critical analysis of job shop scheduling in context of industry 4.0. Sustainability, 13(14). Manne, A.S. (1960). On the job-shop scheduling problem. Operations Research, 8(2), 219–223. Nasiri, M., Yazdanparast, R., and Jolai, F. (2017). A simulation optimisation approach for real-time scheduling in an open shop environment using a composite dispatching rule. International Journal of Computer Integrated Manufacturing, 30, 1239 – 1252. Python-MIP (2022). Python-MIP Home Page. URL https://www.python-mip.com/. Riedl, M., Zipper, H., Meier, M., and Diedrich, C. (2014). Cyber-physical systems alter automation architectures. Annual Reviews in Control, 38(1), 123–133. Rossit, D., Tohm´e, F., and Frutos, M. (2019a). A datadriven scheduling approach to smart manufacturing. Journal of Industrial Information Integration, 15, 69– 79. Rossit, D., Tohm´e, F., and Frutos, M. (2019b). Production planning and scheduling in cyber-physical production systems: a review. International Journal of Computer Integrated Manufacturing, 32(4-5), 385–395. Rossit, D.A., Tohm´e, F., and Frutos, M. (2019c). Industry 4.0: Smart scheduling. International Journal of Production Research, 57(12), 3802–3813. Sabuncuoglu, I. and Bayiz, M. (2000). Analysis of reactive scheduling problems in a job shop environment. European Journal of Operational Research, 126(3), 567–586. Taillard, E. (1993). Benchmarks for basic scheduling problems. European Journal of Operational Research, 64(2), 278 – 285. Zhang, J., Ding, G., Zou, Y., Qin, S., and Fu, J. (2019). Review of job shop scheduling research and its new perspectives under industry 4.0. Journal of Intelligent Manufacturing, 30(4), 1809–1830.