チェン．1ウ CHENGYu Particularpartwithoutviolatingconstraints・However，fbrreal

(1)

日本オペレーションズ・リサーチ学会

2004年秋季研究発表会 2−B−4

ConstraintProgrammlng−basedSchedulingCooperatedwithRules−basedSystems ●

03000500アイログ（株）

1 Introduction

This paper introduces a new approach，Which cooperates COnStraint programmlng−based scheduling with rules−based SyStemS tO fbrm a new application丘amework fbr soIvlng manufactunng scheduling problems．By this approach，

COnStraintprogramm1ng−basedschedulingcanprovidefヒasible andgoodsolutionstoaschdulingproblem，Whilefast−Changlng business conditions have impact upon the problem can be managedbytheru1e−basedsyetem．Itcanalsobeintegratedto aninteractiveGraphicalUserInterface（GUl）builtwithGantt Charttoprovidemoreuser−fhendlyinteractiveinterfacetothe businessusers．Themaintenanceofthebusinessobjectmodel andrulesusedbytheschedulingenglneCanbesupportedviaa rule editor syetem，enabling the agility to modifybusiness modelsandpoliciesunderfast−Changingbusinessconditions・

2 ScheduIingproblemandsolutionapproaches

The task of scheduling is to produce the detailed plan of productionactivities（SuChasassembling，maChining，Chemical

reactions，mixing，forTingorseparating）ondiffbrentmachines

Or PrOductionlines，1n Order to efnciently produce quality 爪nishedproductsinatimelymanner，Whilesatisfyingcustomer demandforthennishedproduct．ThisrequlreSthescheduling

englne tO generate the best valid scheduling dedicated fbr VariouscriterionandtherequlrementS丘ombusinessusersand atthesametimesatisfyallthepossibleconstraintsduringthe PrOductionprocesses．

2．1 Various＄Olutionapproaches

There basica11y exist three difrtrent paradigmsfor soIvlng SChedulingproblems．

・ Rule−basedsystemsamdheuristic−basedapproach Traditionally，ru1e−based systems have been used to store SCheduling heuristic asrules，Which are used as scheduling algorismsfbrgeneratesolutions．Inparticularcases，itisalso usedasatoolforcheckingfeasibleschedulingsolutionsorfor nndingoutanyviolatedconstraintsinasolution．Basically，this approachrequlreStheru1edatabasetogrowwiththeknowledge

ru1eandheuristicnewlyacquiredandcanleadtohuge，barely manageablesystems．Asknowledgeru1eandheuristicusually evoIvequiterapidly，beingupdatedweeklyandevendailywith SOmeOnlineservices，maintainlngSuCharu1ebasecanquickly

become an extremely difnculttask．Besides，Whenru1e−based SyStemSareuSedasschedulingalgorismstogeneratesolutions，

itishardtoadequate fbrmostcomplexscheduling scenarios and specinc constraintsin the processes of manufacturlng Operations．Forthesereasons，rule−basedsystemaloneusedas SChedulingalgorismsiscurrentlyloslnggrOund．

● Procedure−basedapproach

Intheprocedure−basedapproach，theschedulingproblemsare described as a specinc mathematicalmodel，Or a Simulation model，OraloglCalmodelinacomputerprogram．TosoIvethe PrOblem，thesystemmustdescribewhattodoandhowtosoIve asastepby stepprocedure，1ike howto selectqrgeneratea

チェン．1ウ CHENGYu

Particularpartwithoutviolatingconstraints・However，fbrreal SChedulingproblems，itisusuallyadifnculttasktomakesuch kinds of solving procedures when too rnany complex

constraitsandschedulingscenariosneedstobeconsideredat thesametime．Particularly，Whensomecriticalconstraintsare Violated，thesoIvingproceduresshouldberepeatagain丘om thestart．Thecomputlngtimecouldbeincreasedsignincantly

Whentoomanyofsuchkindsofbacktrackingcomputation・

・ Constraintprogrammlng−basedapproach

Scheduling problems can be treated as a particulartype of Constraint Satisfaction Problem（CSP）．With Constraint Programming（CP）technology，itis essentialpossible and efficienttodetectandremoveinfbasible（Orbad）schedulings 丘om the solution space．This can be done easily with COnStraint propagation algorithms．Itis also possible to COmputetheuser sbestschedulingintermSOfcost，qualityor deliverytlme．However，WithCPapproachonly，1tisnoteasy tocaptureconstantlychanglngbusinessconditions，tOObtain highperformanCeOfmaintainlngthechanglngOfrequlrementS

from business users，SuCh as schedulingru1es，POlicies or COnStraints spec摘ed by business users・For axample，aS a SCheduling result，itis obviously reqired to satisfyallthe demand required by business users，tO make allthe orders

froma11thecustomers．However，uSually，nOtallthecustomers and their orders have equalpriority．For axample，loyal CuStOmerSWith1arge orders，nOtSurPnSlngly，Shouldreceive higherpriority．Thisdescribesapotentialbusinesspolicythat theschedulingsystemmustattempttoadhereby．Interestlngly，

POlicieslike this constantly change，are abandoned，Or are newlycreated．UnfbrtunatelywithCPapproachonly，mOSt SyStemShavelimitednexibilitytohandlethesechanges，and

theresultisthatanynewormodifiedbusinesspoliciescannot berenectedinproductionschedulesimmediately・

2．2 CPplusrule−basedapproach−aninnovativeapproach Whileru1e−based system and CP may seem similarfrom a

highlevel，they requitediffbrentintermsoftheteclm0logleS and their applicable uses．Itis commOnly accepted that

ru1e−basedsystemsapproachisnotadequatefbrmostcomplex SChedulingscenarios，WhichisthereasonoptlmizationenglneS basedonCParecurrentlyconsideredthestateoftheart．CP technologygivestheenduserstheabilitytointeractwitha SCheduling englnein the method they prefbr，rather than a predeterminedpathdevelopedwith abusiness−rulemodeler，

However，maintenanceonschedulingapplicationsconsidered exceptlOnally costly and consistently higher than expected・

Rule−based systems p？Vide fbatures fbr siTPlifying

SChedulingapplicationmalntenanCeandreducingmalntenanCe COStSWiththerespecttothechangeofbusinesspolices・Thus，

Obviously，a neW aPprOaCh is to use constraint PrOgrammlng−based scheduling cooperated withrules−based SyStemS，WhichusesbothofthetwotechnologleStOgether，and Whichallowsbusiness users to change schedulingru1es and

use CP technology to provide s．01utions，Which satisfythe

−208−

(2)

COnStraintsrespectlngtOtheru1es．

3 CPCooperatedwithrules−basedsystemsapproach

3．1Schedulingproblemmodeling：CPenglnepart

WithCPplusru1e−basedapproach，the schedulingproblemis representedbyasetofvariables，Witheachvariablehavinga SPeCi坑ed domain ofpossible values．The businessrules or SO−Called schedulingru1es thatdescribe the regulations to be respectedarefbrmulatedasconstraintsamongthosevariables．

TheCPenglneaPPliesthedomainreductiontothevariablesby identifying and removing values that maylead to aninvalid SCheduling．Thesealgorithmsareca11edconstraintpropagation algorithms．The constraint propagation algorithms are embeddedintoasystematictraversaloftherelevantpartsofthe

SOlution space，Whichis organizedin atree．This enablesthe SyStemtOahtomaticallyperfbrmbacktrackingsteps，lmPlement flexiblesearchstrategleS，findoptlmalschedulings．Besides，the number of possible scheduling solutions may become

extremelylargefbrcomplexproblems．Asaconsequence，itis necessary to approprlately guide the search to obtain good SCheduling solutions．This can be done via search strategleS．

StrategleSCOntrOltheorderinwhichdecisions，i．e．，thetrylng Ofthevariouspossiblevaluesforeachfield，aremade．WithCP Plusru1e−basedapproach，PrOblem−SpeCinc strategleSCanalso bedennedbyrules．

3．2 Schedulingbusinessrulemodeling：rule−basedpart Theru1e−basedsystemmanages a1lofthebusinessru1esthat Canbeappliedbothonthemodelobjectsandexternalsetsof datarelatedtothescheduling．Thus，SChedulingrequlrementS Canbedescribedasru1estostate

Hardconstraintsarefbrmulatedviastrictbusinessru1es，SuChas HshouldM orりshould not ．Softconstraints are fbrmulatedin termsofwishesよndprefbrences．Awishcharacterizesadesire

thattheuserwouldliketoachieve，butitmaycontradictsome Otherrules．Preftrencesmakeitpossiblefortheusertoindicate that a choice in a scheduling should be made over another duringanautomaticsearch．A1lofthemcanbeformulatedina

ru1e−1ikesyntax．

3．3Stepsforapplicationdesignandimplementation

Unlikerule−basedsystemswhoseenglnereaSOnSdirectlyonthe application o旬ects，an aPplication with CP plusru1e−based approachiscenteredontheschedulingenglneandmusthaveits OWnO句ectmodeldefinitionandinstances．Becauseofthis，the firstandmostimportant／criticalstepindesignlnganaPPlication

isthedennitionoftheBusine戸SObjectModel（BOM），Which

describestheapplicationdomalnObjectsandtheirrelations．

ThesecondstepIStOWritethesetofschedulingrulesuslngthe BusinessConstraintLanguage（BCL）．Herealso，aSOPPOSedto ru1e−based systems，this set ofru1es does not express the PrOCeSS Ofnnding a solution but the set ofconstraints the SCheduling englne Willenfbrce fbrpossible solutionsifsuch exists．Thus，thedesignandimplementationphasecanbeseen asiterationoverthesetwosteps．

3．4 FunctionalityarChitecture

The framework provides the fo1lowlng 丘velevels of functionality，Summarizedinthearchitectureasbelow：

1）InteractiveGanttchart：Visualize，analyze，interactand updateproductionschedules

2）Optimizationalgorithms：generatefbasible，low−COSt detailedschedules

3）Maintenanceandschedulinginterface：mOdifyobject model，ru1esandalgoritlmparametersovertime 4）0句ectmodel：mOdelandcaptureintricaciesofthe

manufacturing operation

5）Externalintegration：1everagepre−dennedintegrationto existlngeXternalERP／SCMsystem

3．5IntegratedDevelopmentEnvironment

With CP plusru1e−based approach，both problem modeling andrulesmanagementshouldbehandled．Acompletesetof productivltytOOIswouldbehelpfu1，Whichallowsbothsystem developersandbusinessuserstographicallyedit，manageand testschedulingmodelandrelatedrules．Themqjorfunctions oftheIDEinclude：

・Object ModelEditor：graPhicaleditor fbr easily designlng the scheduling modelstruCture，and editing and managlngSChedulingo句ectsandrelationships；

・Scheduling Rule Builder：intuitive editor thatlenables non−teChnicaluserstoeditschedulingbusinessrules；

・Scheduling Rule Management：the Rule Builder also PrOvides tooIs to store，VerSion，query，manage and deploy SChedulingbusinessrules；

・GraphicalUserInterface（GUI）：a1lowsonetointeract

andtovisualizethesolutions丘omtheschdulingenglne．It has been configured to display the problem objective Weightsinchart，aSWellasthesolutioninaganttview，a resource usage view and an objective view as well as editingfunctions．

4 Remarks

This paperpromotes and suggests a nexible，POWerfu1 COnStraint programmlng−based scheduling cooperated with rules−based systems approach to s（）1ve complex manufacturlng SCheduling problems．With the constraint PrOgrammlng−based teclm0logy，itis easier and faster to modelandsoIvearesource−COnStrainedschedulingproblem，

to reduce complexityofthe problem by various kinds of COnStraint propagation．With the ru1es−based systems teclmology，it canobtain highperfbrmance dfmaintainlng thechanglngOfschedulingrequlrementS，andalltheru1es

Can be dynamica11y created or changed through an

interactive polnt−and−Click editor．Thus，it allows business usersornonprogrammerstoexpressschedulingru1esinan intuitive way．Meanwhile，OPtlmization，Visualization，and businessru1esteclmologleSareuSedandmakeitasarich，

POWerfu1pre−integrated applicationframework．For more infbrmationaboutrelatedtechnologleS，itisrecommendedto haveavisittohttp：／／www．ilog．cojp／toknowmoredetail．

5 Rerbrence

［l］OptimizationTechnologyWhitePaper，ILOqInc・200l・

【2］ILOGSoIver，UserManual，VerSion6．0，2003．

【3］ILOGScheduler，UserManual，VerSion6．0，2003．

［4］ILOGJRules，UserManual，VerSion4．5，2003．

−209−