Abstrakt. Att beräkna snäva resursnivåer är ett grundläggande problem vid uppbyggnaden av flexibla planer med resursutnyttjande. I den här artikeln beskriver vi en effektiv algoritm som bygger ett resurskuvert, så snävt som möjligt. Algoritmen är baserad på att omvandla tidsnätet av resurskrävande och producera händelser till ett flöde nätverk med noder lika med händelser och kanter lika med den nödvändiga föregångaren länkar mellan händelser. Ett iscensatt problem med maximalt flöde på nätverket används sedan för att beräkna tidpunkten för förekomst och höjden på varje steg i resurskuvertprofilen. Varje steg har samma computational komplexitet för att lösa ett maximalt flöde problem på hela flödesnätet. Detta gör denna metod möjligt att beräkna och lovande för användning i den inre slingan av flexibla schemaläggningsalgoritmer. Att bibehålla tidsflexibiliteten i verksamhetsplanerna är viktigt för att hantera osäkerheten i genomförandet. Flexibla planer möjliggör till exempel ett uttryckligt resonemang om exogena händelsers tidsmässiga okontrollerbarhet [11] och ett sömlöst införlivande av genomförandemotåtgärder. Tidsscheman för viss tid (dvs. tilldelningen av en exakt start- och sluttid till alla aktiviteter) är spröda och det är vanligtvis mycket svårt att exakt följa dem under utförandet. Ett exempel på effekten av fasta tidsscheman i en intelligent avrättningssituation är "Skylab-strejken" [6], när astronauterna under Skylab 4-uppdraget gick på en sit-down-strejk efter 45 dagar för att försöka komma ikapp de exakta kraven på ett snabbt tempo med ingen flexibilitet för dem att anpassa sig till rymdmiljön. Ett stort hinder för att använda flexibla scheman är dock fortfarande svårigheten att beräkna den mängd resurser som behövs för alla deras möjliga utföranden. Detta problem är särskilt svårt för resurser med flera kapaciteter (t.ex. elkraft) som kan konsumeras och produceras i alla mängder genom samtidig verksamhet. Tekniker har utvecklats [5] [10] för att ge försiktiga uppskattningar av de resursnivåer som krävs enligt ett flexibelt schema, vilket ger både en övre gräns och en lägre gränsprofil på resursnivån över tid. I samband med en systematisk sökmetod för att bygga flexibla planer kan resursnivågränser användas vid varje söksteg enligt följande: a) som ett backtrackingtest, dvs. för att avgöra när det nedre/övre bundet intervallet ligger utanför intervallet för tillåtna resursnivåer vid någon tidpunkt och därför är inga fasta tidsinstanser i planen resursgenomförbara, och b) som ett test för att avsluta sökningen, dvs. för att avgöra när det nedre/övre bundet intervallet är inom intervallet för tillåtna resursnivåer vid alla tidpunkter och därför är alla tidsinstanteringar i planen resursgenomförbara. Gränstäthet är extremt viktig beräkning eftersom en snäv gräns kan spara en potentiellt exponentiell mängd sökning (genom tidig backtracking och lösningsdetektering) jämfört med en lösare gräns. I detta dokument diskuterar vi hur man kan beräkna resursnivån, dvs. måttet på maximal och minimal resursförbrukning vid alla
Begreppet "envelope" har införts i REF, där författaren behandlar schemaläggningen av ett tidsnät med bitvis bestående resurser.
Computing the envelope for stepwise-constant resource allocations
{'venue': 'Proceedings of the 9th International Conference on the Principles and Practices of Constraint Programming', 'journal': None, 'mag_field_of_study': ['Computer Science']}