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

A.Cardonetal./RoboticsandAutonomousSystems33(2000)179–190183

isavectorofnrealvaluescomingfromobjectivefunctions,xisavectorofnvariablesofdecisionandX={x|x∈Rm,gk(x) 0,

k=1,...,m,andx∈S}

(3)

isasetofpossiblesolutions.gkisarealfunctionvaluerepresentingmthekthconstraintandSisasubsetofRrepresentingalltheotherformsofconstraints.Theidealsolutiontosuchaproblemisapointwhereeachobjectivefunctioncorrespondstothebest(minimum)possiblevalue.Theidealsolutioninmostcases,doesnotexistinviewofcontradictoryobjectivefunctionsandhencecompromiseshavetobemade.Adiffer-entconceptofoptimalityhastobeintroduced.Solv-inganMOPgenerallyrequirestheidenti cationofParetooptimalsolutions[33],aconceptintroducedbyV.Pareto,aprominentItalianeconomistattheendofthelastcentury.AsolutionissaidtobeParetoopti-mal,ornondominated,ifstartingfromthatpointinthedesignspace,thevalueofanyoftheobjectivefunctionscannotbeimprovedwithoutdeterioratingatleastoneoftheothers.AllpotentialsolutionstotheMOPcanthusbeclassi edintodominatedandnon-dominated(Paretooptimal)solutions,andthesetofnondominatedsolutionstoanMOPiscalledParetofront.The rstandmostimportantstepinsolvinganMOPisto ndthissetorarepresentativesubset.Af-terwardsthedecisionmaker’spreferencemaybeap-pliedtochoosethebestcompromisesolutionfromthegeneratedset.Thenaturalorderingofvectorval-uedquantitiesisbasicforParetooptimality.Tode nethenotionofdomination,letf=(fg=(g)betworeal-valuedvectors1,...,offnn)and1,...,gmele-ments:fispartiallysmallerthangif: i∈1,...,nand k∈1,...,m,fg,wei≤saygkand i|fthatfdominatesi≤gk,wenotef<pg.Iff<pg.Con-sequently,afeasiblesolutionx issaidtobeaParetooptimaloftheproblemifandonlyifanotherx∈Xdoesnotexistsuchthatf(x)<pf(x ).6.DevelopmentofParetooptimalsolutionsTwodifferentstrategiesareeffectiveingeneratingParetooptimalsolutions[12,16].Inthe rststrategy,anappropriatescalaroptimizationproblem(SOP)[42]isset-upinparametricform,sothatthesolutiontothe

SOPwithgivenvaluesoftheparameters,undercer-tainconditions,belongstotheParetofront;changingtheparametersoftheSOPleadsthesolutiontomoveonthefront.Inthesecondone,theMOPissolvedwithadirectapproachusingthedominancecriteria,sothatasetofParetooptimalsolutionsisdevelopedsimultaneously.Themainadvantageofthe rststrat-egyisthatSOPsaregenerally,verywell-studiedprob-lemsandmanyef cientmethodsareavailabletosolvethem.

6.1.EquivalentSOP1:TheweightingapproachFollowingtheweightingapproach[16],theMOP[42]ismadetocorrespondtothefollowingparametrizedSOP:P(w):minwT

f nx∈X

(x)=

wjfj(x),(4)

j=1

where

w∈W=

w|w∈Rn,wj(x) 0,

n j=1,...,nand

w

j=1j=1

,

(5)

thecorrespondencebetweentheMOPandtheSOPissubjecttosomerules.Ifx0isanoptimalsolutionofP(w0),thenitisalsoParetooptimalifoneofthetwofollowing0conditionsisveri ed:

xistheuniqueoptimalsolutiontoP(w0w0);isstrictlypositive.

ThisimpliesthatatleastsomeParetooptimalso-lutionscanbegeneratedbysolvingP(w)forsomeproperlychosenw,withoutanyhypothesisonthecon-vexityofXandf(X).Instead,someconvexityhy-pothesesareanecessitycondition.Therefore,ifbothXandf(X)areconvex,thenforanygivenParetoop-timalsolution,x ,itispossibleto ndaweightvectorw,notnecessarilyunique,suchthatx isasolutiontoP(w).Therefore,whentheseconvexityassumptionsareveri ed,allParetooptimalsolutionscan,inthe-ory,befoundbyvaryingwandsolvingP(w),whileiftheyarenotveri ed,someParetooptimalsolutionsmayneverbediscoveredbythisprocedure.