Det har hävdats att användningen av begränsningsbaserade tekniker och verktyg gör det möjligt att införa exakta, flexibla, effektiva och extensibla schemaläggningssystem: exakta och flexibla eftersom systemet kan ta hänsyn till eventuella begränsningar som kan uttryckas i begränsningsspråket; effektiva i den mån det nu finns mycket optimerade förfaranden för begränsningsutbredning; extensibla eftersom hänsyn till en ny typ av begränsning kan kräva (särskilt i en objektorienterad ram) endast en utvidgning av begränsningssystemet eller, i värsta fall, införandet av ytterligare beslutsmoduler (utan behov av ändring av den befintliga koden). I följande dokument presenteras ILOG SCHEDULE, ett C++-bibliotek som gör det möjligt att representera en bred samling av schemaläggningsbegränsningar när det gäller "resurser" och "aktiviteter". ILOG SCHEDULE är baserad på SOLVER, det generiska programvaruverktyget för objektorienterad begränsningsprogrammering som utvecklats och marknadsförts av ILOG. SOLVER-variabler och begränsningar kan nås från SCHEDULE:s verksamhet och resurser. Som ett resultat kan användaren av SCHEDULE använda sig av SOLVER för att representera specifika begränsningar, och genomföra och kombinera de specifika problemlösningsstrategier som är mest lämpliga för den schemaläggning ansökan som övervägs. Man hoppas - och förväntar sig - att objektorienterade begränsande programmeringsverktyg som SCHEDULE kommer att göra det möjligt för industrin att ta avgörande steg mot genomförandet av "state of the art", mycket flexibla, begränsningsbaserade schemaläggningstillämpningar. 1 I: Intelligent systemteknik, 1994, 3, (2), s. Det är 55-66. -2 - Schemaläggning är processen att tilldela aktiviteter till resurser i tid. Det är en beslutsprocess - processen för att fastställa en tidsplan. En mängd olika begränsningar påverkar denna process: aktivitetstid, utgivningsdatum och förfallodatum, företrädesbegränsningar, överförings- och installationstider, resurstillgänglighetskrav (skiften, stilleståndstid) och resursdelning. Dessa begränsningar definierar utrymmet för godtagbara lösningar. Avslappningsbara preferensbegränsningar kännetecknar dessutom kvaliteten på planeringsbesluten. Dessa preferenser är relaterade till förfallodagar, produktivitet, frekvens av verktygsförändringar, lagernivåer, övertid, etc. Eftersom företrädesbegränsningar kan stå i konflikt med varandra, består lösningen på ett schemaläggningsproblem också i att avgöra vilka preferenser som bör uppfyllas och i vilken utsträckning andra bör mildras. I praktiken kombineras dock ofta preferensbegränsningar antingen till en unik utvärderingsfunktion (eller kostnadsfunktion) för att maximera (eller minimera) eller sammanställas till utvärderingsheuristik för att gynna kandidatlösningar som uppfyller (eller sannolikt kommer att tillfredsställa) preferenserna. I båda fallen definieras schemaläggningsproblemet så småningom som en uppsättning begränsningar för att uppfylla [1]. En lösning på schemaläggningsproblemet är en uppsättning kompatibla schemaläggningsbeslut (t.ex. "perform aktivitet A 2 så snart som möjligt efter aktivitet A 1 på maskin M") som garanterar att begränsningarna uppfylls. Schemaläggningsproblemen skiljer sig mycket från varandra: • För det första kan tre breda familjer av schemaläggningsproblem skiljas åt beroende på graden av frihet när det gäller positionering av resurstillgång och resursefterfrågans intervaller i tiden. I rena schemaläggningsproblem (t.ex. schemaläggning av arbets- och verkstadsmaskiner) definieras varje resurss kapacitet över ett antal tidsintervall och problemet består av positionering av resurskrävande aktiviteter över tid, utan att någonsin överskrida den tillgängliga kapaciteten. Vid problem med ren resursfördelning (t.ex. fördelning av personal till flygplan eller tåg) är efterfrågan på varje resurs känd i förväg och problemet består i att fördela resurser i tid för att garantera att tillgången alltid motsvarar eller överstiger efterfrågan. Vid gemensamma planerings- och resursfördelningsproblem finns det en grad av frihet att bestämma både vilka aktiviteter som ska utföras och när och vilka resurser som ska ställas till förfogande för dessa aktiviteter. -3 - • Olika miljöer utsätts för olika begränsningar som mer eller mindre bidrar till problemets komplexitet. Ett problem med fabriksplanering kan till exempel endast omfatta maskiner som resurser, medan ett annat kan kräva att man tar hänsyn till de mänskliga operatörernas förmågor. Storleken på ett schemaläggningsproblem kan variera från några dussintals aktiviteter till tusentals aktiviteter. Av komplexa skäl kanske de schemaläggningsalgoritmer som fungerar bra för de små problemen inte är tillämpliga på de större problemen. • Viktiga numeriska funktioner i schemaläggningsproblem varierar från en miljö till en annan. I samma miljö varierar de också från problemlösning till problemlösning. Variationen i tillverkningsprocessens varaktighet beror till exempel på de tillverkade produkterna, och vikten av flaskhalsresurser varierar med den globala belastningen i butiken. Återigen, schemaläggning algoritmer som fungerar bra för vissa problem kanske inte är tillämpliga på andra problem. • Beroende på omgivningen kan den lämpliga svarstiden för ett schema variera från några mikrosekunder till några dagar. Det kan också vara nödvändigt att stegvis ändra schemat, antingen som ett svar på miljöförändringar, eller eftersom det är lämpligare för en människa att "göra besluten". Förekomsten av sådana skillnader innebär att strikta schemaläggningsförfaranden, som är utformade för att ge optimala eller nära optimala scheman under särskilda omständigheter, i allmänhet inte är tillfredsställande tillämpliga under andra omständigheter, antingen på grund av att vissa begränsningar (t.ex. mänskliga operatörers förmåga) inte kan beaktas eller på grund av att tillfredsställande scheman inte kan genereras under en godtagbar tidsperiod. Det finns två tänkbara svar på den stora variationen och variationen i schemaläggningsproblemen. Det första är att utveckla mycket flexibla system, vilket gör det möjligt för schemaläggaren att kombinera olika typer av schemaläggnings- och revisionsalgoritmer och dynamiskt anpassa den övergripande schemaläggningsstrategin till den problemlösningssituation som finns. Exempel på flexibla begränsningsbaserade schemaläggningssystem är ISIS [2] [3], OPIS [4] [5], FLYPAST [6], SONIA [1, [7] [8] [9], DAS [10] [11] [12], och senare REDS 2 -4 -systemet Hadavi et al [13]. Intressanta kommentarer om de mest kända systemen och utvecklingen av arbetet inom detta område visas i recensioner av Anne Collinot [7], Peter Burke [10], Pauline Berry [12], Howard Beck [14], Khalil Hindi [15], Patrick Prosser [16], och Claude Le Pape [17]. I detta dokument hävdas att uppkomsten av objektorienterade verktyg för begränsningsplanering medför viktiga möjligheter för det industriella genomförandet av flexibla begränsningsbaserade schemaläggningssystem. Detta påstående stöds av utvecklingen av SCHEDULE, ett bibliotek som gör det möjligt att representera en bred samling av schemaläggningsbegränsningar, och med resultaten av preliminära experiment (som inte återges här utan i tidigare uppsatser [18] [19] [20] ) som omfattar bibliotekets primitiva lågnivå. Ett andra kompletterande svar är att möjliggöra en snabb utveckling och anpassning av effektiva planeringstillämpningar som är inriktade på särskilda problem. I detta perspektiv är ett bibliotek för schemaläggning utan tvekan användbart. Användaren av ett sådant bibliotek måste dock kunna (a) utöka biblioteket för att möjliggöra representation av domänspecifika begränsningar och (b) genomföra och kombinera de specifika problemlösningsstrategier som är mest lämpliga för de aktuella problemen. SCHEDULE är baserat på SOLVER, det generiska programvaruverktyget för objektorienterad begränsningsprogrammering som utvecklats och marknadsförts av ILOG. SOLVER-variabler och begränsningar kan nås från SCHEDULE:s verksamhet och resurser. Som ett resultat av detta drar användaren av SCHEDULE nytta av all flexibilitet och extensibilitet hos SOLVER för att utveckla nya typer av begränsningar och genomföra nya problemlösningsstrategier. I avsnitt 2 presenteras huvudbegreppen begränsningsplanering och diskuteras användningen av dessa begrepp för att utveckla flexibla schemaläggningssystem. I avsnitt 3 beskrivs resurstidstabeller som genomförts i SCHEDULE-biblioteket för att möjliggöra representation av många typer av resursbegränsningar, dvs. begränsningar för resursanvändningen över tid. I avsnitt 4 ges en översikt över SCHEDULE (version 1.0) och i avsnitt 5 ges ett exempel. Slutligen diskuteras i avsnitt 6 möjligheten att förlänga SCHEDULE-biblioteket. -5 - Det huvudsakliga intresset för begränsningsprogrammering ligger i att aktivt använda de begränsningar för att minska den beräkningsansträngning som krävs för att lösa ett problem. Restriktioner används inte bara för att testa en lösnings giltighet, som i konventionella programmeringsspråk, utan också på ett konstruktivt sätt för att fastställa nya begränsningar och upptäcka inkonsekvenser.  I den första typen av modell, som i allmänhet är begränsad till diskreta problem, beskrivs ett problem med begränsad tillfredsställelse som en graf. Noderna i grafen representerar problemvariabler, till vilka ändliga domäner är associerade, och kanterna representerar begränsningarna [21]. • Den andra typen av modell härstammar från logisk programmering, där begränsningslösning kan ses som en förlängning av enandet [22] [23] [24] [25] [26] [27] [28] [29] [30]. • Slutligen består en tredje typ av modell i att särskilja begreppet allmän begränsning (ett samband som till exempel representeras av en klass i ett objektorienterat språk) och begreppet ett exempel på den begränsning som tillämpas på specifika variabler i problemet för att lösa [31] [32] [33] [34] [35]. Den största fördelen med denna typ av modell är att den gör det möjligt för användaren att exakt definiera problemets begränsningar å ena sidan och att genomföra den lämpligaste problemlösningsstrategin å andra sidan. Dessutom möjliggör det en nära integrering av begränsningsbaserade metoder med en objektorienterad programmeringsmiljö [34]. Tillgången till begränsningsutbredningsmetoder i en objektorienterad miljö medför många fördelar för utvecklingen av komplexa schemaläggningstillämpningar. För det första är det lätt att definiera flera klasser av resurser och bifoga lämpliga tvångsförökningsmetoder till varje klass. Exempelvis kan en resurss kapacitet begränsas antingen i termer av makt eller i termer av energi (eller båda). I det första fallet är den tillgängliga effekten när som helst (t.ex. antal maskiner, antal män och kvinnor, elkraft mätt i watt) begränsad. I det andra fallet kan en begränsad mängd energi (t.ex. i persondagar, i watttimmar) användas under ett visst tidsintervall. Låt oss till exempel anta att en resurs består av en grupp på 10 personer, som var och en accepterar att arbeta varje dag (inklusive veckoslutet) men globalt inte mer än 5 dagar varje vecka. Då är den ström som finns tillgänglig varje dag 10 personer, och den energi som finns tillgänglig varje vecka är 50 persondagar. Användningen av flera kategorier av resurser gör det möjligt för schemaläggningssystemet att ta hänsyn till både begränsningar och tillåta samma syntax för att ange att en verksamhet kräver en resurs, oavsett om resurskapaciteten definieras med avseende på kraft eller energi. -7 -Liknande är det lätt att definiera så många resursutnyttjandemönster som behövs för att aktiviteterna ska kunna schemaläggas. Det enklaste fallet är när en aktivitet kräver en fast kvantitet q av en resurs under hela dess utförande. Men många varianter är tänkbara. Till exempel kan en aktivitet definitivt konsumera en resurs. Och en annan kan kräva 2 enheter av en resurs (t.ex. 2 mänskliga operatörer) när den startar, ingen resurs under större delen av dess utförande och 2 enheter av resursen när den slutar. Användningen av ett objektorienterat begränsande-baserat programmeringsverktyg möjliggör organisering av en mängd olika resursutnyttjande begränsningar som underklasser av en rot "resource restriktion" klass. Med andra metoder skulle antingen kod behöva kopieras eller tester måste göras i körtid för att skilja mellan olika typer av resursbehov. Användningen av ett objektorienterat begränsningsbaserat programmeringsverktyg förenklar också genomförandet av flera versioner av en begränsning. "Multiple versions" betyder att den semantiska betydelsen av begränsningen inte ändras från en version till en annan, men varje "version" kan skilja sig från en operativ synvinkel. Till exempel, en version av begränsningen kan stödja icke-monotoniska resonemang medan en annan kanske inte. Den andra versionen kommer att sprida sig mer effektivt och innebära mycket mindre bokföring, men kommer endast att tillåta kronologisk bakåtspårning som reaktion på upptäckta inkonsekvenser. En annan version av begränsningen kan också propagera mer än de andra: lösningen av ett "verkligt svårt" problem [36] kan kräva en stor mängd begränsning förökning (inklusive spridning av överflödiga begränsningar [37] [38] ) medan lösningen av ett enklare problem kan vara snabbare om schemaläggningssystemet kan fatta starkare beslut utan att sprida för mycket efter varje beslut [8]. För att statiskt införa ett begränsande förökningsscenario måste man bara använda motsvarande version av begränsningen. För att dynamiskt införa och uppdatera scenariot måste man bara skapa versioner av intresse (instanser av olika begränsningsklasser) och hämma eller aktivera lämpliga versioner vid lämpliga tidpunkter i problemlösningsprocessen. Mer allmänt ger en objektorienterad begränsningsbaserad formalism ett schemaläggningssystem med mycket flexibilitet längs tre dimensioner: begränsningsrepresentation, problemlösningskontroll och integration med andra system [39] [40]. I samband med ett objektorienterat programverktyg för begränsning leder detta till utformning av olika klasser av begränsningar som motsvarar olika avvägningar mellan precision, effektivitet, flexibilitet och extensibilitet för den slutliga schemaläggningen. Med tanke på en -8 -scheming ansökan, valet (och eventuellt genomförandet) av de mest lämpliga begränsningsklasser är sedan under ansvar av schemaläggningssystemet designer, varje möjligt urval resulterar i olika avvägningar mellan precision, flexibilitet, effektivitet och extensibilitet. Följande avsnitt fokuserar på representationen av resursbegränsningar. Den behandlar de representationer som används i OPIS [4] [5] och SONIA [1, [7] [8] [9], och presenterar den allmänna mekanism som föreslås i SCHEDULE-biblioteket. Två huvudkategorier av begränsningar förekommer i de flesta schemaläggningsproblem: tidsbundna begränsningar och resursbegränsningar. • En tidsbegränsning uttrycks logiskt med en formel (I 1 + d ≤ I 2 ). I 1 och I 2 är tidpunkter, dvs. variabler som representerar starttider eller sluttider för aktiviteter, och d en minimal fördröjning som måste förflyta mellan de två tidpunkterna. I praktiken, spridningen av en sådan begränsning resulterar i en konstant uppdatering av (a) det minimala värdet av I 2, och (b) det maximala värdet av I 1, dvs., i uppdateringen av tidigaste och senaste start- och sluttider av aktiviteter. • En resursbegränsning anger att utförandet av en viss aktivitet kräver (eller tillhandahåller) ett visst belopp (antingen en konstant eller en variabel) kapacitet från en given resurs. Restriktiv spridning sker i båda riktningarna: från resurser till verksamhet, för att uppdatera de tidigaste och senaste start- och sluttiderna för verksamheten, och från verksamhet till resurser för att uppdatera den minimala och maximala kapacitet som kan användas när som helst. Representationen av problem med planering och resursfördelning kräver ofta att det finns tidtabeller för att exakt definiera tillgången på olika typer av resurser över tiden. I detta avseende varierar modelleringskraven att ta hänsyn till när man utformar ett schemaläggningssystem för en viss miljö enormt från en miljö till en annan. -9 - Följande fall representerar tre allt mer komplexa typer av resursanvändningsbegränsningar som man skulle kunna vilja tillämpa: • Fall A. Tillgången på varje resurstyp varierar över tid (t.ex. beroende på skift i en fabrik) oberoende av tillgången på de andra resurstyperna. Det kan till exempel finnas sex personer som arbetar i en tillverkningscell under ett visst veckoskift, och endast tre personer som arbetar under motsvarande veckoslutsskift. • Mål B. Resurstyper aggregeras i mer och mer abstrakta typer, vanligtvis för att möjliggöra representation av resursutbytbarhet. Det kan till exempel finnas sex personer som arbetar i en tillverkningscell under ett visst skift, två som kan driva svarvar och fem som kan använda fräsmaskiner. Det finns i detta fall tre begränsningar att beakta under det givna skiftet: aldrig mer än två svarv samtidigt; aldrig mer än fem fräsningar parallellt; och aldrig mer än sex "slip- eller fräsoperationer" parallellt. • Fall C. Tillgången till en resurstyp vid vissa tidpunkter beror på tillgången till andra resurstyper vid andra tidpunkter. Till exempel kan det vara så att en polyvalent operatör (som kan driva både svarvar och fräsmaskiner) under varje skift måste förbli anvisad till samma typ av maskin, antingen en svarv eller en fräsmaskin. I ett sådant fall gäller ytterligare en begränsning: om operatören vid något tillfälle under skiftet måste tilldelas en svarv, kan han eller hon inte tilldelas en fräsmaskin och omvänt. Övervägandet av dessa exempel får oss att generalisera de tidsplanerade modelleringssystem som tidigare antagits i ett antal flexibla schemaläggningssystem som OPIS [4] [5] och SONIA [1, [7] [8] [9]. Den lösning som antogs i SCHEDULE består av ett mycket generiskt ramverk som gör det möjligt att definiera "variabler" som en del av det objektorienterade programbiblioteket SOLVER (tidigare kallat PECOS [33] [34] ). Semantiskt sett representerar en tabell med variabler en variabel vars värde är en funktion av någon parameter, vanligtvis tid. Därför betraktas tillgången på en resurs som en variabel vars värde så småningom måste vara en funktion som associerar en kvantitet v(t) till varje punkt i tid t. Som vi ska se i avsnitt 3.3, tillåter detta representation av fallen A, B och C ovan. -10 -Avsnitt 3.1 behandlar begränsningsbaserade representationer av tidtabeller som används i OPIS och SONIA, avsnitt 3.2 presenterar den allmänna mekanism som används i SCHEDULE, och avsnitt 3.3 ger information om dess nuvarande genomföranden (i LE-LISP och i C++). Ett antal restriktionsbaserade representationer av resurstidstabeller har beskrivits i litteraturen. Dessa representationer uppnår i stort sett samma mål: begränsningsutbredning genom tidstabellen för en resurs gör det möjligt för schemaläggningssystemet att upprätthålla exakta tidsgränser (tidigare och senaste möjliga start- och sluttider) för de aktiviteter som kräver användning av resursen, och följaktligen för de relaterade aktiviteterna. Den första betydande begränsningsbaserade ramen för representationen av resurstidstabeller utvecklades som en del av ISIS schemaläggningssystem [2] [3]. Denna ram gör det möjligt att specificera förändringar och reservationer för resurser för planerad verksamhet på olika aggregeringsnivåer, dvs. för både enskilda maskiner och homogena arbetsområden som består av likvärdiga eller liknande maskiner. Stephen Smith [41] beskriver den första utformningen av denna ram för vilken en "en oplanerad order i taget" implementation utvecklades. "En oplanerad order åt gången" innebär att begränsningsutbredning utförs för en unik ordning för att schemalägga, d.v.s. att begränsningsutbredningssystemet inte samtidigt kan hantera två oplanerade order. En ny objektorienterad design, som möjliggör ett antal oanmälda beställningar, sattes sedan samman av OPIS-teamet och implementerades av Kevin Neel och Claude Le Pape som en del av OPIS-systemet [42]. Den metod som används i OPIS kan sammanfattas på följande sätt: •
Restriktiv logik programmering tillät genomförande av en mängd olika begränsningar som finns i ILOG Scheduler REF.
Implementation of Resource Constraints in ILOG SCHEDULE: A Library for the Development of Constraint-Based Scheduling Systems
{'venue': 'Intelligent Systems Engineering', 'journal': None, 'mag_field_of_study': ['Computer Science']}