I detta dokument beskrivs en genetisk algoritm strategi för ett personalplaneringsproblem som uppstår på ett större brittiskt sjukhus. Även om Genetiska Algoritmer har använts framgångsrikt för liknande problem i det förflutna, de alltid varit tvungna att övervinna begränsningarna i den klassiska Genetiska Algoritmer paradigm för att hantera konflikten mellan mål och begränsningar. Den metod som används här är att använda en indirekt kodning baserad på permutationer av sjuksköterskorna, och en heuristisk dekoder som bygger scheman från dessa permutationer. Beräkningsförsök baserade på 52 veckors levande data används för att utvärdera tre olika dekodrar med olika nivåer av intelligens, och fyra välkända crossover operatörer. Resultaten förbättras ytterligare genom att införa en hybrid crossover operatör och genom att använda enkla gränser för att minska storleken på lösningen utrymme. Resultaten visar att den föreslagna algoritmen kan hitta högkvalitativa lösningar och är både snabbare och mer flexibel än en nyligen publicerad Tabu Search approach. Nyckelord: Genetiska algoritmer, Heuristik, Manpower Scheduling. Under de senaste åren har Genetiska algoritmer (GAs) blivit allt populärare för att lösa komplexa optimeringsproblem som de som finns inom schemaläggning eller tidsplanering. Tyvärr finns det inget fördefinierat sätt att inkludera begränsningar i god jordbrukshävd och goda miljöförhållanden. Detta är förmodligen en av deras största nackdelar, eftersom det inte gör dem lätt tillgängliga för de flesta verkliga problem världen optimering. Det finns vissa metoder för att hantera begränsningar, särskilt straff- och reparationsfunktioner. Men som Michalewicz [1] konstaterade är deras tillämpning och framgång problemspecifik. Här använder vi ett alternativt tillvägagångssätt: de genetiska operatörerna agerar på ett okonstruerat lösningsutrymme vars element omvandlas till lösningar av en schemabyggare som fungerar som dekoder för GA. Vårt arbete skiljer sig från tidigare studier med hjälp av en liknande strategi på två sätt. För det första används begränsningar aktivt för att vägleda heurismen att minska beroendet av strafffunktioner. Problemets natur innebär dock att det inte är möjligt för schemabyggaren att garantera genomförbara lösningar, och en stor del av vår utredning handlar om att hitta det bästa sättet att balansera de motstridiga frågorna om genomförbarhet och lösningskostnader. För det andra undersöker vi effektiviteten hos olika permutationscrossover operatörer för genomförandet av denna typ, och följaktligen införa en hybrid crossover som kombinerar de önskvärda egenskaperna hos de två bästa. Det arbete som beskrivs i detta dokument har två syften. Den första är att utveckla en snabb, flexibel lösning till en sjuksköterska rostning problem och den andra, att öka mängden kunskap om att lösa begränsade problem med hjälp av GAs. Även om det finns många publicerade algoritmer för sjuksköterska schemaläggning, vissa egenskaper hos vårt särskilda problem, som beskrivs i nästa avsnitt, göra dessa metoder olämpliga för oss. En omfattande sammanfattning av dessa metoder finns i Hung Utan dessa funktioner, ungefär en tredjedel av fallen krävde flera timmars körtid för att hitta bra genomförbara lösningar. På grund av de höga kostnaderna för sådan programvara, är detta inte en praktisk lösning för många sjukhus. Dowsland [8] 3 löser problemet med hjälp av en Tabu Search-strategi. Hennes resultat är imponerande i att lösa fall som uppstår på ett visst sjukhus, men är mindre bra på data med olika egenskaper. Det tillvägagångssätt som användes här motiverades av tidigare forskning om en lösning på problemet med god jordbrukshävd och goda miljöförhållanden. Aickelin och Dowsland [9] visar att ett enkelt genomförande av god jordbrukshävd och goda miljöförhållanden inte kan lösa problemet. Tillägg av problemspecifik information, i form av samevolverande delpopulationer och en modifierad fitnessfunktion i kombination med en intelligent bergsklättrare, ger rimliga lösningar på mycket kort tid. Lösningens kvalitet är dock inte konsekvent och ändringarnas karaktär innebär att metoden kanske inte är robust när det gäller små ändringar i problemspecifikationen. Därför finns det fortfarande utrymme för förbättringar. Här använder vi en annan strategi för en GA-strategi, där individerna i befolkningen inte representerar direkta kodningar av lösningar. Istället erhålls lösningar via separat dekoderheuristik som bygger lösningar från permutationer av listan över tillgängliga sjuksköterskor med hjälp av begränsningarna som guider. Dessa permutationer manipuleras av GA. Fördelen med denna strategi är att god jordbrukshävd och goda miljöförhållanden kan förbli kanoniska, dvs. Det löser ett obestämt problem och kräver ingen bergsklättrare eller annan problemspecifik kunskap. Observera att strafffunktioner fortfarande kan krävas om dekodern misslyckas med att hitta en genomförbar lösning. Detta gör också algoritmen mer flexibel än de integrerade tillvägagångssätt som beskrivs ovan, eftersom GA-komponenten kan förbli oförändrad om problemet ändras, t.ex. om det finns nya begränsningar eller mål. Tanken på en indirekt GA är inte ny, och liknande metoder har använts för andra problem, till exempel Davis [10] och Palmer och Kershenbaum [11]. Det finns dock en stor skillnad mellan vårt arbete och deras: Sjuksköterskans schemaläggningsproblem är inte ett enkelt permutationsproblem som schemaläggning av arbetsplatser utan har ytterligare begränsningar och därför kan våra dekodrar inte garantera att alltid ta fram genomförbara lösningar. Därför finns det fortfarande en del arbete att utföra genom en strafffunktion. Våra beräkningsförsök är utformade för att undersöka denna aspekt av genomförandet, samt undersöka påverkan av valet av heuristisk dekoder och crossover operatör på lösning hastighet och kvalitet. Resultatet är en algoritm som fortfarande är enkel men tillräckligt robust för att klara av denna ogenomförbarhet. Detta uppnås genom att hitta en balans mellan de stokastiska elementen i GA och den deterministiska karaktären hos den föreslagna dekodern. Våra viktigaste verktyg för detta är fastställande av parametervärden, beslut om genetiska strategier och hitta en lämplig dekoderfunktion. Det listande problem som tas upp i detta dokument kan beskrivas på följande sätt. Uppgiften är att skapa veckovisa scheman för avdelningar med upp till 30 sjuksköterskor genom att tilldela en av ett antal möjliga skiftmönster till varje sjuksköterska. Dessa scheman måste uppfylla arbetskontrakten och tillgodose efterfrågan på ett visst antal sjuksköterskor av olika lönegrader vid varje skift, samtidigt som personalen i fråga ska anses vara rättvis. Det senare målet uppnås genom att uppfylla så många av sjuksköterskornas önskemål som möjligt och beakta historisk information för att säkerställa att otillfredsställda förfrågningar och impopulära skift fördelas jämnt. Problemet kompliceras av att högre kvalificerade sjuksköterskor kan ersätta mindre kvalificerade sjuksköterskor men inte tvärtom. Därför är det inte möjligt att planera de olika betygen självständigt. Dessutom har problemet en särskild dag-natt struktur eftersom de flesta sjuksköterskor kontrakteras att arbeta antingen dagar eller nätter i en vecka men inte båda. På grund av arbetsavtal är dock antalet arbetade dagar vanligtvis inte detsamma som antalet nätter. Därför blir det viktigt att schemalägga de "rätta" sjuksköterskorna på dagar respektive nätter. Det är de två sistnämnda egenskaperna som gör detta problem utmanande för alla lokala sökalgoritmer eftersom det är extremt svårt att hitta och underhålla genomförbara lösningar. Dessutom, på grund av denna speciella struktur tidigare sjuksköterska schemaläggning algoritmer som föreslås i litteraturen kan inte användas. Ytterligare detaljer om planläggningsproblemet finns i Aickelin och Dowsland [9]. Som beskrivs i Dowsland och Thompson [12] kan problemet brytas ned i tre oberoende faser. Det första steget säkerställer att det finns tillräckligt många sjuksköterskor för att ge tillräckligt skydd. Den andra etappen tilldelar sköterskorna rätt antal dag- eller nattskift. I en slutfas fördelas de som arbetar på en viss dag till ett tidigt eller sent skift den dagen. Faserna 1 och 3 löses enkelt med hjälp av klassiska optimeringsmodeller. Detta dokument behandlar därför det mycket begränsade andra steget. Antalet dagar eller nätter som ska arbetas av varje sjuksköterska definierar uppsättningen genomförbara veckoarbetsmönster för den sjuksköterskan. Dessa kommer att kallas skiftmönster eller skiftmönster vektorer i följande. För varje sjuksköterska i och varje skift mönster j all information om önskvärdheten av mönstret för denna sjuksköterska fångas i en enda numeriska preferens kostnad p ij. Detta gjordes i nära samråd med sjukhuset och är en viktad summa av följande faktorer: Grundläggande skift-mönster kostnad, allmänna dag / natt preferenser, specifika önskemål, kontinuitetsproblem, antal på varandra följande arbetsdag, roterande nätter / helger och annan arbetstid historia information.
Till exempel har särskilda kodningssystem utvecklats för att utnyttja problemspecifik kunskap när man tar itu med ett starkt begränsat problem i verkligheten, såsom sjuksköterskelistan REF.
An Indirect Genetic Algorithm for a Nurse Scheduling Problem
{'venue': 'Computers&Operations Research, 31(5), pp 761-778, 2004', 'journal': None, 'mag_field_of_study': ['Computer Science']}