💻 computer science

PyCSP3-Scheduling: A Scheduling Extension for PyCSP3

Dit artikel introduceert PyCSP3-Scheduling, een bibliotheek die het PyCSP3-framework uitbreidt met native planningsabstrcties zoals interval- en sequentievariabelen, die worden gecompileerd tot standaard constraints om de scheiding tussen modellering en solver te behouden, terwijl gemengde prestatieresultaten worden aangetoond met aanzienlijke snelheidswinst bij sommige probleemfamilies en regressies veroorzaakt door overhead bij andere.

Oorspronkelijke auteurs: Sohaib Afifi

Gepubliceerd 2026-05-15

📖 4 min leestijd☕ Koffiepauze-leesvoer

CC BY 4.0

Oorspronkelijke auteurs: Sohaib Afifi

Oorspronkelijk artikel gelicentieerd onder CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Dit is een AI-gegenereerde uitleg van het onderstaande artikel. Het is niet geschreven of goedgekeurd door de auteurs. Raadpleeg het oorspronkelijke artikel voor technische nauwkeurigheid. Lees de volledige disclaimer

Stel je voor dat je een meesterkok bent die probeert een enorme, complexe banket te organiseren. Je hebt tientallen gerechten om te bereiden, beperkte fornuizen, specifieke kooktijden en strikte regels over welk gerecht klaar moet zijn voordat een ander kan worden opgediend.

Het Probleem: De "Handmatige" Keuken
Op dit moment, als je de populaire "PyCSP3"-software wilt gebruiken (een krachtig hulpmiddel voor het oplossen van complexe logische puzzels), moet je je keuken beschrijven in zeer laag-niveau termen. Je moet handmatig elke enkele pot, elke seconde kooktijd opschrijven en lange, vermoeiende regels formuleren zoals: "Als Pot A op het fornuis staat, kan Pot B niet op het fornuis staan tenzij Pot A klaar is."

Je moet het volledige schema van scratch opbouwen, baksteen voor baksteen, met behulp van basiswiskunde. Het werkt, maar het is als proberen een roman te schrijven met alleen losse letters zonder woorden of grammaticaregels. Het is makkelijk om een fout te maken, en de instructies worden een rommelige muur van tekst die moeilijk te lezen of te wijzigen is.

De Oplossing: PyCSP3-Scheduling
Dit artikel introduceert een nieuwe "keukenassistent" genaamd PyCSP3-Scheduling. In plaats van je te laten schrijven over elke enkele regel over potten en timers, geeft deze tool je hoog-niveau "slimme ingrediënten":

Intervalvariabelen (De "Slimme Pot"): In plaats van alleen een getal voor tijd, krijg je een "Pot"-object dat zijn eigen starttijd, eindtijd en de benodigde kookduur kent. Het weet zelfs of het optioneel is (misschien hoef je dat gerecht vandaag niet te bereiden).
Sequentievariabelen (De "Vervoerband"): Je kunt potten groeperen in een lijn. De tool weet automatisch dat als Pot A op de band staat, Pot B er niet tegelijkertijd kan zijn. Het regelt zelfs "opsteltijden" (zoals het wassen van de pot tussen gerechten) automatisch.
De Vertaler: Het beste deel is dat deze assistent niet probeert de kok (de solver) te vervangen. Het neemt je hoog-niveau, makkelijk leesbare instructies en vertaalt ze terug naar de laag-niveau, rommelige wiskunde die de computer perfect begrijpt.

Het Experiment: Werkte het?
De auteur testte deze nieuwe tool op 261 verschillende "recepten" (planningsproblemen), variërend van eenvoudige jobshops tot complexe personeelsplanning in ziekenhuizen en toernooiplanning. Ze vergeleken de "Handmatige" methode met de "Slimme Assistent"-methode.

Hier is wat ze vonden:

De Resultaten zijn Identiek: Wanneer de computer het probleem perfect oploste, kregen beide methoden exact hetzelfde antwoord. De vertaling was 100% accuraat.
Snelheid is een Gemengd Pakket:
- De Winsten: Voor sommige problemen (zoals het plannen van vliegtuiglandingen of theaterrepetities) was de nieuwe tool tot 5,8 keer sneller. Het was als overstappen van een fiets naar een sportauto.
- De Verliezen: Voor andere problemen (zoals bepaalde soorten productie of flexibele jobshops) was de nieuwe tool eigenlijk trager.
- Waarom? De auteur legt uit dat soms het "vertaal"-proces te veel extra bagage toevoegt. Bijvoorbeeld, als een probleem "optionele" taken bevat, moet de tool soms duizenden extra "als/dan"-regels uitschrijven om elke mogelijkheid te dekken, wat de computer vertraagt. Het is als een koffer vullen met extra lagen plasticfolie om veilig te zijn; het beschermt de items, maar maakt de koffer zwaar.

De Conclusie
PyCSP3-Scheduling is een brug. Het stelt mensen in staat planningsmodellen op een natuurlijke, logische manier te schrijven (met behulp van "Intervallen" en "Sequenties") zonder de verbinding te verbreken met de krachtige solvers die het zware werk doen.

Het is Open Source: Iedereen kan het gratis gebruiken.
Het is Veilig: Het sluit je niet vast aan één specifiek computerprogramma; het vertaalt je model naar een standaardformaat dat elke compatibele solver kan lezen.
Het is geen Wondermiddel: Hoewel het modelleren voor sommige problemen veel makkelijker en sneller maakt, maakt het niet automatisch elk probleem sneller. In sommige gevallen voegen de extra "vertalingsstappen" een kleine overhead toe.

Kortom, deze tool maakt het werk van de "kok" (de modelleur) veel makkelijker en minder foutgevoelig, zelfs als de "keuken" (de computersolver) soms een paar extra stappen nodig heeft om de nieuwe instructies te verwerken.

Technische Samenvatting: PyCSP3-Scheduling

Probleemstelling

Hoewel PyCSP3 een productieve omgeving biedt voor het modelleren van combinatorische problemen en het exporteren ervan naar de XCSP3-standaard, ontbreekt er native ondersteuning voor hoog-niveau scheduling-abtracties. Momenteel moeten modelleurs schedulingproblemen coderen met behulp van laag-niveau gehele variabelen (starttijden, duur) en handmatig rekenkundige voorrangswaarden en disjuncties voor resourceconflicten construeren. Hoewel PyCSP3 globale constraints biedt zoals NoOverlap en Cumulative op gehele arrays, moet de modelleur expliciet arrays van starttijden, lijsten met duur en resourcehoogtes beheren. Deze benadering verbergt de inherente schedulingstructuur, bemoeilijkt het toevoegen van functies zoals optionaliteit (taken die al dan niet kunnen voorkomen) of sequentie-afhankelijke opstarttijden, en vereist het opnieuw opbouwen van coderingen vanaf nul voor nieuwe modellen. Bestaande industriële hulpmiddelen (bijv. CP Optimizer) bieden schedulingobjecten, maar koppelen modellen vaak aan specifieke, soms commerciële, oplosprogramma's, terwijl zelfstandige talen zoals MiniZinc geen intervalvariabelen van het eerste niveau hebben.

Methodologie

Het artikel introduceert PyCSP3-Scheduling, een bibliotheek die PyCSP3 uitbreidt met een dedicated schedulinglaag. De kernmethodologie omvat:

Abstractielaag: De bibliotheek introduceert twee primaire variabeletypes:
- IntervalVar: Representeert een taak met attributen voor start, einde, grootte (duur) en aanwezigheid. Het ondersteunt vijf varianten: Vast, Flexibel, Optioneel, Gebonden en Geschaald (koppeling van duur aan intensiteitsprofielen).
- SequenceVar: Groepeert een lijst van intervalvariabelen in een geordende sequentie, die doorgaans een disjunctieve resource (bijv. een machine) voorstelt, en ondersteunt sequentietijden die afhankelijk zijn van het type.
Compilatieschema: De bibliotheek introduceert geen nieuwe oplosprogramma-backend. In plaats daarvan compileert deze hoog-niveau abtracties naar standaard PyCSP3-variabelen en -constraints, die vervolgens worden geëxporteerd als standaard XCSP3-instanties.
- Directe Mapping: Wanneer patronen overeenkomen met bestaande globale constraints (bijv. verplichte intervallen zonder overgangen), genereert de bibliotheek standaard XCSP3-globals zoals noOverlap en Cumulative.
- Decompositie: Voor complexe gevallen (bijv. optionele intervallen met aanwezigheidswachters of sequentie-afhankelijke opstarttijden) decomposeert de bibliotheek abtracties naar primitieve constraints. Bijvoorbeeld, SeqNoOverlap met optionele intervallen valt terug op $O(n^2)$ paarsgewijze disjuncties bewaakt door aanwezigheidsliterals, aangezien de huidige XCSP3-standaard geen optionele intervallen in globale constraints ondersteunt.
- Hybride Modelleren: De laag is ingebed binnen PyCSP3, waardoor modelleurs hoog-niveau schedulingconstructen kunnen mengen met ruwe PyCSP3-constraints (bijv. het gebruik van presence_of om aangepaste tellogica te activeren).
Expressiesysteem: De bibliotheek biedt accessors (start_of, end_of, presence_of, enz.) die PyCSP3-expressies retourneren, waardoor complexe rekenkundige en logische combinaties direct op intervalattributen mogelijk zijn.

Belangrijkste Bijdragen

Het artikel levert drie specifieke bijdragen:

Een Scheduling-API: Een uitgebreide API voor PyCSP3, gecentreerd rond interval- en sequentie-abtracties, met ondersteuning voor optionaliteit, intensiteitsfuncties en sequentievorming die rekening houdt met overgangen.
Een Compilatieschema: Een mechanisme dat deze abtracties verlaagt naar oplosprogramma-onafhankelijke PyCSP3/XCSP3-constraints, terwijl vervulbaarheid en optimaliteit behouden blijven.
Empirische Evaluatie: Een rigoureuze vergelijking van 261 gepaarde instanties (klassieke PyCSP3-formulering versus schedulingformulering) over 17 modelfamilies.

Resultaten

De evaluatie werd uitgevoerd op 261 gepaarde instanties met de ACE-oplosser en een time-out van 1200 seconden. Belangrijkste bevindingen zijn:

Semantische Correctheid: Op de 72 instanties waarbij beide formuleringen optimaliteit bewezen, kwamen de doelwaarde exact overeen (100%), wat bevestigt dat de compilatie geen semantische divergentie introduceert.
Toestemming Oplosprogramma-status: De twee formuleringen kwamen in 80,8% van de paren overeen over de oplosprogramma-status (Optimum, Sat, Unsat, Time-out). Oneenigheden waren voornamelijk te wijten aan verschillen in zoekvoortgang gerelateerd aan time-out in plaats van logische fouten.
Prestatievariatie: De prestaties in runtime varieerden aanzienlijk tussen families:
- Winsten: Drie families lieten duidelijke snelheidswinsten zien: MSPSP (5,82×), AircraftLanding (3,47×) en Rehearsal (3,31×). De winst bij MSPSP werd toegeschreven aan artefacten in variabele volgorde in de PyCSP3-variabele declaratie in plaats van aan de abtracties zelf, terwijl AircraftLanding en Rehearsal profiteerden van een verkleinde modelgrootte en een betere structurele vastlegging.
- Achteruitgangen: Drie families vertoonden achteruitgang: LotSizing (0,29×), MRCPSP (0,61×) en FlexibleJobshopScen (0,89×).
  - De achteruitgang bij MRCPSP werd teruggevoerd naar de compilatie van optionele intervallen die terugvallen op paarsgewijze disjuncties in plaats van het genereren van een globale noOverlap-constraint, wat efficiënte propagatie verhinderde.
  - De achteruitgang bij LotSizing was gerelateerd aan coderingsproblemen op constraintniveau en propagatiesterkte onder time-out.
  - FlexibleJobshopScen leed onder significante structurele uitbreiding (explosie van variabelen en constraints) door het dupliceren van optionele beslissingen over scenario's heen.
Structurele Impact: 8 van de 17 families toonden een verwaarloosbare structurele uitbreiding (<1% verandering). Voor anderen verkleinde de schedulingformulering soms de modelgrootte (bijv. BACP, Rehearsal) en vergrootte deze soms aanzienlijk (bijv. FlexibleJobshopScen +383,7% constraints).

Betekenis en Claims

Het artikel positioneert PyCSP3-Scheduling als de eerste schedulinglaag die first-class IntervalVar- en SequenceVar-abtracties biedt met optionaliteit en sequentievorming die rekening houdt met overgangen, terwijl het compileert naar een oplosprogramma-onafhankelijke standaard (XCSP3).

De auteurs benadrukken dat de bibliotheek de volledige scheiding tussen modelleren en oplossen behoudt, een kernbeginsel van het PyCSP3-ecosysteem. Dit stelt modellen in staat bruikbaar te blijven met een breed ecosysteem van oplosprogramma's (ACE, Choco, CoSoCo, OR-Tools, CP Optimizer, enz.) zonder aanpassingen.

Het artikel is bescheiden wat prestatieclaims betreft, met de opmerking dat runtime-winsten niet universeel zijn en vaak gekoppeld zijn aan specifieke probleemstructuren of oplosprogramma-heuristieken (bijv. variabele volgorde). De auteurs stellen expliciet dat de significante snelheidswinst bij MSPSP waarschijnlijk een artefact is van patronen in variabele declaratie in plaats van de schedulingabtracties zelf. De primaire waardepropositie is de expressiviteit en onderhoudbaarheid van de schedulingformulering, die de codecomplexiteit verlaagt (bijv. een reductie van 31% in regels voor een flexibel job-shop-model) en het toevoegen van functies zoals optionaliteit vereenvoudigt, zelfs als dit soms een compilatie- overhead met zich meebrengt die de runtime-prestaties op specifieke probleemfamilies beïnvloedt.

Toekomstig werk wordt geïdentificeerd als het uitbreiden van de compilatie om XCSP3-globale constraints met optionaliteitsondersteuning te genereren (om paarsgewijze decompositie te vermijden) en het verfijnen van compilatieregels om structurele overhead in afwijkende families te verminderen.