2.Thesis 2

  https://www.reads.ie/college-printing-dublin.php

 

 
 
Journal of Software Engineeringand Applications,2014,7,571-580

PublishedOnlineJune2014 inSciRes. http://www.scirp.org/journal/jseahttp://dx.doi.org/10.4236/jsea.2014.77053

 

 

Comparative Study of Different Representations in Genetic Algorithms for JobShop Scheduling Problem

 

 

Vedavyasrao Jorapur*,V.S. Puranik,A.S.Deshpande,M.R. Sharma

 

Visvesvaraya Technological University, Belgaum, India

Email:*jorapur@fragnel.ac.in

 

Received 13February 2014;revised 10March2014;accepted 18March2014

 

Copyright ©2014by authorsand ScientificResearch PublishingInc.

Thiswork islicensed underthe Creative Commons Attribution International License(CCBY).

http://creativecommons.org/licenses/by/4.0/

 

 

 Abstract

 

Dueto NP-Hardnature of the JobShop Scheduling Problems(JSP),exactmethods failtoprovide the optimalsolutions in quiter easonable computational time.Dueto this natureof theproblem, so many heuristicsand meta-heuristics havebeen proposed in the pasttogetop timalornear- op- timalsolutions foreasy to toughJSP instances in lesser computational time comparedto exact methods.One of suchheuristicsis geneticalgorithm(GA). Representationsin GA will havea direct impact on computationa timeittakesin providing optimalornearoptimalsolutions.Different representationschemesarepossibleincaseofJobScheduling Problems.Theseschemesinturn willhavea higher impacton the performanceof GA.It isintendedto show throughthis paper, how these representationswill perform,bya comparativeanalysisbased on average deviation,evolu- tionof solution over entiregenerationsetc.

 

Keywords

 

JobShopScheduling,GeneticAlgorithm, GeneticRepresentation, Conceptual Model

 

 

 

1.Introduction

 

Scheduling isadecision-making processwhich dealswithallocation of resourcestotasksovergiventime-pe- riodsanditsgoalistooptimizeoneormoreobjectivefunctions.Aschedulingproblem isrepresentedbytriplet α/β/γfielddescribesmachineenvironment;βfieldprovides details of processing characteristicsandcon- straintsandγfielddescribes theobjective functiontobeminimized.Being essentially acombinatorial optimiza- tionproblem,jobshopschedulinghascaughttheattentionof researchersinthelastsomany yearsforoptimized

 

*Correspondingauthor.

 

How tocite this paper:Jorapur,V.,Puranik,V.S.,Deshpande,A.S.andSharma,M.R.(2014)ComparativeStudyofDifferent

RepresentationsinGeneticAlgorithmsforJobShopSchedulingProblem.JournalofSoftwareEngineeringandApplications,

7,571-580. http://dx.doi.org/10.4236/jsea.2014.77053

 

performance.Combinatorialoptimization problemscanbeclassifiedas easyandhard. Problemswhicharepoly- nomialysolvablewithlimitednumberofvariablesaretreatedeasy andarecalledP.Thenotionpolynomial solvabledependsonthetypeofencoding.Itisassumedthatproblemsdescribingnumericaldataarebinary en- codedandthenumberof stepsinvolvedin solvingthese increasesexponentiallywithincreasein length of string andhencecomputationaltimewill beenormously large andtreatedto behardproblems.Jobscheduling prob- lemsbelongtothiscategory andaretermedNP-Hard[1].Inthepracticalmanufacturingenvironment,thescale ofjobshopsisgenerallymuch largerthan thatof JSSPbenchmarkinstancesconsideredintheoreticalresearch. Optimizationalgorithmsforjobshopschedulingusually proceed by BranchandBoundandamongthemostre- centandsuccessful,onesarethoseofCarlierandPinson(1989) andApplegateandCook(1991)[2].Approxi- mationproceduresorheuristicswereinitiallydevelopedonthebasisofpriority rulesordispatching rules.The quality ofsolutionsgeneratedbytheseprocedures leaveplenty of room forimprovement(1998)[3].Therefore, traditionalormeta-heuristicalgorithmscanhardly beabletosolvesuchproblems satisfactorily.Inmanufactur- ingworkshops,availabilityof computationalresourcesismuch lessthanthelaboratorieswhichleadtodifficulty inexploring all possiblefeasiblesolutions.Undersuchcircumstances,itis reasonabletoreducethesearchspace andrangetoonlypromisingareas.Theveryideaof usingconstructiveheuristicsandheuristicsearchalgorithms forlargerproblem sizesof JSSPisthecomputationalexpensivenatureofenumerativetechniques andLagrann- gianalgorithms.AccordingtoOsman(1996),aheuristicsearch“isaniterativegenerationprocesswhichguides asubordinateheuristicby combining intelligently differentconceptsforexploring andexploiting thesearch spaces”.

Extensiveuseofgeneticalgorithmstosolvejobshopschedulingproblemscan beseen throughliteraturesur- vey[4].However,how effectivelygeneticalgorithmscanbeusedinJSSPcaseisnotcompletelyexplored.In this context, some directionis provided byTamer F.Abdelmaguid[5]in hispaper. Gasare based onanabstract modelof naturalevolution,suchthatquality of individualsbuildstothehighestlevelcompatiblewith theenvi- ronment (constraintsofthe problem). (Holland, 1975;Goldberg, 1989)

Representations inGA environmentappliedsofarin jobshopschedulingcanbeclassifiedintoninecatego- ries asgivenbyChengetal. (1996):

1) Operationbased               2)Jobbased                 3)Jobpairrelationbased               4) Completiontime based

5)Randomkeys                 6)Preferencelistbased            7)Priority rulebased          8)Disjunctivegraphbased.

9) Machinebased.

Ninecategoriesmentionedabovecan begroupedintotwobasicencodingapproachesdirectandindirect encoding.Indirectapproach,aΠj    scheduleisencodedasachromosomeandgeneticoperatorsareused  to evolvebetterindividualones.Categories1to5areexamplesofthiscategory.Incaseofindirectapproach,a sequenceofdecisionpreferenceswillbeencodedintoachromosome.Inthis,encoding,geneticoperatorsareappliedtoimprovetheorderingofvariouspreferencesandaΠj  scheduleisthengeneratedfromthesequenceofpreferences.Categories6to9areexamplesof thiscategory[6].Theserepresentationsneedtobestudiedin case ofjobshopschedulingproblemstocomparetheirperformancecriteriatogenerateoptimalornearoptimalsolu- tions,eventhoughcomputationalcomparisonofdifferentrepresentationsisreportedina  tutorialpaperby Cheng,GenandTsujimura[6].AreportbyAnderson,GlassandPotts[7],conductedwithdifferentmetaheu- risticsapproachesincludingfourdifferentGA implementations,lacksinconsistencyaswellascoherenceasre- gards numberoftestproblemsbeingtestedwithrequisitenumber ofruns.

Therestof this paperisorganizedas follows: Wewillstartwithmathematicalmodels withcertain assump- tions thathavebeenusedinnextsectionfollowedbythe literaturereview onthedifferentGA representations usedin thecaseof JSP.Followedby reviewofGArepresentations,wewilldiscussregardingdifferentGAop- eratorsfrequentlyusedby researchersandourownviewsonaddingotheroperatorsnotdiscussedsofar.Now, wewillanalyzetheexperimentalresultsconductedfollowedbytheconclusionprovidedin thefinalpartofthis paper.

 

2.Problem Formulation

 

Sinceitisan importantpracticalproblem,someauthorshaveformulatedvarious JSPmodels basedon different production situationsand problemassumptions. Themostcommonassumptionsincaseof JSPare:

1) A machinemayprocessmorethanone jobata time;

2) Nojobmaybe processedbymorethanonemachineatatime;

3)The sequence of machines whicha jobvisitsiscompletelyspecifiedandhasa linear precedence structure;

4) Processingtimesare known. Allthe processingtimesareassumedto be integers;

5) Eachjobmustbe processed oneachmachineonlyonce. There is no recirculation;

6) Set-uptimesare assumedzero;

7) Pre-emptionis notallowed.

LetJrepresentasetofjobsandeachjobwillbe processedona setof machines ina particular order. LetI=


(1..v)representtheoperationindexes.Theoperationindexesareassignedsuchthatfora job


k  J,the subset


ofconsecutiveindexes  I =


βk,β + 1,β + 2,ωk


I,isasubsetcontainingindexesforthatjob.Nowfrom


thesubsetI dependingonthepriorityoperationwithhigherorlowervalueisprocessedfirst.Letp bethe

processingtimeofithoperation,thejobwhichitbelongstoisj(i)andthemachineonwhichithoperationcar-

riedism(i).


Now theobjectiveofschedulingprocessistodeterminethestarttimesti  ofanoperation


iI.Whileassign-


ingajobtoamachinebasedonabovecalculationsfollowingconstraintsshouldbetakenintoconsiderationviz.

Thetechnological constraintswilltakecareof order of operations tobecarriedout on a jobandasecondsetof constraintwilltakecare of conflictof twojobstobeprocessedonthesamemachinesimultaneously.Accor- dingly:


 

 

and


st +p sti+1..Is the equation to satisfytechnologicalconstraints


(1)


st st +p Or


stj    st +pi


(2)


 

Isthe equationto satisfythe conflictoftwojobsonthe samemachineatthe same time.

i,  j Iwherem(i ) =m( j ) and  j(i )  j( j )

Differenttotalcostfunctionsthatcanbe studiedare

Fmax.(C) :=max.{ fi  (Ci) i=1,,n} IscalledBottleneckobjective and


 

i= 

 fi  (C) = fi  (Ci) IscalledSumObjective.

i=1

The  most  common  objective  functions  are  the  make  span  max


 

 

 

{(Ci) i= 1,,n}


 

 

 

 

and  total  flotime


n

(Ci ) ,andweighted(total)flowtime

i =1


n

 w  C .Wehaveconsideredtheminimizationofmakespanas

i=1


ourobjectivefunction.Mannes[8]proposed anintegerlinearprogrammingmodel(ILP)whichuses different formsof binary variables.Thismodelhasgainedlargerinterestintheresearch community duetosmallnumber ofvariablesconsideredin themodel.Thetechnological constraintsof Equation (1)areanalogoustoaseriesof consecutiveactivities thatarecarried outin projectscheduling.Thisanalogyhasmotivatedimportingproject networksintoJSPenvironment.Torepresentdisjunctiveconstraints as in Equation (2),additionalsets ofarcs required.Thisisachieved ina disjunctive graphmodel[9]andPIANmodel[10].

In thedisjunctivegraphmodel,adisjunctivearc is definedbetweenapairof operationsthatsharethema- chine.Eachdisjunctivearcisassignedabinary decisionvariablesuchthatselectiononthevaluethatvariable definesthelength anddirectionofeach disjunctivearc. ThisistotheMannesmodel.Very efficientalgorithms like immediateselectionsandshifting bottleneckheuristicswere proposedby Carlier[11]andAdams [12]and Lars Monch[13], whichare derivedfromdisjunctive graphmodel.

A variable notationofthe type

m


xi,t


= 1…ifoperationi’isprocessed onmachineminunittime t’

=0...otherwise.


In ILPmodelwas proposed byBowman[14]. Wagner[15]proposedamodelwhereavariablenotation of the


 

x

 
type:

m

i,l


= 1…ifoperationi’takesithpositioninthe processingsequence onmachinem’

=0...otherwise.


 

x

 
And.Mannes[8]proposedamodelwhereavariablenotationofthetype:

processedpriorto operationj’onmachinem.


m

i,j


=1…ifoperationiis

 

= 0...otherwise.


 

3.Representationofthe Problem inGA andGA Operators

 

Darwinsprinciplesurvivalofthefittest”can beusedasastartingpointinintroducingevolutionary computa- tion.Theproblemsofchaos,chance,nonlinearinteractivitiesandtemporality beingsolvedby biologicalspe- cies are provedto beinequivalencewithclassicmethod ofoptimization[15].

Evolutionarycomputationstechniquesthatcontainalgorithmsbasedonevolutionaryprinciplesareusedto

searchforan optimalorbestpossiblesolutionforagivenproblem.Inasearchalgorithm,numberof possible solutionsisavailableandthetask istofindthebestpossiblesolutionin afixedamountoftime. Traditional searchalgorithmsrandomlysearch(e.g.randomwalk)orheuristicallysearch(e.g.gradientdescent),explore onesolution at atime in thesearch spacetofindbest possibleoroptimalsolution,whichiscomputationally in- efficient asthesearchspacegrowsin size. Whereasevolutionaryalgorithmsfromsuchtraditionalalgorithmsare populationbased.Evolutionary algorithmperformsadirectedefficientsearchby adaptationofsuccessivegen- erationsofalargernumberofindividuals.GeneticAlgorithmsisonesuchevolutionary algorithminfindingan optimalornear optimalsolutiontoa problem.Inatraditionalgeneticalgorithm,therepresentationis bitlength string.Itsapproachistogenerateasetof random solutionsfrom theexistingsolutions, sothat there isan im- provement inthequality ofsolutionsthroughoutthegenerations.Thisimplementationis achieved throughmain GAoperatorsviz.random selectionoftwosolutionsfrom individualsintheparentgeneration;performing crossoveroperation onthesetwosolutionstogeneratetwonew childsolutions.Crossoveroperation isper- formedby exchangingspecificelementsof thetwosolutionsselected;andmutationoperationisconductedon childsolutionstofurtherexplorethesearchspaceforbettersolutions.Differentvariations insimpleGA ap- proachcanbefoundinliterature surveyto improveitssearchcapabilities [16]. Representation of solutions of an optimizationproblem istobedoneinasuitableformatin GAtodealwithreproductionandmutation operators. Thisformatorstructurereferredasgenotype,needstobeeasilyinterpretabletoasolutionoftheproblem under study.Inacombinatorialoptimization problem,representationofasolution inGA isdifficultaswellasachal- lengingtask.Theseareproblemscontainingdiscretedecision variablesandare interrelatedby logical relation- ships.Asaresult,differentmathematicalmodelsmayexistforthesamecombinatorialoptimizationproblem andthismayleadto differentrepresentationsfor the same problem.

AsexplainedaboveCheng, GenandTsujimura[6]intheirpaperrepresentationofJSPinGA intodirectand indirecttype.Furthertothat,T.F.Abdelmaguid[17]inhispaperclassifiedGArepresentationsintoModel basedandAlgorithm based.In ouropinion,all representationsarealgorithm basedthoughtheyappeartobe model based.

InPriorityRuleBased(PR)representation, achromosomeisrepresentedasastringof(n1)entries(p1, p2pn)wheren−1isthenumberofoperationsintheproblem instance.Anentryp1  representsapriority rule selectedbeforehand.Accordingly,aconflictintheith   iterationofGifflerandThompsonalgorithm[18]should be resolved usingpriorityrulerepresentedbypi. Itmeans an operation fromtheconflictset hasto be selectedby thepi  tiesarebrokenrandomly.InGA domain,abestsetofpriority rulesshouldbeselected.Heresimplecros- soveryieldsfeasible schedules.

InRandom KeysRepresentation (RK) wasfirstproposedbyBean[19]. Inthisrepresentation,eachgeneis representedwithrandom numbersgeneratedbetween0 and1.These random numbersinagivenchromosome aresortedoutandarereplacedby integers andnow theresultingorderistheorderofoperationsinachromo- some.Thisstringis then interpretedintoafeasibleschedule.Anyviolationofprecedenceconstraintscan be correctedbya correctionalgorithmincorporated.

InOperationbasedrepresentation,each generepresentsanoperation.Achromosomecontainsasmany genesasthenumber of operations.For example, annxm JSPtherewillbenxmgenes in the chromosome. Beirwirth proposedatechniquepermutationwith repetition[20]which issimilartooperation basedrepresen- tation.Fang[21]alsoproposed akindoperation basedrepresentationwherestringcontainsnxmchunkswhich arelargeenoughtoholdthelargestjobnumberforthenxm JSP.Whereas BeirwirthusedaspecialGOXcros- sovertechnique togeneratefeasibleschedule,Fang usedaspecialdecoding approach todecodeachromosome intoa validschedule always.

ThePreferenceListbasedrepresentation(PL)usesastring of operationsforeach machineinsteadof a singlestringforall operationswhichisadirectrepresentation of processingsequencedecisionvariables. Quite oftenviolationofconstraintsisencounteredwhichcanbe overcome byrepair algorithm.

In theMachinebasedrepresentation,[21]thechromosomecontainsastring of lengthequaltothenumber ofmachines.Thesequenceofmachinesinthestringistheorderbywhichamachineistreatedasabottleneck


 

machineinthe shiftingbottleneckalgorithm[12].

IntheJobbasedrepresentation[22] achromosomeisastringoflengthequaltothenumber ofjobsinthe problem understudy.Usingthisrepresentation,asimple algorithmcangenerateafeasibleschedulegivense- quence ofthe jobsonto differentmachines.

 

4.Methodology

 

Thereproductionandmutation operatorsappliedtoJSPmodelaregenerallyadoptedfromTravelling Salesman Problembecause of thesimilarity inrepresentations.Reproductionoperatorsaregenerally requiredinGAto conducttheneighborhoodsearchandamutation operatorgenerallyensuresthatthesolution isnottrappedin localminima.Thedesign of both operatorsiscrucialforthesuccess of GA.Amongthereproduction operators reportedin theliterature, PMX(partiallymatchedcrossover)[23],OX (orderedcrossover)[24]anduniform crossover[25]areextensivelyusedin JSSP.PMXandOX crossovertechniquesuseeithersinglepointortwo pointcrossover.Differentmutation operatorsusedareswapmutation, inversionmutation andinsertion orshift mutationreportedinthe literature[17].

Ingeneral, theflowchartfor GAcanbe representedasshown.

 

5.Results andAnalysis

 

Inourexperiment,fourrepresentationsareusedviz.Operationbased(OB),Jobbased(JB),Machinebased (MB),Priorityrule based (PR). Allexperimentsare conductedwith50generationsanda populationsize of1000. Mutationprobabilityvarieswith 0.1to0.9valuesdynamicallyandelite populationsizeis20%.Reproduction probabilityusedinourexperimentis0.1Parentsinourexperimentareselectedfromtwogroupssortedout basedon fitnessvalue (i.e.minimum makespan). Eachparentisselectedfromthesegroupsprobabilistically.

Inour experimentation,GA isprogrammedwith differentreproductionandmutation operators.Insteadof selectingoperators randomlyas in [17],wehavebuilt-in reproduction operatorsandare beingusedacross the representationsandthebenchmark instances.Thebenchmarkproblemsusedinthispaperaretakenfrom ORli- brary [26]availablein World Wide Web.AlltheexperimentsareconductedwithaPentium-4dualcoreproces- sorwithclockspeed of2.06GHzandRAM of512 Mbs.68benchmarkinstancesare takenandinthe single run, thebestand averagevalues areobtainedandcomparedwith lowerboundoroptimumvalue ofthebenchmark instance.Resultsare showninTable 1. Differentgraphsgeneratedare alsoshownbelow.

 

Table 1.Results ofbenchmarkinstances underdifferentrepresentations.


 

Problem       Size         No.of

Operations


 

BestKnown

Solution


OB         OB            JB              JB            MB          MB          PR        PR Best   Avg.         BestAvg.                 Best         Avg.         Best               Avg.


mt06       6×6          36               55              55        64.889        55         65.712        55         61.822      55    66.648 mt10              10 × 10       100             971       989            1116.02 971               1100.992                         1145.06       958             1100.42 mt20         5× 20        100        1206            1220     1394.47     1206 1383.081245                                1427.24     1242     1426.54 abz05                             10 × 10 100           1259              1275                                1394.79     1259    1386.12                    1287             1409.87                  12671390.94 abz06                               10 × 10      100       971                          958              1072.19971          1075.9996                                1096.13       978      1080.3 abz07                               15 × 20 300                     742         734                                821.16      742     804.892                    751              817.937                  73807.128 abz08                               15 × 20      300       758                          751              833.362758          825.98763                                838.59        755     826.954 abz09                             15 × 20 300                     752         784                                877.468     752     849.838                    773              873.541                    764859.258 car01                               5× 11       55       7038                          7038            8747.847038         8694.017038                                8707.83     7038    8782.28 car02                              4× 13   52             7376              7378            8788.38      7376          8738.23                   7221                           8817    7166          8881.94 car03                               5× 12       60       7725                          7590            9219.197725         9195.367725                                9293.86     7725    9272.51 car04                              4× 14   56             8072              8003            9620.16      8072          9452.62                   8276                         9697.218132            9643.3 car05                                 6× 10       60       7835                          7873            9207.147835         9130.267862                                9251.68     7862      9407 car06                                    9×8    72             8505              8505            10017.7      8505          9886.82                   8505                         10229.58485          9830.33 car07                                 7×7        49       6558                          6576            7673.646558         7782.766627                                7751.89     6632    7738.75 car08                                8×8    64             8407              8407            9436.29      8407          9500.61                   8458                         9470.578366          9470.64 la01                                 5× 10        50        666                            666              783.616666              796.901       674             746.506     666      782.789


 

 

Continued

 

la02

10

50

655

665

748.122

655

774.664

660

745.747

667

757.79

la03

10

50

617

620

688.729

617

687.389

626

690.773

620

699.527

la04

10

50

607

595

695.259

607

690.822

619

699.926

602

688.268

la05

10

50

593

593

640.494

593

658.885

593

606.404

593

699.114

la06

15

75

926

926

1000.79

926

1021.85

926

958.039

926

1075.5

la07

15

75

890

890

998.253

890

1015.05

893

983.784

890

994.044

la08

15

75

863

863

981.109

863

985.795

863

959.264

863

995.054

la09

15

75

951

951

1051.15

951

1084.34

951

988.331

951

1167.81

la10

15

75

958

958

1017.01

958

1045.73

958

971.19

958

1089.97

la11

20

100

1222

1222

1308.89

1222

1334.96

1222

1264.12

1222

1389.85

la12

20

100

1039

1039

1132.34

1039

1157.8

1039

1104.58

1039

1226.58

la13

20

100

1150

1150

1248.7

1150

1278.51

1150

1191.37

1150

1314.64

la14

20

100

1292

1292

1320.59

1292

1348.95

1292

1295.72

1292

1388.82

la15

20

100

1207

1207

1336.66

1207

1352.88

1227

1368.04

1207

1352.41

la16

10 × 10

100

979

982

1083.26

979

1066.88

988

1088.68

987

1071.61

la17

10 × 10

100

797

793

890.389

797

885.073

832

905.275

807

888.012

la18

10 × 10

100

861

861

962.052

861

967.819

885

976.877

883

977.685

la19

10 × 10

100

875

875

970.966

875

972.302

899

983.686

877

976.925

la20

10 × 10

100

936

907

1022.37

936

1040.62

944

1039.52

914

1041.05

la21

10 × 15

150

1105

1098

1252.76

1105

1247.82

1115

1264.74

1111

1281.85

la22

10 × 15

150

972

988

1146.21

972

1125.68

1031

1161.32

990

1133.83

la23

10 × 15

150

1035

1045

1188.52

1035

1168.18

1037

1180.52

1068

1187.63

la24

10 × 15

150

1004

1006

1135.91

1004

1134.02

1029

1155.7

995

1149.69

la25

10 × 15

150

1040

1055

1177.18

1040

1170.37

1036

1175.69

1058

1178.36

la26

10 × 20

200

1269

1279

1457.86

1269

1424.04

1304

1466.35

1310

1446.12

la27

10 × 20

200

1341

1363

1529.94

1341

1500.85

1421

1539.77

1374

1538.38

la28

10 × 20

200

1301

1295

1454.95

1301

1456.94

1334

1463.16

1284

1453.35

la29

10 × 20

200

1274

1302

1441.65

1274

1416.42

1307

1429.08

1270

1425.34

la30

10 × 20

200

1418

1429

1576.32

1418

1554.81

1444

1592.45

1432

1591.74

la31

10 × 30

300

1784

1784

1927.56

1784

1938.51

1785

1934.69

1784

1933.39

la32

10 × 30

300

1850

1850

2019.59

1850

2029.95

1855

2024.57

1853

2031.31

la33

10 × 30

300

1719

1725

1890.07

1719

1873.95

1719

1871.39

1725

1883.41

la34

10 × 30