An efficient Pareto approach for solving the multi-objective flexible job-shop scheduling problem with regular criteria

(1)

ContentslistsavailableatScienceDirect

Computers and Operations Research

journalhomepage:www.elsevier.com/locate/cor

An eﬃcient Pareto approach for solving the multi-objective ﬂexible job-shop scheduling problem with regular criteria

Andrés Alberto García-León

^a^,^b^,^∗

, Stéphane Dauzère-Pérès

^b^,^c

, Yazid Mati

^d

aFacultad de Ingeniería, Programa de Ingeniería Industrial, Universidad de Ibagué, Ibagué, Colombia

bDepartment of Manufacturing Sciences and Logistics, Mines Saint-Etienne, Univ Clermont Auvergne, CNRS, UMR 6158 LIMOS, CMP, Gardanne, France

cDepartment of Accounting, Auditing and Business Analytics, BI Norwegian Business School, Oslo, Norway

dCollege of Business and Economics, Qassim University, Saudi Arabia

a rt i c l e i n f o

Article history:

Received 13 February 2018 Revised 19 February 2019 Accepted 9 April 2019 Available online 11 April 2019 Keywords:

Flexible job-shop scheduling Multi-objective

Regular criteria Pareto optimization Local search

a b s t r a c t

Inthispaper,agenerallocalsearchapproachfortheMulti-ObjectiveFlexibleJob-shopSchedulingProb- lem(MOFJSP)isproposedtodetermine aPareto frontforanycombinationofregularcriteria.The ap- proachisbasedonadisjunctivegraph,afastestimationfunctiontoevaluatemovesand ahierarchical testtoeﬃcientlycontrolthesetofnon-dominatedsolutions.Foursearchstrategiesusingtwoneighbor- hoodstructuresaredeveloped.Numericalexperimentsareconductedontestinstancesoftheliterature withthree setsofcriteriato minimizeand using metricsto evaluateandcompare Pareto fronts.The resultsshowthatourapproachprovidessetsofnon-dominatedsolutionsofgoodquality.

ThisisanopenaccessarticleundertheCCBY-NC-NDlicense.

(http://creativecommons.org/licenses/by-nc-nd/4.0/)

1. Introduction

Ina strongcompetitiveenvironmentandwithmoreandmore demandingcustomers,manufacturingandservicesystemsmustbe flexible (Johnzenetal., 2011) andable todeal withdifferent objectives dynamically. Among the important operational decisions are scheduling decisions where several types of flexibility have beenconsidered, andinparticularoperationflexibility that refers to the ability ofan operation to be performed indifferent ways.

The schedulingliterature dealing withoperation ﬂexibility inthe classical Job-shopSchedulingProblem(JSP)hasaccumulatedover thelast twentyﬁveyears(seetherecentsurveyofChaudhryand Khan, 2016), leading to the so-called Flexible Job-shop Schedul- ingProblem(FJSP).TheFJSPismorerealisticformodelingawide range of real-life applications, as it can capture key features of modernmanufacturingandservicesystems.

The Flexible Job-shopScheduling Problem (FJSP)is deﬁned as follows.AsetMofm machinesarealways availableto processa set ofnjobsJ =

{

^J1,...,J_n

}

^.Êach^machine ^can ônly^performône

operationatatime.Eachjobconsistsofasequenceofoperations,

∗ Corresponding author at: Facultad de Ingeniería, Programa de Ingeniería Indus- trial, Universidad de Ibagué, Ibagué, Colombia.

E-mail addresses: andres.garcia@unibague.edu.co (A .A . García-León), dauzere- peres@emse.fr (S. Dauzère-Pérès),matie@qu.edu.sa (Y. Mati).

calledrouting,whichcandifferfromonejob toanother,i.e.there isnotasinglepre-speciﬁedorderofmachinesforalljobs.Thepre- emption ofoperationsisnot allowed, i.e.an operationcannot be interruptedoncestarted.EachjobJ_ihasareleasedater_i,aweight w_i related to thepriority ofjob J_i, anda duedate d_i that speci- ﬁes thedate before which J_i should be completed. An important featureoftheFJSPisthatthemachineneededtoperformanoper- ationjisnotgivenbutmustbeselectedfromasubsetRj⊆Mof eligiblemachines.Theprocessingtimep_jofanoperationjdepends ontheselectedmachineinRj.Letusassumethattheseprocessing timesarenon-negativeinteger,knownandincludenon sequence- dependent setup times between operations. The FJSP consists in bothassigninga machinetoeachoperation andsequencingoper- ationsontheselected machines,to optimizeasinglecriterion or multiplecriteria.

Insinglecriterion optimization,the moststudied criterion for the FJSP is the minimization of the makespan Cmax, which cor- responds to the completion time of all jobs. However, minimiz- ing other criteria that include the weight of jobs and their due dates are better suited to capture critical factors that affect the competitiveness of a ﬁrm (Zhang and Wu, 2011). Regular criteria are among the most common objectives considered in the scheduling literature. A criterion is said to be regular if it is an increasing function of the completion timesof the jobs (see e.g.

Mati et al., 2011 for the JSP). In addition to the makespan, the https://doi.org/10.1016/j.cor.2019.04.012

(2)

followingregularcriteriaareamongthemostpopularonesinthe schedulingliterature:(1)MaximumtardinessTmax=maxT_i,where T_i=max(⁰,C_i−d_i),C_iisthecompletiontimeofjobJ_iandd_iisits duedate,(2)Totaltardiness iT_i,(3)Totalcompletiontime iC_i, and(4) Number oftardy jobs iU_i, whereU_i=1 if T_i>0and 0 otherwise.

The Multi-Objective Flexible Job-shop Scheduling Problem (MOFJSP)istheoptimizationoftheFJSPwithmultiplecriteriathat areinconﬂicttosomeextent.Inthispaper,wedevelopageneral localsearch approach that optimizes anycombination of regular criteriafortheMOFJSP.Theremainderofthepaperisorganizedas follows.Section 2reviewsthe relatedliterature. Section 3details thedisjunctivegraphmodelandtheneighborhoodstructuresthat areusedtosolvetheFJSP.Section4proposesatheoreticalframe- worktoevaluatethequalityofthesetofnon-dominatedsolutions.

Section5 describesthe proposed localsearch approach basedon Paretooptimizationwithfournew searchstrategies. Experiments thatvalidate theeﬃciencyofourapproacharepresentedanddis- cussedinSection6.Finally,Section7concludesthepaperandpro- videssomedirectionsforfutureresearch.

2. Literaturereview

The FJSP has beenextensively studiedin the literature to optimizeasinglecriterion ormultiple criteria.Arecentsurvey cov- eringthe various techniques to solve the FJSP with a single objective and multiple objectives, can be found in Chaudhry and Khan (2016). This survey includes different comparative tables to classify the literature accordingto the performance measures and the types of techniques. It also gives, for each paper, the algorithm and shop details, the objective functions considered and the number of citations. Another survey can be found in Genova et al. (2015) that only covers techniques developed to solve the MOFJSP between 2005 and 2014. A recent literature review on genetic algorithms to solve the FJSP is presented in Amjadet al.(2018) where,for each paper,the considered objective functions, the parameters of the genetic algorithms andthe benchmarksarepresented.

By taking a closer look at the literature on the MOFJSP, one canobservethat mostpapersfocus onoptimizingthe makespan, the total workload of machines, and the workload of the criti- calmachine. ChaudhryandKhan (2016)report (Table3) that the makespan is used in combination with another objective function in 39.59% of papers, and 23.35% of them use the workload of machines. Even though the list of papers in Chaudhry and Khan (2016) is not exhaustive as they missed some papers, the observationand trend are the same. The makespan remains the moststudiedcriterionfortheFJSP,andisgenerallycombinedwith theworkloadofmachinesintheMOFJSP.Asimilarobservationcan be drawn fromAmjad etal. (2018) (Table 10) where 88.88% (i.e.

32out of36) ofpapersrelyingongeneticalgorithmsto solvethe MOFJSPconsider themakespan andworkload ofmachines. Since thereare avery largenumber ofpaperson theMOFJSP, we only focusinthissectionontherecent,state-of-the-artandcloselyre- latedworkswheremultiplecriteriaareoptimized,withspecialat- tentiontopapersthatconsiderregularcriteria.

TheMOFJSPisusuallytackledintheliteratureusingtwotypes of approaches. The ﬁrst one consists in transforming the multi- objectiveproblemintoamono-objectiveproblembyassigningdif- ferent weights for each objective. Various heuristics in this cat- egory were proposed in the literature. A Tabu Search algorithm is presented in Li et al. (2014) that uses several neighborhood search rules for machine assignment and operation scheduling.

A heuristic method that starts from an initial solution, and im- proves it using two move search algorithms, is introduced in Xingetal.(2009).Severalhybrid heuristicsareproposed such as

thehybridizationofparticleswarm optimizationandTabu Search inZhangetal.(2009),genetic algorithmsandShifting Bottleneck inGao et al.(2007), andParticle Swarm Optimization andSimu- latedAnnealinginXiaandWu(2005).

Thesecond typeofapproachesthatstartedaboutﬁfteenyears agoisbasedonParetooptimizationwherethegoalistodetermine the set of non-dominated solutions, i.e. the Pareto front. A hier- archicalheuristic algorithmthat isan adaptationoftheNewton’s methodforcontinuousmulti-objectiveunconstrainedoptimization problemsisproposedinPérezandRaupp(2016).Twoadaptedge- netic algorithms arepresented inRahmati etal.(2013). Asimple andeffective evolutionaryalgorithm that needs only two param- etersisdeveloped inChiangandLin(2013),anda ﬁltered-beam- search-basedheuristicinShi-Jinetal.(2008).

Many authors developed hybrid methods that combine two or more algorithms to improve the convergence while ensuring the diversity of solutions. Chun et al.(2013) combine an evolutionaryalgorithm withalocal search heuristic.ANon-dominated Sorting Genetic Algorithm II is combined with a local search in Yuan and Xu (2015), a Scatter Search algorithm that uses Tabu Search andPath-Relinking is proposed in González et al. (2015), a Path-Relinking based on a Tabu Search algorithm with back- jumping trackingisdevelopedinJiaandHu(2014),a hybriddis- crete ParticleSwarm Optimization andSimulatedAnnealingalgo- rithmareproposedinShaoetal.(2013),aPareto-basedestimation ofdistribution algorithm iscombined witha localsearch heuris- ticinWangetal.(2013),ageneticalgorithmandlocalsearch are combinedinXiong etal.(2012), ageneticalgorithm iscombined withaSimulatedAnnealinginLi(2011),andanapproachhybridiz- inga discreteArtiﬁcial BeeColonyalgorithm andlocalsearch ap- proachesisproposedinLietal.(2011).

All the above mentioned papers focus on optimizing the makespan, the total workload of machines, and the workload of the critical machine. There are only very few papers that consider other objectives such as regular criteria. In the FJSP with mono-objective, García-León et al. (2015) propose a gen- eral approach foroptimizing any regular criteria, which presents new concepts to be used in local search methods. To minimize the total tardiness, Trkylmaz and Bulkan (2015) combine a genetic algorithm and a Variable Neighborhood Search, and Mousakhani (2013) presents a Mixed Integer Linear Pro- gramming model and an iterated local search. For the MOFJSP, Singh et al. (2016) propose a Particle Swarm Optimization algo- rithmtosimultaneouslyminimizethemakespan,meanﬂowtime, andmeantardiness. Gaoet al.(2014) minimize a weightedcom- bination of the makespan and the mean of earliness and tardiness, usinga discrete Harmony Search algorithm that makes use ofseveralheuristics. AVariableNeighborhoodSearchalgorithmis proposed in Bagheriand Zandieh (2011)to minimize aweighted sum of the makespan and the mean tardiness. Vilcot and Bil- laut(2011)presentaversion ofTabuSearch thatminimizesalin- earcombinationofC_max,^TiandL_max.TayandHo(2008)consider theminimizationoftheweightedsumofthemakespan,themean tardiness,andthemeanﬂowtime,byusingpriorityrulesandthe concept of geneticprogramming. A heuristic inspired fromParti- cleSwarmOptimizationandVariableNeighborhoodSearchispro- posedinLiuetal.(2006)forminimizingaweightedlinearcombi- nationofthemakespanandthesumofcompletiontimes.

The MOFJSP has also been addressedunder a variety of con- straints, assumptions and practical issues. In Lei et al. (2018), the makespan and total tardiness are minimizedunder the con- straintthatthetotalenergyconsumptiondoesnotexceedagiven threshold.MokhtariandHasani(2017)developanevolutionaryal- gorithm to minimize the makespan, the total availability of the system, andthetotalenergycost ofboth productionandmainte- nanceoperations.Theuncertaintyinprocessingtimesisaddressed

(3)

in Shen et al. (2017) to simultaneously minimize makespan, maximal machine workload, and robustness to uncertainties.

Lu et al. (2017) investigate the problem under controllable processing times, i.e. the processing times of operations can be controlled by allocating additional resources, to ﬁnd an eﬃcient trade-off betweenthe makespanand the totaladditional resource consumption.Fuzzyprocessingtimesandfuzzyduedates aread- dressed in Chun et al. (2013) using a memetic algorithm that combinesgeneticglobaloptimizationwithalocalsearchmethod.

Ahmadietal.(2016)addressrandommachinebreakdownsbycon- sideringthemakespanandstabilitymeasures.Lietal.(2014)consider maintenance activities on machines and propose a discrete Artificial Bee Colonyalgorithm to deal withthe makespan, the total workload of machines, and the workload of the critical machine.Randommachinebreakdowns arealsoconsideredin Xiongetal.(2013)withtheobjectiveofminimizingthemakespan andtherobustness.ThedynamicFJSPwithjobreleasedatesisad- dressed inNieetal.(2013) tominimize themakespan,themean flow time, and the mean tardiness. Sadrzadeh (2013) considers sequence-dependentsetupsusinganArtificialImmuneSystemand ParticleSwarmOptimization tominimizeanaggregatefunctionof themakespanandthemeantardiness.Setuptimesarealsoconsid- eredinBagheriandZandieh(2011)usingaVariableNeighborhood Search approach to minimize the makespan andthe meantardi- ness.

To conclude, the MOFJSP has been solved in the literature using different methods that range from simple heuristics to sophisticated metaheuristics. Although the MOFJSP gained con- siderable attention from researchers during the last ten years, moststudies considertheoptimizationofthe makespanandtwo non-regular criteria (total workload and maximum workload of machines).Averylimitednumberofpapersaddressregularcrite- riaevenwhenoptimizingasinglecriterion.Indeed,Chaudhryand Khan (2016) report that the optimization of the makespan combined withother regularcriteriahaslittle beenstudied,e.g. 2.5%

ofthepapersconsidermaximumtardinessand1.5%dealwithtotal tardiness.Whenregularcriteriaarecombinedwiththemakespan, mostpapersdonotaimatParetooptimizationandinsteadaggre- gate the criteria in one objective using a weight for each criterion. Moreover, the concepts of disjunctive graph andestimation functionsarenot exploited.Oneofthecontributionsofthispaper is thedesign ofan eﬃcientParetooptimization approachforthe MOFJSPwithregular criteriaby developingdifferent strategiesto eﬃcientlydetermineasetofnon-dominatedsolutions.

3. ProblemmodelingandneighborhoodstructuresfortheFJSP

Thissection introduces thedifferentconcepts used inthispa- pertomodelandsolvetheMOFJSP, andillustratestheseconcepts usingthe exampleinTable 1withthree jobsandfourmachines.

Each job J_i has four operationswhich are denoted O_ij (i=1,2,3 and j=1,2,3,4).Forexample,theﬁrstoperationofjobJ₁hastwo eligiblemachinesM₁ andM₃withprocessingtimesof3and5,re- spectively.The thirdoperationofJ₂ hasnoﬂexibility,sinceitcan onlybeperformedonmachineM₄.

TheFJSPwithregularcriteriacanbemodeledusingadisjunc- tive graph G=(V,A,E) ^where V is the set of nodes and A∪E is theset ofarcs (see Dauzère-PérèsandPaulli, 1997). Letusre- call some important deﬁnitions.The set V includes operationsof jobs, a dummy node 0that represents thestart of each job, and ndummynodes

φ

i associatedto thecompletionsofjobs(seee.g.

Matietal.,2011).Nodes

φ

iarenecessarysinceregularcriteriade- pendonthecompletiontimesofjobs.ThesetAcontainsconjunc- tivearcsthatconnecttwoconsecutiveoperations(i.e.intherout- ing)ofajob,thenode0andeveryﬁrstoperationofeachjob,and thelast operationofeach jobJ_itoitscorresponding node

φ

i.The

Table 1

An illustrative example of the FJSP.

Eligible machines and processing times for operations

Job 1 2 3 4

J 1 M 1(3)/ M 3(5) M 2(3)/ M 4(4) M 1(5)/ M 3(1) M 3(1) J 2 M 1(5)/ M 3(4) M 1(4)/ M 2(5) M 4(1) M 2(2) J 3 M 1(2) M 3(3)/ M 4(4) M 2(8) M 3(2)/ M 4(2)

Table 2

Critical paths of jobs and their corresponding blocks for solution in Fig. 1 (b).

Job Critical path Block

J 1 0 → O 11→ O 31→ O 22→ O 13→ O 14→ φ1 ( O 11→ O 31→ O 22→ O 13) J 2 0 → O 11→ O 31→ O 32→ O 33→ O 24→ φ2 ( O 11→ O 31), ( O 33→ O 24) J 3 0 → O 11→ O 31→ O 32→ O 33→ O 34→ φ3 ( O 11→ O 31)

setE=∪m∈MEm containsdisjunctivearcs whereEm includes arcs betweenpairsofoperationsthatmayusemachinem.Thearcfrom 0totheﬁrstoperationofajobJ_ihasalengthwhichisequaltothe releasedater_iof J_i, andanyremaining conjunctiveordisjunctive archasa lengthwhichisequalto theprocessingtime oftheop- erationfromwhichitstarts.Fig.1(a)showsthedisjunctivegraph fortheexampleinTable1.

Afeasible solutionof theFJSP isobtained by assigninga machine to each operation (thus keepingonly the relevant disjunctive arcs in E) and by fixing a direction to each disjunctive arc in E such that the induced graphdoes not contain anydirected cycle. To effectively exploit the structure and properties of the graph in a local search approach, the graph must be simplified by removing redundant arcs so that every node x has at most onepredecessorandonesuccessoronthemachinethatperforms x.Fig. 1(b)shows a feasiblesolution forthe example inTable 1. Forexample, the firstoperation O₂₁ of job J₂ is assigned to machine M₃. The sequences of jobs with their operations on machines are the following: J₁(O₁₁)→J₃(O₃₁)→J₂(O₂₂)→J₁(O₁₃) on M₁, J₁(O₁₂)→J₃(O₃₃)→J₂(O₂₄) on M₂, J₂(O₂₁)→J₃(O₃₂)→J₁(O₁₄) onM₃,andJ₂(O₂₃)→J₃(O₃₄)onM₄.

Thestartingtime hx (calledhead) ofa node xis givenby the lengthofa longestpathfrom0tox.Thelevel lx ofnode xisthe maximum number of arcs fromnode 0 to x. The tail qⁱ_x of x to a dummy node

φ

i is the maximum length from the completion ofx to

φ

i ifa path exists fromx to

φ

i and−∞otherwise. Tails areneededsinceregular criteriaare consideredinthispaper.For example,looking at Fig. 1(b),the head of operation O₂₃ is 9, its level isequal to 4 andits tail to

φ

3 isequal to 2. However, the tailofoperationO₂₃ to

φ

1 isequal to−∞sincethereis nopath fromO₂₃ to

φ

1.Thelongestpathfromnode0tonode

φ

iiscalled thecriticalpathfrom0to

φ

i,anditslengthisequaltoh_φ

i,which correspondsto thecompletion time ofJ_i.Everynode xbelonging toa criticalpath iscriticalaccordingto J_i,andsatisﬁes hx+px+ qⁱ_x=h_φ

i. Each arc(x, y) belonging to the critical path from 0 to

φ

i iscritical ifnodes xand y are assignedto the same machine andbelongtotheroutingofdifferentjobs.Ablockisamaximum sequenceofcriticalnodesassignedto thesamemachine.Table 2 showsthecriticalpathsofjobsandtheir correspondingblocksfor thesolution inFig.1(b).Note that O₃₁ iscritical forall jobs, O₂₄ isonlycriticalforjobJ₂,whereasoperationsO₁₂,O₂₁,andO₂₃ are notcritical.ThecriticalpathofjobJ₂containstwoblocks.

Neighborhood structures are used in local search to generate newsolutionsbyperformingsmallperturbationsofacurrentsolu- tion.IntheFJSP,awell-knownperturbationproposedinDauzère- PérèsandPaulli(1997)consistsinmoving(i.e.resequencingorre- assigning)acriticaloperationinthegraphofthecurrentsolution.

In this paper,we consider two neighborhood structures (N₁ and

(4)

Fig. 1. Disjunctive graph model and a feasible solution for the example in Table 1 .

N₂), whichdifferfromone anotherin theselection ofoperations thatare moved.Neighborhoodstructure N₁ focusesonall critical operationsof jobs, while neighborhood structure N₂⊂N₁ focuses on operationsthat belong to blocks of critical paths of the jobs thataffectthevalueofthecriterion(e.g.jobsthatarelateforlate- nesscriteria).Ourmotivation indeﬁning thesetwoneighborhood structures is to analyze whether the concept of blocks is help- ful to generate sets of non-dominated solutions for the MOFJSP.

Tounderstandthe differencebetweenN₁ andN₂,let usconsider theminimizationof^Ci inthesolutionofFig.1(b).According to thecriticalpathsandblocksofTable2,neighborhoodstructureN₁ considers the criticaloperations O₁₁, O₁₃, O₁₄,O₂₂,O₂₄, O₃₁, O₃₂, O₃₃ and O₃₄, whereas neighborhood structure N₂ “only” focuses on O₁₁, O₁₃,O₂₂,O₂₄, O₃₁ and O₃₃. Table 3 gives the possible re- sequencingandreassignmentmovesforeachcriticaloperation in bothneighborhoodstructures.ForagivencriticaloperationO_ij,the notation[a−b]meansthatO_ijismovedbetweenoperationsaand b.Ifa=0(resp.b=∗), O_ij ismoved in theﬁrst (resp.last)posi- tionofthesequenceofthemachineonwhichitisresequencedor reassigned.Forexample,O₁₁ canberesequencedbetweenO₂₂ and O₁₃,andreassignedonmachineM₃betweenO₃₂andO₁₄.

Moving an operation in both neighborhood structures N₁ and N₂ can generate directed cycles in the resulting graph, thus leading to unfeasible solutions of the FJSP. To check the feasi- bility of a move, the suﬃcient conditions proposed in García- León et al. (2015) are used. Without actually transforming the graph,they validate thata cycleisnot createdinthenewgraph.

These conditions generalize previous conditions of the literature by usingthe concepts of heads, tailsand levels ofoperations. In

Table 3

Possible resequencing and reassignment moves in Fig. 1 (b).

Critical Resequencing Reassignment

operation Move Machine Move

[ O 31−O 22] ^‡ [0 −O 21] ^‡ O 11 [ O 22−O 13] ^‡ M 3 [ O 21−O 32] ^‡

[ O 13− ∗] [ O 32−O 14] ^‡ [ O 14− ∗]

[0 −O 11] ^‡ O 31 [ O 22−O 13] ^‡

[ O 13− ∗] ^†

O 22 [0 −O 11] ^‡ [0 −O 12] ^‡

[ O 11−O 31] ^‡ M 2 [ O 12−O 33] ^‡ [ O 13− ∗] ^‡ [ O 33−O 24] ^‡ [ O 24− ∗]

[0 −O 21] ^‡ [0 −O 23] ^‡

O 32 [ O 14− ∗] ^‡ M 4 [ O 23−O 34] ^‡ [ O 34− ∗]

[0 −O 11] [0 −O 21] ^‡

O 13 [ O 11−O 31] ^‡ M 3 [ O 21−O 32] ^‡ [ O 31−O 22] ^‡ [ O 32−O 14] ^‡ [ O 14− ∗]

O 33 [0 −O 12] ^‡ [ O 24− ∗] ^‡

[0 −O 23] ^‡ [0 −O 21]

O 34 M 3 [ O 21−O 32]

[ O 32−O 14] ^‡ [ O 14− ∗] ^‡ O 24 [0 −O 12] ^†

[ O 12−O 33] ^‡ O 14 [0 −O 21]

[ O 21−O 32] ^‡

(5)

Table 3, feasible moves that are obtained by the suﬃcient conditions are denoted by the superscript‡, unfeasiblemovesby the superscript,andmovesthat arefeasiblebutcannotbe validated bythesuﬃcientconditionsaredenotedbythesuperscript†.

The best move in the neighborhood ofa solution is generally obtained using the value of the criterion of the generated solution. Previousstudies onthe FJSPhaveshownthat usingestima- tionfunctionsismoreappropriatetoevaluatethequalityofmoves, because signiﬁcant computational times can be saved and much moreiterationscan beperformedto reachbetter solutions.Since regular criteriaareconsidered inthispaper,we needto estimate thenewcompletion timesofnodes

φ

i aftermovingan operation (see Mati etal., 2011 forthe classical job-shop scheduling problem).Todoso,weusetheestimationfunctionproposedinGarcía- León etal.(2015)by consideringforwardandbackward moves.A forward (resp.backward) move of a node x,currently sequenced between nodes p and q, between two nodes u and v is deﬁned whenlx≤lu(resp.lx>lu).Theideaoftheestimationfunctioncon- sists in considering the newly created paths after the move to- getherwithasuitablesubsetofpathsthatareavailableinthecur- rentandnewgraphs.Thisisperformedbyfocusingnotonlyonthe operationx,butalsoontheoperationsinvolvedinthemovep,q,u andv,aswellasonoperationswforwhichl_w=l_x(seeMatietal., 2011). In addition to its eﬃciencyin estimating thevalue ofthe criterion,theestimationfunctionisfastandguaranteeswhenever possiblethelowerboundproperty,i.e.thequalityofamoveisnot overestimated(García-Leónetal.,2015).

4. Evaluatingsetsofnon-dominatedsolutions

Aneffectiveapproach forsolving theMOFJSPwithregularcri- teria is thePareto approach,which aimsat ﬁndinga set ofnon- dominatedsolutions S,calledtheParetofront.Inthissection,let us brieﬂy recall the main notions related to Pareto optimization andintroducethemeasurestoevaluatethequalityofthesetS. 4.1. DominanceofPareto

LetC bethe setofcriteriato minimize inParetomanner and fc(s)bethevalueofthecriterioncofafeasiblesolutions.Solution s₁ dominatessolutions₂ ifthefollowingtwoconditionsaretrue:

1. Solutions₁isnotworsethansolutions₂forallcriteria,i.e.

∀

^c∈ C,f_c(s₁)≤f_c(s₂),

2. Solution s₁ is strictly better thans₂ forat leastone criterion, i.e.

∃

^c∈C suchthatfc(s₁)<fc(s₂).

Accordingly,anytwosolutionsofSarenon-dominatedwithre- specttoeach other,andanysolutionnot inS isdominatedby at leastonesolutioninS.

4.2. Qualitymeasuresofthesetofnon-dominatedsolutions

Agoodsetofnon-dominatedsolutionsshouldsatisfytwogoals:

Convergenceanddiversity.Convergenceensuresthatthesetofso- lutions isascloseaspossibletotheoptimalParetofront,anddi- versityisrelatedtothesparsityofsolutionstoensurethatthede- cisionmakerhasmultiplerepresentativetrade-off solutionsamong conflicting objectives. Zitzleretal.(2003) state that it isdifficult todefineappropriatemeasures toapproximatetheoptimalPareto front when analyzing both goals, and that the discrepancies in- creasewhenconsideringstochasticapproaches.

For the MOFJSP, most previous studies aim at improving the convergence and increasing the number of non-dominated solutions without consideringdiversity (see e.g. JiaandHu,2014).In thispaper,weconsiderboththeconvergenceanddiversitytobet- ter evaluatethequality ofsets ofnon-dominatedsolutions.Three

measures are selected to evaluate the convergence: (1)The elite solutions, (2)The mean idealdistance and(3) The hypervolume.

Elitesolutions correspond to the best values of the criteria. The MeanIdeal Distance (MID) is the average distancebetween non- dominatedsolutions andthe originpoint (Singh etal., 2016), i.e.

thepoint(0,0)iftwocriteriaareanalyzed.MIDiscalculatedusing (1),where

|

S

|

^is^the^number^ofnon-dominatedsolutions.

MID=

s∈S

c∈C

f_c²

(

^s

)

|

^S

|

⁽¹⁾

TheHyperVolume(HV)isthevolumecoveredbythesolutions of the front. When all criteria are minimized, a reference point having ascoordinates the worst valuesof the criteria is used to limitthiscoverage(Zitzleretal.,2007).Thus,HV=

s∈SVs,where Vsisthehypercubeofswithrespecttothereferencepoint.Since thehypervolumecanlead tolarge values,(2)isused tocalculate HV,whichcorrespondstotheratioofthetotalvolumeVT covered bythereferencepointandtheoriginpoint.

HV=

s∈S

Vs

|

^S

|

^×^VT (2)

The maximum spread (D) and spacing (SP) are selected to evaluate the diversity. The metric D is the longest diagonal of the hyperbox formed by the extreme values of the criteria in S (Zitzler,1999),andiscalculatedusing(3),where f_c^maxandf_c^min are themaximumandminimumvaluesofcriterionc forallsolutions inS:

D=

c∈C

(

^fc^max−f_c^min

)

² ⁽³⁾

ThemetricSPistheaveragedistancebetweenconsecutivesolu- tionsinS (Schott,1995).Letdˆ_ibethedistancebetweensolutions_i anditsnearestsolution,i.e.dˆ_i= min

sp∈S;p=i

c∈C

|

^fc(^si)−f_c(^sp)

|

,andlet d¯betheaverageofthesedistancesforall solutionsinS.Spacing iscalculatedusing(4).

SP=

1

|

S

|

|S|

i=1

(

^d^ˆi−d¯

)

² ⁽⁴⁾

ToensurethequalityofS,thespacingandmeanidealdistance mustbeminimized,themaximumspreadandhypervolumemust bemaximizedandelite solutionsmust beascloseaspossible to theoptimalvaluesofthecriteria.

5. SolvingtheMOFJSP

TheproposedParetoapproachfortheMOFJSPwithregularcri- teria aims at finding a set of non-dominated solutions S whose convergenceanddiversityareoptimized.Letusfirstdescribehow Sismanaged,thenpresenttheframeworkoftheapproachandthe initialsolution,andfinallyproposefoursearchstrategies.

5.1. Controllingthesetofnon-dominatedsolutions

The control of the setof non-dominated solutions consists in managingsolutionsentering andleavingS eachtimeanewsolu- tionsisobtainedbythesearchprocess.Aschedules∈S iscalled areferencescheduleforcriterionciffc(s)isthebestpossiblevalue forcriterionc.Thereferencescheduleforcisdenotedbys^{re f}_c ,and thesubsetofS withthereferenceschedulesisdenotedbyS^{re f}.

Toeﬃciently control S, we propose a fasthierarchical test in three steps to avoid performing too many evaluations to check

(6)

Fig. 2. Test to check whether s is added to S.

whethersshould be added to S.The test is illustrated inFig. 2. Itﬁrstevaluatesifthevalueofanycriterioncofsisstrictlylower thanthebestvalueforcriterionc.Ifitisthecase,thensbecomes thereferencescheduleforcriterion c, andsisadded toS^{re f} and S, maybereplacing other solutions. Otherwise,the test validates the dominance between s_i∈S and s starting with the reference schedules. Ifno dominance is found, then s can be added to S, maybereplacingothersolutions.Hence,thestepUpdateS consists inaddingsandremovingthedominatedsolutions.Notethatmul- tiplesolutionsarenotconsidered,i.e.ifthevaluesofallthecrite- riaofsandofasolutions_i∈S areequal.

5.2.Frameworkoftheapproach

Theapproachconsistsoftwoalternatingphases,namelyanim- provingphaseandadiversification phase.Theimprovingphase is asteepestdescentthatperformsiterativeimprovementsuntilalo- caloptimumisreachedforagivencriterionorallcriteria.Ateach iteration,asetofneighborsolutionsisgeneratedusingtheneigh- borhoodstructures,thefeasibilitytestandthemoveevaluationde- scribedinSection3.Thediversificationphasestartsfromthelocal optimum of the improving phase andperforms at most b itera- tions.During thisphase,a criticaloperation israndomlyselected anda moveis randomly chosen. Ifthe selectedmove is feasible, theheuristic advances to the next iteration, otherwisethe above processisrepeateduntilafeasiblemoveisobtained.Ifanewbest solutionisobtainedinthe diversification phasefora givencrite- rion,thesearchreturnstotheimprovingphase,otherwiseitcon- tinuesuntilbiterationsareperformed.Thevalue ofbisrandomly selectedin[4,10]whichisfixedexperimentally.

After performingamoveinbothphases,all localvaluesofthe criteriaareupdated, thehierarchical testto determinewhether s isaddedtoS isperformed,andS isupdated ifsisaddedasde- scribed in Fig. 2. Additionally, the best values of the criteriaare updated.

TodealwithmultiplecriteriafortheMOFJSP,wepropose four versionsoftheabove approachthat differmainly inthe waythe criteriontooptimizeisselected,thewaytheapproachisalternat- ingbetweentheimprovinganddiversiﬁcationphases,andtheway thesolutionisselectedwheneachphaseisresumed.

5.3. Initialsolution

The initial solution is obtained using a constructive heuristic that selectsanoperation ateach stepaccordingtoan established order of the jobs. The main idea of the heuristic is to complete theselected operationassoonaspossibleto trytominimize the completion timesofjobs.Thejobsareorderedby non-decreasing weightswhenatleastonecriterionconsidersweights.Thetiesare brokenusingtheduedates,andthentheaverageprocessingtimes n_i

j=1

|^R1j|

a∈R_jp_j wheren_iis the number of operations of job J_i. Foragivenoperation xandforeacheligiblemachine M_k∈Rx,the time t_k atwhich themachine completes its previous operation v onthesequence(ifitexists)iscalculated.Operationxisthen assigned to the machine that completes x as soon as possible, i.e.

themachineM_k∈R_x that minimizest_k+p_x.The graphisupdated byaddingarc(v,x)andtheheuristiccontinuesuntilalloperations havebeenselected.

5.4. SearchstrategyT1

Theideaofthisstrategyistoconcentrateonoptimizingagiven criterion by performing an improving phase followed by a diver- siﬁcation phase. More precisely, a random criterion c is selected in C, and the improving phase performs iterative improvements of c until reaching a localoptimum for this criterion. The diver- siﬁcation phase startsfrom this local optimum and, ifthe value of the criterion c is improved during this phase, the search re- turnstotheimprovingphasewiththesamecriterionc.However, ifthemaximumnumberofiterationsbisreached,thesearchsets alllocalvaluesofthecriteriato∞,randomlyselectsanewcrite- riontominimizefromthesetC−

{

^c

}

^and^returns^to^the^improving

phase.

Thisstrategygivesmoreattentiontotheimprovingphasesince most of the promising solutions are obtained in this phase. The strategyintensiﬁesthesearch intheimprovingphaseuntilreach- ing the local optimum of all criteria. To apply this strategy, the concept offorbidden criterion orcriteriais introduced. Thiscon- cept is deﬁned and applied, for a given criterion c, only during

(7)

theimprovingstepwhenthelocaloptimumofcisreached.More precisely, a criterion becomes forbidden when, in the improving phase, it is selected to create a move and it cannot generate an improving move.A criterion isauthorized tobe selected assoon asitslocalvalueisimprovedorintheﬁnalizationofthediversiﬁ- cationphase.

More precisely, Strategy T2 starts by setting the set of forbidden criteria C^{f or} to ∅ to specify that initially all criteria are authorized.Then, ateach iteration oftheimproving phase,a criterion c is randomly selected fromthe setC−C^{f or} of authorized criteria.Thesearchoptimizescwheneveritispossibletogenerate an improvingmove, and anyforbidden criterion becomesautho- rizedifitslocalvalueisimproved.However,ifanimprovingmove is not possible with c, this criterion becomesforbidden and the search continueswith acriterion randomly selectedinthe setof authorizedcriteria.Ifallcriteriaareforbidden,i.e.C−C^{f or}=∅,the searchgoestothediversiﬁcationphase.

Animportantproblemwiththecontinuityofthesearchcanbe caused by criterion Tmax since, ifit is equal to zero,criteria ^Ti

and^Uiwillalsobeequaltozero,anditisnotpossibletocreate amove.Inthiscase,thesearchremovesallforbiddencriteriafrom C^{f or}andtheselectedcriterionciseitherCmaxor^Ciifthelatter criterionbelongstoC.

Thediversiﬁcation phasestartsfromthesolutiongeneratedby theneighborhoodstructureofthelastforbiddencriterion.Ifalocal value ofanycriterionis improvedinthisphase,thecriterion becomes authorized,andthesearch returnsto theimprovingphase using the neighborhood of this criterion. In case of several im- provedcriteria, arandomchoiceisperformed.Ifitisnotpossible toimproveanycriterionduringbiterations,allcriteriaare authorized, all localvalues ofthe criteriaare setto ∞ andthe search goestotheimprovingphasewitharandomcriterion.

ThisstrategyisavariantofT2,theonlydifferenceisintheim- proving phase inwhich it is possible that criterion c is changed in each iteration even if the last iteration was an improving move forc. This means that, rather than continuingwith a single criterion until reaching its localoptimum, T3 canmodify the optimized criterion by using a random selection fromthe set of non-forbiddencriteria.Moreprecisely,ineachiteration,arandom criterion c is selected to create a move from the set C−C^{f or}. If thismoveimprovesthecriterion,thesetofforbiddencriteriaC^{f or} is emptied.If it isnot possible to createan improving move us- ingc,thiscriterionbecomesforbiddenanditisaddedtoC^{f or}.Ifit is notpossible tocreate animproving move withallcriteria, the search goestothediversiﬁcation phaseconsideringtheneighbor- hoodofthelast forbiddencriterion andthesameguidelinesthan StrategyT2.

Strategy T4 operates as Strategy T3 but uses the concept of globalvalueofthecriterionc.Theonlydifferenceisintheimprov- ing phase inwhich,ifthe globalvalue ofacriterion c=c isim- proved,thiscriterionbecomestheoptimizedcriterioninthenext iterationevenifthesearchwiththecurrentcriterionwasimprov- ing. The motivationis that itis moresuitable to shiftthe search tooptimizecwiththeaimofﬁndingnewreferenceschedulesfor c,sincetheseschedulescanbelostifthesearchprocessdoesnot focusoncatthisiteration.Ifseveralglobalvaluesareimproved,a random choiceis performed.Further, inthediversiﬁcation phase, thesearchcanreturntotheimprovingphasewithacriterionthat improvesitsglobalvalue.

6. Computationalresults

Thissectionanalyzestheeﬃciencyofthegeneralapproachpro- posedintheprevioussection,whichwasdevelopedinJava.Inthe remainderofthepaper,thisapproachisdenotedGMD.Theexper- imentswere conductedonaPCwith3.40GHzand8GBRAM. The computational time for each search strategy and each neighbor- hoodstructurewassetto300 seconds.Hence,thecomputational time foraninstance is2400seconds foraset ofcriteriatoopti- mizeinParetomanner,i.e.300secondsmultipliedby foursearch strategiesandtwo neighborhood structures.Three sets ofcriteria tooptimizeareconsidered:CA,CBandCC.CA includesthreecrite- ria:Cmax,Tmaxand^Ti.CB addscriterion^UitothecriteriainCA, andCCaddscriterion^CitothecriteriainCB.

The analysis was conducted in six phases that are described in the following sections. Sections 6.1–6.5 use the problem in- stances fromBrandimarte(1993) bysetting thedue dateofeach job J_i to 1.3×n_i

j=1 1

|^Rj|

a∈R_jp_j, where n_i is the number of op- erationsofjob J_i.Section 6.1analyzes theNet FrontContribution (NFC)andthe WeakOutPerformance(WOP) ofthe twoneighbor- hoodstructures tocheckifoneisdominatingtheother.Then,the same analysisis performed forthe search strategies.The impact ofadding criteria inthe set of criteria to optimizeon the num- berofnon-dominatedsolutionsisstudiedinSection 6.2.Eliteso- lutionsforﬁveregularcriteriaareanalyzedinSection6.3.Thedi- versityis studiedinSection 6.4.Theanalysisofthe hypervolume andthe mean ideal distance is presented in Section 6.5. Finally, Section6.6comparesourapproachtoprevious approachestoop- timizethemakespanandthetotaltardiness.

6.1. AnalysisoftheNetFrontContribution(NFC)andWeak OutPerformance(WOP)

TheNetFrontContribution(NFC)isthepercentageofsolutions ofthereferencefrontthat areincludedin aspeciﬁedset ofnon- dominatedsolutions (Debetal., 2001). Forexample,iftheNFCof StrategyT1is25%,then25%ofthesolutionsofthereferencefront belongtoT1.TheWeakOutPerformancemetric(WOPx,o)evaluates the dominance betweentwo sets of non-dominated solutions sx

andso(seeVilcotandBillaut,2011).Thesetsx weaklyoutperforms soifnosolutioninsx isdominatedbyasolutioninsoandatleast onesolutionins_x dominatesasolutionins_o.Hence,WOP_x,o takes value 1 if sx weakly outperforms so and 0 otherwise. To further improvetheanalysisofdominancebetweensx andso,weextend thenumericalscaletothreevalues−1,0and1:WOP_x,oisequalto 1(resp.−1)ifsx (resp.so)weaklyoutperformsso(resp.sx)and0 otherwise.

Table 4 presents, over ten runsof the algorithm, the average NFC andthe average percentagefor WOP_N

1,N₂ (WOP) when it is equal to 1 or −1 for each set of criteriaand for each neighborhoodstructure.Asanexample,mk01hassixmachines(m),10jobs (n) and a ﬂexibility level (ﬂex) of 2.09, i.e.one operation has on average2.09eligiblemachines.ForCA,theaverageNFCforneigh- borhoodN₁is50%and53.3%forN₂.N₁ weaklyoutperformsN₂(1 incolumnWOP)in33.3%ofcasesandN₂ weaklyoutperformsN₁ (−1in columnWOP)in 60% ofcases.Additionally,the neighbor- hoodstructurewiththeaveragelargestNFCandWOP arewritten inbold.

Table4showsthatthereisnotadominantneighborhoodstruc- ture, even though N₂ is slightly better, which confirms the ben- efit ofusing the concept of blocks to solve the flexible job-shop scheduling problem. Using the NFC metric, neighborhood struc- tureN₂generateslargercontributionsfor17instancesover30in- stances:mk01, mk03, mk07, mk08 andmk10 for CA; mk02, mk03, mk04,mk05,mk08andmk09forCB,andmk03,mk04,mk05,mk06, mk07and mk08for CC. N₁ generates larger contributions for the