Elsevier

Journal of Manufacturing Systems

Volume 54, January 2020, Pages 272-284
Journal of Manufacturing Systems

Technical Paper
Multiobjective scheduling algorithm for flexible manufacturing systems with Petri nets

https://doi.org/10.1016/j.jmsy.2020.01.003Get rights and content

Highlights

  • Two Petri net-based algorithms for FMS scheduling are proposed: NSGAII and WGA.

  • Both NSGA II and WGA found new best solutions on some scheduling problems.

  • The NSGA II finds better Pareto Fronts in comparison with the WGA.

  • The WGA finds better extreme solutions in comparison with the NSGA II.

  • Both NSGA II and WGA find near-optimal Pareto fronts in classical job shop problems.

Abstract

In this work, we focus on general multi-objective scheduling problems that can be modeled using a Petri net framework. Due to their generality, Petri nets are a useful abstraction that captures multiple characteristics of real-life processes.

To provide a general solution procedure for the abstraction, we propose three alternative approaches using an indirect scheme to represent the solution: (1) a genetic algorithm that combines two objectives through a weighted fitness function, (2) a non dominated sorting genetic algorithm (NSGA-II) that explicitly addresses the multi-objective nature of the problem and (3) a multi-objective local search approach that simultaneously explores multiple candidate solutions. These algorithms are tested in an extensive computational experiment showing the applicability of this general framework to obtain quality solutions.

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)

  • M.S. Nagano et al.

    A constructive heuristic for total flowtime minimization in a no-wait flowshop with sequence-dependent setup times

    J Manuf Syst

    (2015)
  • P. Renna

    Decision-making method of reconfigurable manufacturing systems’ reconfiguration by a gale-shapley model

    J Manuf Syst

    (2017)
  • S. Sadrieh et al.

    An integrated petri net and ga based approach for scheduling of hybrid plants

    Comput Ind

    (2007)
  • N. Shahsavari-Pour et al.

    A novel hybrid meta-heuristic algorithm for solving multi objective flexible job shop scheduling

    J Manuf Syst

    (2013)
  • B. Sharda et al.

    Robust manufacturing system design using multi objective genetic algorithms, petri nets and bayesian uncertainty representation

    J Manuf Syst

    (2013)
  • Y.-W. Si et al.

    A petri nets based generic genetic algorithm framework for resource optimization in business processes

    Simul Model Pract Theory

    (2018)
  • I.R. Uhlmann et al.

    Production rescheduling review: opportunities for industrial integration and practical applications

    J Manuf Syst

    (2018)
  • M. Vatani et al.

    Decomposition of first-order hybrid petri nets for hierarchical control of manufacturing systems

    J Manuf Syst

    (2015)
  • A. Zhou et al.

    Multiobjective evolutionary algorithms: a survey of the state of the art

    Swarm Evol Comput

    (2011)
  • I.B. Abdallah et al.

    Deadlock prevention and avoidance in fms: a petri net based approach

    Int J Adv Manuf Technol

    (1998)
  • D. Applegate et al.

    A computational study of the job-shop scheduling problem

    INFORMS J Comput

    (1991)
  • P. Argoneto et al.

    Supporting capacity sharing in the cloud manufacturing environment based on game theory and fuzzy logic

    Enterprise Inf Syst

    (2016)
  • O.T. Baruwa et al.

    Anytime heuristic search for scheduling flexible manufacturing systems: a timed colored petri net approach

    Int J Adv Manuf Technol

    (2014)
  • J.C. Bean

    Genetic algorithms and random keys for sequencing and optimization

    ORSA J Comput

    (1994)
  • J.E. Beasley

    Or-library: distributing test problems by electronic mail

    J Oper Res Soc

    (1990)
  • P. Brucker

    Scheduling algorithms

    (2010)
  • J.P. Caballero-Villalobos et al.

    Scheduling of complex manufacturing systems with petri nets and genetic algorithms: a case on plastic injection moulds

    Int J Adv Manuf Technol

    (2013)
  • J.-H. Chen et al.

    Petri-net and ga-based approach to modeling, scheduling, and performance evaluation for wafer fabrication

    IEEE Trans Robot Autom

    (2001)
  • X. Chen et al.

    Confusion control in generalized petri nets using synchronized events

    Math Probl Eng

    (2015)
  • T.-C. Chiang et al.

    Modeling, scheduling, and performance evaluation for wafer fabrication: a queueing colored petri-net and ga-based approach

    IEEE Trans Autom Sci Eng

    (2006)
  • Cited by (17)

    • Smart manufacturing scheduling with Petri nets

      2023, Designing Smart Manufacturing Systems
    • Bi-objective resource-constrained project scheduling problem with time-dependent resource costs

      2022, Journal of Manufacturing Systems
      Citation 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.

    • A study for further exploring the advantages of using multi-load automated guided vehicles

      2020, Journal of Manufacturing Systems
      Citation 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 Systems
      Citation 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.

    View all citing articles on Scopus
    View full text