We are interested in a job-shop scheduling problem corresponding to an industrial problem. Gantt diagram’s optimization can be considered as an NP-difficult problem. Determining an optimal solution is almost impossible, but trying to improve the current s

184A.Cardonetal./RoboticsandAutonomousSystems33(2000)179–190

6.2.EquivalentSOP2:TheconstraintapproachTheconstraintapproach[16,19]isbasedonthefol-lowingparametrizedminimumproblem:Pk( ):minx∈X

fk(x),

(6)

subjecttofj(x)≤ j,j=1,...,nandj=k,where =( 1,..., n)T∈Rnisthevectorofparameters.Themainadvantageofthisapproachisthatconvex-ityassumptionsarenotrequired.ThereforeallParetooptimalsolutionscanalwaysbediscoveredbysolv-ingtheconstraintproblemPtheMOPk( )foranyk.Thecorre-spondencebetweenandtheSOPissubjecttothe0followingrules.

IfxisanoptimalsolutionofPfeasible,thenk( 0x)0with 0avec-torforwhichPk( 0)isisanondomi-natedsolutionoftheMOP,ifoneofthetwofollowingconditionsoccurs:

x0isauniquesolutionofPk( 0)forsomegivenkbetween01andn.

xisnotunique,butsolvesP,n.

k( 0)foreachandeveryk=1,...Onthecontrary,ifx isanondominatedsolutionoftheMOP,an canalwaysbefoundsuchthatx istheoptimalsolutionofPkk( )for =1,...,nfor.Inallfact,i=this1,...condition,nwithiseachi=veri edandeveryk.wheni=fi(x )6.3.Resultsfromthegeneticalgorithm

Fromourobjectmodelization,ageneticalgorithmusingtheplacingmethodhasbeendeveloped[24,47].ThisprogramusestheC++languageinordertouseitonanSGIOrigin2000.Herearesomebenchmarks(seeTable1).

Asthecomputationaltimedependsonthecom-puterloading,thisrealtimedoesnotcorrespondto

Table1

BenchmarkresultsNumberofNumberofNumberofCalculationjobsoperationsmachinestime

1010450s

50549min,53s5010414min,27s100101040min,58s500

100

50

2h,24min,7

s

Fig.2.Dataextraction

software.

Fig.3.Tardinessasafunctionofthenumberofgenerations.

theCPUtime(Fig.2).Wecanthendetermineheuris-tics[8,9,24],tousewithourdynamicmodelbasedonthecontract-netprotocol[40,48].Anotherresultcomingfromthesimulationprocessisasetofgraphsgivingthetardinessandtheadvanceasafunctionofthenumberofgenerations.Wecanseethatthedelaydecreasesrapidly.Butitisnotnecessarytoincreasethenumberofgenerationstoobtainabetterresult(Fig.3).

6.4.Problemsencountered

Inourproblem,the rstlevelofmodelizationwasastaticmodel.Itdoesnottakeintoaccountthefactthatwehaveinteractionsbetweenmachinesandjobs.Ajobcanbedoneonlyiftheresourceisfree.