Technical PaperMultiobjective scheduling algorithm for flexible manufacturing systems with Petri nets
Introduction
Scheduling ranks among the most important activities for the proper management and control of manufacturing systems. Its goals are to establish the timing of the tasks execution and to allocate resources to perform these tasks accordingly. Given the generality of the scheduling activity, its use has not been limited to only production settings but has also become an integral part of many other activities. Consequently, scheduling problems have been widely considered in the scientific literature. Moreover, due to their intrinsic combinatorial nature, the majority of scheduling problems are considered to be difficult to solve and require special solution methods.
Most of the literature focuses on the study of very specific systems and with problem formulations under a single decision criterion [8], e.g., the flow shop and the job shop scheduling problem under the makespan minimization objective as well as variants of the above models [45], [52], but alternatives exist, like multi-criteria decision-making methods [48], multi-objective optimization approaches [37], game-theoretic frameworks [3], [58]. This work takes an alternative and innovative approach and puts forward a general modeling framework based on the Petri net paradigm for scheduling problems under a multi-objective optimization approach.
Broadly, a Petri net is a compact representation of the system under study, the scheduling environment, and of each of its possible states including its initial and a possible final state [53], [56]. This representation, together with a set of rules to describe transformations between states, denoted as transition firings, provides a general formalism in which a schedule corresponds to an ordered set of transition firings that transform the initial state into the final state.
Due to its generality, the Petri net formalism can be used to accurately model different manufacturing settings such as parallel machines, buffers of finite capacity, dual resources (multiple resources that are required simultaneously on one operation), alternative routings, and material handling devices, to name a few. In addition to their modeling capabilities, Petri nets can be used to simulate the operation of the real system and/or to evaluate the scheduling decisions.
The performance of these scheduling decisions is evaluated using some metric, i.e., an objective function, such as makespan minimization, which is the total amount of time required to perform all tasks. Nonetheless, manufacturing firms commonly face additional performance criteria such as meeting deadlines, minimizing work-in-progress or reducing energy consumption. To address these objectives simultaneously, some trade-offs must be attained. Pareto-based approaches provide the means to identify such trade-offs and single out a subset of attractive, i.e., efficient, solutions. This efficient subset corresponds to non-dominated schedules, i.e., solutions in which improvements in one of the objectives imply a deterioration of at least one of the other objectives, from which the decision-makers select a schedule according to their preferences.
In this paper, we propose several algorithms to solve multi-objective scheduling problems that have been modeled through a Petri net. Our objective is two-fold. First, we analyze the capability of Petri nets to offer a convenient framework to model multi-objective scheduling problems and, second; we consider the applicability of general-purpose multi-objective optimization methods for it. We now review related work on Petri-net based scheduling.
Petri nets have been a popular approach to optimize the performance of many manufacturing systems. Petri net-based scheduling works have studied flexible manufacturing systems (FMS), [5], [33], [42], [49], flexible assembly systems (FAS) [25], [40], [42], resource constrained project (RCPSP) [43], [47], [59], flexible flow (FFSSP) and flexible job shop (FJSSP) [44], and re-entrant manufacturing [10], [31] scheduling problems. Scheduling within the Petri net modeling framework has been combined with several optimization approaches. The most prevalent in the literature have been priority rules [44], graph search methods [4], [28], [33], [42], and metaheuristics [9], [26], [57].
Priority rules [44] are simple conflict resolution rules that select one transition to fire among the enabled transitions in a given state. Graph search methods are by far the most popular [5], [33], [42], [49]. Essentially, these methods expand the nodes of the Petri net search space using an evaluation function, typically a local lower bound, which essentially prioritizes the node selection [44]. Despite their popularity, graph search methods present some disadvantages such as (1) the state explosion, (2) the difficulties in computing good evaluation functions and, (3) the limited capability to handle multi-objective criteria.
Metaheuristics in combination with Petri nets for scheduling have also been proposed. For example, genetic algorithms (GA) [9], [13], [47], [54], [57], particle swarm optimization (PSO) [26], [59], hybrid differential evolution (HDE) [34], ant colony optimization (ACO) [38], and local search-based (LS) approaches [39]. Unlike graph search methods, which generally use the same algorithmic structure, metaheuristics exhibit many variants in terms of the solution representation (encoding) and the decoding method. The encoding can be seen as a list of attributes (genes in a genetic algorithm) that map to a solution (i.e., the schedule). The decoding is the procedure that transforms the encoding into a solution and evaluates its performance. In terms of Petri nets, different encodings have been proposed and can be classified as problem-based or transition selection-based encodings.
In a problem-based encoding, each gene corresponds to an element of the problem. Examples of elements in scheduling are jobs, routes, machines or combinations of such elements. The encoding must be able to encode a schedule in such a way that whenever some ith decision is made, the element encoded in the ith gene maps to a unique transition to fire. In a transition-selection encoding, genes correspond to a priority associated with each specific transition. Consequently, whenever a scheduling decision is made, the decoding operation selects among the enabled transitions the one with the highest priority (e.g., lowest gene value) and fires it. This type of indirect encoding scheme is common in many other environments, and it is also known as a random-key encoding [6], [23].
In terms of objective functions, the vast majority of works (examples are [25], [26], [36], [40], [41], [59]) minimize makespan. Other works address total weighted tardiness [9], idle time [24] and weighted objective functions [12], [51], [54] that include measures of time and cost.
Please note that few works have considered multiple objectives within a Petri net framework [10], [13], [51], [54]. These works have focused on the use of weighted objective functions in which the objectives are combined into a single objective through some weights that define the priority of each objective in the overall quality of a solution (a schedule). Table 1 summarizes the approaches of Petri nets in combination with a metaheuristic for scheduling problems. Our work is the first to consider a multi-objective evolutionary algorithm in which each of the objectives are independently considered.
In this work, we propose a novel approach for general multi-objective scheduling problems. This approach makes use of three major building blocks: (1) the Petri net formalism to model scheduling problems; (2) Pareto efficiency to tackle the intrinsic multi-criteria decision-making nature of the problem; and (3) different multi-objective combinatorial optimization methods that explore the space of feasible solutions through an indirect representation. The results of the proposed approach are then tested in extensive experiments with both new and classical instances from the literature. The results show that the method is able to provide quality efficiency fronts with reduced computing times.
The remainder of this paper is organized as follows: Section 2 describes Petri nets, their notation and their application to model flexible manufacturing systems as well as a description of multi-objective optimization. Section 3 details three different procedures to solve the problem in hand, namely: (1) a single-objective genetic algorithm that combines multiple objectives using a weighted objective function [15], (2) a multi-objective local search [18] procedure and (3) a multi-objective genetic algorithm [16]. Computational experiments with these procedures are described in Section 4, and conclusions and future lines of work are discussed in Section 5.
Section snippets
Petri nets
A Petri net is a directed, weighted, bipartite graph with two kinds of nodes, called places and transitions. Arcs are directed either from a place to a transition or from a transition to a place. Usually, places represent actions or conditions and transitions represent events. Tokens (represented by black dots) reside in places and represent the truth of the condition associated with the corresponding place. A place containing at least one token is denoted as a marked place.
In this paper, we
Proposed approach
This section describes three different algorithms to solve the problems discussed in Section 2. As all of the proposed algorithms make use of the same representation (referred to as “chromosome” from here on), decoding scheme, neighborhoods and local search, Section 3.1 introduces these common aspects for all the proposed algorithms. After introducing the common components, Section 3.2 describes a genetic algorithm (GA) that uses a weighted objective function weighting the different objectives
Implementation details and description of instances
To test the algorithms described in Section 3, they were implemented in Java, compiled using Java 8. The experiments were run in a cluster of Intel Xeon processors with 32 2.0 GHz processors and 128 GB of RAM, running the Linux operating system. The code does not make use of any parallelism and the multiple cores are used to simultaneously execute the code on multiple instances (and thus, we can consider that the code is executed in a single-core CPU with 4 GB of RAM).
The proposed methods with
Conclusions and future research
In this work, we propose two multi-objective algorithms for a broad class of scheduling problems in manufacturing systems. This generic class of scheduling problems includes alternative routings, batch sizes and non-identical parallel machines. flexible job shop and flow shop scheduling problems are special cases of such problems. These problems are modeled with a Petri net framework. To account for the different criteria commonly found in real life conditions, a multi-objective
Aknowledgements
The authors would like to thank Diego Vásquez, alumni of the M.Sc. program in Industrial Engineering of the Pontificia Universidad Católica de Valparaíso (Chile) for his valuable help. J. Pereira also acknowledges the support of the National Commission for Scientific and Technological Research, CONICYT, through the grant FONDECYT N. 1191624 “Assembly line balancing for industry 4.0”. Also, the authors want to express their gratitude to the anonymous reviewers for their suggestions. The final
References (60)
- et al.
Identifying fms repetitive patterns for efficient search-based scheduling algorithm: a colored petri net approach
J Manuf Syst
(2015) - et al.
A hybrid tp+pls algorithm for bi-objective flow-shop scheduling problems
Comput Oper Res
(2011) - et al.
Resource assignment and scheduling based on a two-phase metaheuristic for cropping system
Comput Electron Agric
(2009) - et al.
Mixed integer programming models for job shop scheduling: a computational analysis
Comput Oper Res
(2016) - et al.
Hybrid heuristic search approach for deadlock-free scheduling of flexible manufacturing systems using petri nets
Appl Soft Comput
(2017) - et al.
Deadlock-free scheduling for flexible manufacturing systems using petri nets and heuristic search
Comput Ind Eng
(2014) - et al.
Bi-objective optimization for a multistate job-shop production network using nsga-ii and topsis
J Manuf Syst
(2019) - et al.
A new hybrid filtered beam search algorithm for deadlock-free scheduling of flexible manufacturing systems using petri nets
Comput Ind Eng
(2017) - et al.
A petri net-based framework for realistic project management and scheduling: an application in animation and videogames
Comput Oper Res
(2016) - et al.
An approach using petri nets and improved heuristic search for manufacturing system scheduling
J Manuf Syst
(2005)
A constructive heuristic for total flowtime minimization in a no-wait flowshop with sequence-dependent setup times
J Manuf Syst
Decision-making method of reconfigurable manufacturing systems’ reconfiguration by a gale-shapley model
J Manuf Syst
An integrated petri net and ga based approach for scheduling of hybrid plants
Comput Ind
A novel hybrid meta-heuristic algorithm for solving multi objective flexible job shop scheduling
J Manuf Syst
Robust manufacturing system design using multi objective genetic algorithms, petri nets and bayesian uncertainty representation
J Manuf Syst
A petri nets based generic genetic algorithm framework for resource optimization in business processes
Simul Model Pract Theory
Production rescheduling review: opportunities for industrial integration and practical applications
J Manuf Syst
Decomposition of first-order hybrid petri nets for hierarchical control of manufacturing systems
J Manuf Syst
Multiobjective evolutionary algorithms: a survey of the state of the art
Swarm Evol Comput
Deadlock prevention and avoidance in fms: a petri net based approach
Int J Adv Manuf Technol
A computational study of the job-shop scheduling problem
INFORMS J Comput
Supporting capacity sharing in the cloud manufacturing environment based on game theory and fuzzy logic
Enterprise Inf Syst
Anytime heuristic search for scheduling flexible manufacturing systems: a timed colored petri net approach
Int J Adv Manuf Technol
Genetic algorithms and random keys for sequencing and optimization
ORSA J Comput
Or-library: distributing test problems by electronic mail
J Oper Res Soc
Scheduling algorithms
Scheduling of complex manufacturing systems with petri nets and genetic algorithms: a case on plastic injection moulds
Int J Adv Manuf Technol
Petri-net and ga-based approach to modeling, scheduling, and performance evaluation for wafer fabrication
IEEE Trans Robot Autom
Confusion control in generalized petri nets using synchronized events
Math Probl Eng
Modeling, scheduling, and performance evaluation for wafer fabrication: a queueing colored petri-net and ga-based approach
IEEE Trans Autom Sci Eng
Cited by (17)
Smart manufacturing scheduling with Petri nets
2023, Designing Smart Manufacturing SystemsBi-objective resource-constrained project scheduling problem with time-dependent resource costs
2022, Journal of Manufacturing SystemsCitation Excerpt :What is more, all these costs may be affected by an annual increase induced by the consumer price index. Above all, by capturing more realistic settings, it is possible to develop more adequate tools of great relevance in the context of smart manufacturing in general [46] and in the context of scheduling activities in manufacturing systems in particular [37]. The goal for the bi-objective problem we investigate in this work is to find the Pareto front, i.e., the entire set of solutions that cannot be improved in terms of one objective without deteriorating the other.
Multi-objective scheduling in labor-intensive manufacturing systems
2020, Journal of Manufacturing SystemsA study for further exploring the advantages of using multi-load automated guided vehicles
2020, Journal of Manufacturing SystemsCitation Excerpt :The CPN modelling method is briefly introduced in Section 2; the layout of the AGV system considered is described in Section 3; three types of CPN models are developed in Section 4 which take into account the number and load capacity of AGVs, mission allocation, routing problem, and conflict avoidance; the simulation calculations and discussion are conducted in Section 5; the paper ends with the key research conclusions in Section 6. PN provides an intuitive graphical representation of a system and their flexibility enables modifications in design, operation & maintenance of a system to be easily incorporated [27–29]. As shown in Fig. 1, a PN is a direct bipartite graph, which consists of four types of symbols, i.e. circles, rectangles, arrows, and tokens.
A survey on decision-making based on system reliability in the context of Industry 4.0
2020, Journal of Manufacturing SystemsCitation Excerpt :These methods provide a comprehensive analysis of the manufacturing system. However, they end up being complicated or inconvenient, considering that it depends on the prior analysis of the subsystem and equipment reliability individually [55,72,91] The introduction of technology to efficiently check the condition of the equipment is today one of the most relevant maintenance tools, contributing to improvements in predictive models.
Optimization of Workpiece Maintenance Discipline through Simulation Modeling of the Functioning of Automated Technological Complexes
2023, Journal of Machinery Manufacture and Reliability