Genetic algorithms using multi-objectives

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

RoboticsandAutonomousSystems33(2000)

179–190

Geneticalgorithmsusingmulti-objectives

inamulti-agentsystem

AlainCardona,ThierryGalinhob,Jean-PhilippeVacherc,

b

LIP6ParisVI,UPMC,Case69,4,PlaceJussieu,75252ParisVI,France

LIH,InstitutSupérieurd’EtudesLogistiques,QuaiFrissard,BP1137,76063LeHavreCedex,FrancecLIH,InstitutUniversitairedeTechnologie,PlaceRobertSchuman,BP4006,76610LeHavre,France

Received1January1999;receivedinrevisedform1May1999;accepted1December1999

a

Abstract

Weareinterestedinajob-shopschedulingproblemcorrespondingtoanindustrialproblem.Ganttdiagram’soptimizationcanbeconsideredasanNP-dif cultproblem.Determininganoptimalsolutionisalmostimpossible,buttryingtoimprovethecurrentsolutionisawayofleadingtoabetterallocation.Thegoalistoreducethedelayinanexistingsolutionandtoobtainbetterschedulingattheendoftheplanning.

Weproposeanoriginalsolutionbasedongeneticalgorithmswhichallowstodetermineasetofgoodheuristicsforagivenbenchmark.Fromtheseresults,weproposeadynamicmodelbasedonthecontract-netprotocol.Thismodeldescribesawaytoobtainnewschedulingswithagentnegotiations.Weimplementtheagentparadigmonparallelmachines.

Afteradescriptionoftheproblemandthegeneticmethodweused,wepresentthebenchmarkcalculationsthathavebeenperformedonanSGIOrigin2000.Theinterpretationoftheseisawaytore neheuristicsgivenbyourevolutionprocessandawaytoconstrainouragentsbasedonthecontract-netprotocol.ThisdynamicmodelusingagentsisawaytosimulatethebehaviorofentitiesthataregoingtocollaboratetoimprovetheGanttdiagram.©2000ElsevierScienceB.V.Allrightsreserved.

Keywords:Job-shopschedulingproblem;Multi-objectivegeneticalgorithm;Multi-agentsystem;Contract-netprotocol

1.Introduction

Inthejob-shopschedulingproblem(JSSP),Ganttdiagram’soptimizationcanbeconsideredasanNP-dif cultproblem[10].Determininganoptimalsolutionisalmostimpossible,buttryingtoimprovethecurrentsolutionisawayofleadingtoabetterallocation.Multi-agentsystems[15]areoftenused

ExpandedversionofatalkpresentedattheSecondInterna-tionalSymposiumonIntelligentManufacturingSystems,IMS’98,SakaryaUniversity,Turkey,6–7August1998. Correspondingauthor.

E-mailaddresses:alain.cardon@lip6.fr(A.Cardon),thierry.galinho@univ-lehavre.fr(T.Galinho),jean-philippe.vacher@poleia.lip6.fr(J.-P.Vacher).

forsuchproblems,whereasolutionexistsbutisnoteasilycalculable[52–55].Weexpectsomesolutiontoemergefromsuchsituations,thatisthereasonwhyweusethem.Weusethemtosimulatethebehaviorofentitiesthataregoingtocollaboratetoaccom-plishactionsontheGanttdiagramsoastosolveagiveneconomicfunction.Theidealsolutiontosuchaproblemisapointwhereeachobjectivefunctioncorrespondstothebest(minimum)possiblevalue.WepresentourJSSP,whichisasimpli edversionofFISIAS[41].Wepresentsomeresultsbasedonge-neticalgorithms[50],thenwepresentanagentmodelbasedonthecontract-netprotocoltoimproveasolu-tioncorrespondingtoaGanttdiagram.

0921-8890/00/$–seefrontmatter©2000ElsevierScienceB.V.Allrightsreserved.PII:S0921-8890(00)00088-9