2.Thesis 2

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. Ga’sare 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 begroupedintotwobasicencodingapproaches—directandindirect 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.

Let“J” representasetofjobsandeachjobwillbe processedona setof machines ina particular order. LetI=

(1…..v)representtheoperationindexes.Theoperationindexesareassignedsuchthatfora job

k ∈ J,the subset

ofconsecutiveindexes  Ik   =

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

⊆I,isasubsetcontainingindexesforthatjob.Nowfrom

thesubsetIk   dependingonthepriorityoperationwithhigherorlowervalueisprocessedfirst.Letpi   bethe

processingtimeofithoperation,thejobwhichitbelongstoisj(i)andthemachineonwhichithoperationcar-

riedism(i).

Now theobjectiveofschedulingprocessistodeterminethestarttimesti  ofanoperation

i∈I.Whileassign-

ingajobtoamachinebasedonabovecalculationsfollowingconstraintsshouldbetakenintoconsiderationviz.

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

and

sti   +pi   ≤sti+1..Is the equation to satisfytechnologicalconstraints

(1)

sti   ≥stj   +pj   Or

stj    ≥sti   +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=n   

∑ fi  (C) =∑ fi  (Ci) …IscalledSumObjective.

i=1

The  most  common  objective  functions  are  the  make  span  max

{(Ci) i= 1,,n}

and  total  flow  time

n

∑(Ci ) ,andweighted(total)flowtime

i =1

n

∑ wi   ⋅ Ci   .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. ThisistotheMannes’model.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…ifoperation ‘i’isprocessed onmachine‘m’ inunittime ‘t’

=0...otherwise.

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

m

i,l

= 1…ifoperation‘i’takes‘ith’positioninthe processingsequence onmachine ‘m’

=0...otherwise.

processedpriorto operation ‘j’onmachinem.

m

i,j

=1…ifoperation‘i’is

= 0...otherwise.

3.Representationofthe Problem inGA andGA Operators

Darwin’sprinciple“survivalofthefittest”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 GAoperators’viz.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(n−1)entries(p1, p2…pn)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 proposedatechnique“permutationwith repetition”[20]which issimilartooperation basedrepresen- tation.Fang[21]alsoproposed akindoperation basedrepresentationwherestringcontainsnxmchunkswhich arelargeenoughtoholdthelargestjobnumberforthenxm JSP.Whereas BeirwirthusedaspecialGOXcros- sovertechnique togeneratefeasibleschedule,Fang usedaspecialdecoding approach todecodeachromosome intoa validschedule always.