This paper proposes an effective hybrid discrete differential evolution (DDE) algorithm for solving a scheduling problem of flexible manufacturing systems (FMSs), where sequence-dependent setup times are considered. The objective is to find a deadlock-free schedule that minimizes the makespan. Based on the timed Petri net models of FMSs, a possible solution of the scheduling problem is represented as an individual that is a permutation with repetition of jobs. For the existence of deadlocks, most of the individuals cannot be directly decoded into feasible (live) schedules. Therefore, a deadlock controller is applied in the decoding scheme, and infeasible individuals are amended into feasible ones. Moreover, in order to overcome the premature convergence of DDE algorithm and improve solution quality, a variable neighbourhood search algorithm, which performs a systematic change of neighbourhood in solution searching, is adopted. Then a hybrid scheduling algorithm that combines a DDE with a variable neighbourhood search is presented. Computational results and comparison based on a variety of instances show the feasibility and superiority of the proposed algorithm.
AbdallahIBElmaraghyHAElmekkawyT (2002) Deadlock-free scheduling in flexible manufacturing system using Petri nets. International Journal of Production Research40(12): 2733–2756.
2.
AllahverdiANgCChengTCE. (2008) A survey of scheduling problems with setup times or costs. European Journal of Operational Research187(3): 985–1032.
3.
BanaszakZAKroghBH (1990) Deadlock avoidance in flexible manufacturing systems with concurrently competing process flows. IEEE Transaction on Robotics and Automation6(6): 724–734.
4.
BaruwaOTPieraMAGuaschA (2015) Deadlock-free scheduling method for flexible manufacturing systems based on timed colored Petri nets and anytime heuristic search. IEEE Transactions on Systems, Man, Cybernetics, Part A: Systems and Humans45(5): 831–846.
5.
ChuFXieXL (1997) Deadlock analysis of Petri nets using siphons and mathematical programming. IEEE Transaction on Robotics and Automation13(6): 793–804.
6.
ElMekkawyTYElMaraghyHA (2003) Real-time scheduling with deadlock avoidance in flexible manufacturing systems. The International Journal of Advanced Manufacturing Technology22(3−4): 259–270.
7.
EzpeletaJColomJMMartinezJ (1995) A Petri net-based deadlock prevention policy for flexible manufacturing systems. IEEE Transaction on Robotics and Automation11(2): 173–184.
8.
HanLBXingKYChenX. (2014) Deadlock-free genetic scheduling for flexible manufacturing systems using Petri nets and deadlock controllers. International Journal of Production Research52(5): 1557–1572.
9.
HuangYSJengMDXieXL. (2001) Deadlock prevention policy based on Petri nets and siphons. International Journal of Production Research39(2): 283–305.
10.
JengMD (1997) A Petri net synthesis theory for modeling flexible manufacturing systems. IEEE Transaction on System, Man, and Cybernetics, Part B: Cybernetics27(2): 169–183.
11.
JengMDChenSC (1998) A heuristic search approach using approximate solutions to Petri net state equations for scheduling flexible manufacturing systems. International Journal of Flexible Manufacturing Systems10(2): 139–162.
12.
KumaranTKChangWChoH. (1994) A structured approach to deadlock detection, avoidance and resolution in flexible manufacturing systems. International Journal of Production Research32(10): 2361–2379.
13.
LeeDYDiCesareF (1994) Scheduling flexible manufacturing systems using Petri nets and heuristic search. IEEE Transaction on Robotics and Automation10(2): 123–132.
14.
LiZWZhouMC (2004) Elementary siphons of Petri nets and their application to deadlock prevention in flexible manufacturing systems. IEEE Transactions on Systems, Man, Cybernetics, Part A: Systems and Humans34(1): 38–51.
15.
LuoJCXingKYZhouMC. (2015) Deadlock-free scheduling of automated manufacturing systems using Petri nets and hybrid heuristic search. IEEE Transactions on Systems, Man, Cybernetics, Part A: Systems and Humans45(3): 530–541.
NaderiBZandiehMRoshanaeiV (2009) Scheduling hybrid flowshops with sequence-dependent setup times to minimize makespan and maximum tardiness. The International Journal of Advanced Manufacturing Technology41(11–12): 1186–1198.
18.
NazeemAReveliotisSWangY. (2011) Designing compact and maximally permissive deadlock avoidance policies for complex resource allocation systems through classification theory: the linear case. IEEE Transaction on Automatic Control56(8): 1818–1833.
19.
PinedoML (2008) Scheduling: Theory, Algorithms, and Systems (3rd ed.). New York: Springer.
20.
PiroddiLCordoneRFumagalliI (2008) Selective siphon control for deadlock prevention in Petri nets. IEEE Transactions on Systems, Man, Cybernetics, Part A: Systems and Humans38(6): 1337–1348.
21.
RamaswamySEJoshiSB (1996) Deadlock-free schedules for automated manufacturing workstations. IEEE Transaction on Robotics and Automation12(3): 391–400.
22.
ReveliotisSAFerreiraPM (1996) Deadlock avoidance policies for automated manufacturing cells. IEEE Transaction on Robotics and Automation12(6): 845–857.
23.
ReveliotisSALawleyMAFerreiraPM (1997) Polynomial-complexity deadlock avoidance policies for sequential resource allocation systems. IEEE Transaction on Automatic Control42(10): 1344–1357.
24.
RuizRStützleT (2008) An iterated greedy heuristic for the sequence-dependent setup times flowshop problem with makespan and weighted tardiness objectives. European Journal of Operational Research187(3): 1143–1159.
25.
StornRPriceK (1997) Differential evolution – a simple and efficient adaptive scheme for global optimization over continuous spaces. Journal of Global Optimization11(4): 341–359.
26.
WuNQZhouMC (2007a) Deadlock resolution in automated manufacturing systems with robots. IEEE Transaction on Automation Science and Engineering4(3): 474–480.
27.
WyskRAYangNSJoshiS (1991) Detection of deadlocks in flexible manufacturing cells. IEEE Transaction on Robotics and Automation7(6): 853–859.
28.
XingKYHuBSChenHX (1996) Deadlock avoidance policy for Petri net modeling of flexible manufacturing systems with shared resources. IEEE Transaction on Automation Control41(2): 289–295.
29.
XingKYZhouMCLiuHX. (2009) Optimal Petri net based polynomial-complexity deadlock avoidance policies for automated manufacturing systems. IEEE Transactions on Systems, Man, Cybernetics, Part A: Systems and Humans39(1): 188–199.
30.
XingKYZhouMCWangF. (2011) Resource transition circuits and siphons for deadlock control of automated manufacturing systems. IEEE Transactions on Systems, Man, Cybernetics, Part A: Systems and Humans41(1): 74–84.
31.
XingKYHanLBZhouMC. (2012) Deadlock-free genetic scheduling algorithm for automated manufacturing systems based on deadlock control policy. IEEE Transactions on System, Man, and Cybernetics, Part B: Cybernetics42(3): 603–615.
32.
XiongHHZhouMC (1998) Scheduling of semiconductor test facility via Petri nets and hybrid heuristic search. IEEE Transaction on Semiconductor Manufacturing11(3): 384–393.
33.
ZhouMCDiCesareF (1993) Petri Net Synthesis for Discrete Event Control of Manufacturing Systems. London: Kluwer Academic Publishers.
34.
ZhouMCVenkateshK (1998) Modeling, Simulation and Control of Flexible Manufacturing Systems: A Petri Net Approach. Singapore: World Scientific.
