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

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

1.1.Job-shopschedulingproblem

Schedulingisanessentialfunctioninproductionmanagement.Itisadif cultproblemdependingonthenumberofcalculationsrequiredtoobtainaschedul-ingthatoptimizesthechosencriterion[37].Inaddi-tion,therearemanyschedulingproblemsandvariousapproachmethodshavebeenproposedtosolvesomepartsofthem.Wearegoingtode neourschedulingproblemanddescribesomeexistingproblemsaswellastheconstraintsthatweconsidered.

Amongvariousde nitionsoftheschedulingprob-lem,wecanhighlightacommondenominator:itisthetaskallocationwithaminimumcostandinareason-abletime.Weareinthe eldofdiscontinuousproduc-tionwiththeprocessingofsmallandaverageseries.Aschedulingproblemexists:

whenasetoftasks(jobs)istobeprocessed;

whenthisproblemcanbebrokenupintotasks(operations);

whentheproblemconsistsinthede nitionofthetemporaltasklocationand/orthemannertoallocatethemtothenecessaryresources.

Lamy[34]de nestheschedulingproblemofdiscon-tinuousproduction:“Theschedulingproblemoftheproductionconsistsinmanufacturingatthesametime,withthesameresources,asetofdifferentproducts.”Schedulingdetermineswhatisgoingtobemade,when,whereandwithwhatresources;givenaset

of

taskstoaccomplish,theschedulingproblemconsistsindeterminingwhatoperationshavetobeexecutedandingivingdatesandresourcesfortheseoperations.1.2.Ourjob-shopschedulingproblem

Schedulingandplanningaredif cultproblems[34,37]withalongandvariedhistoryintheareasofoperationalresearchandarti cialintelligence,andtheycontinuetobeactiveresearchareas.Theschedulingproblem,whichissubjecttoprecedenceandresourceconstraints,isanNP-dif cultproblem[13].Itisthusimpossibletoobtainanoptimalsolu-tionsatisfyingtherealtimeconstraint.

So,heuristicalgorithmsareusuallyimplementedtoobtaina“good”solutioninsteadofanoptimalone[34,50].Duetothenumberofvarietiesofproductionprocessesandtheincreasingrateofchangeinoper-ationalparameterscharacterizingthedatatobepro-cessed(capacitiesoftheresources,demands,etc.),itisbecomingmoreandmoredif cultformanagementboardstomakedecisions.

ThereasonthatwehavechosentheJSSPwithMmachinesandNjobsisbecauseitisthemostcom-plexandthemostoftenconsidered[10].Todeterminethequalityofthesolution,agraphicalinterfacehasbeendeveloped(Fig.1).Forourproblem,thegoalistheminimizationofdelaysandadvancesforalljobsaccordingtothe“duedates”givenbythemanager

Fig.1.GraphicalinterfaceusedforourJSSP.