The Chicken Flock Sizing, Allocation and Scheduling Problem - A Mathematical Model and Alternative Heuristic Approaches for Optimization of Broiler Production

Abstract

Produksjon av slaktekylling er en global industri som vokser år etter år. Denne masteroppgaven ser på Norsk Kyllings (NKs) slaktekyllingproduksjon. Flere ledd i verdikjeden er undersøkt, fra mottak av befruktede egg i klekkeriet til fullvoksne slaktekyllinger transporteres til slakteriet. Gjennom vertikal integrering betraktes alle verdikjedeledd samtidig og dette sikrer en helhetlig tilnærming. Formålet med denne oppgaven er å matematisk modellere et optimeringsproblem for slaktekyllingproduksjon, og utvikle løsningsmetoder som løser problemet effektivt. Optimeringsmodeller kan benyttes som et verdifullt verktøy for beslutningsstøtte for produksjonsplanleggere ved NK. Videre kan de foreslåtte modellene og metodene bidra til forskning på optimering av slaktekyllingproduksjon og husdyrproduksjon generelt.

Et statisk og deterministisk optimeringsproblem er modellert i samarbeid med NK. Dette problemet betegnes som innsettsplanleggingsproblemet, på engelsk kalt the Chicken Flock Sizing, Allocation and Scheduling Problem, forkortet CFSASP. CFSASP er matematisk modellert som et blandet heltallproblem som bestemmer innsett av egg, størrelse og allokering av kyllingflokker til slaktekyllingprodusenter og slakteplan. Målfunksjonen minimerer de faktiske kostnadene ved å kaste egg og kompensere gårder som mottar utilstrekkelig mengde kyllinger, og alternativkostnaden for uklekkede egg. Det legges også til en straffekostnad for kyllinger som avviker fra ønsket slaktvekt, og for over- og underlevering til slakteriet. Kapasitetsbegrensninger og industristandarder begrenser mulighetsrommet for lovlige innsetts- og slakteplaner. Et viktig bidrag fra den matematiske modellen er inkluderingen av endeeffekter i overgangen mellom planleggingsperioder.

CFSASP er svært komplekst, og det fullstendige problemet er umulig å løse til optimalitet innen rimelig tid. Derfor har ulike løsningsmetoder blitt utviklet. Heuristikken konstruer- og forbedre (construct-and-improve, forkortet C&I) konstruerer først en rekke mulige løsninger, og forbedrer deretter den best rangerte av disse løsningene ved å bytte om på verdiene til en viss mengde av de binære variablene. Som en alternativ løsningsmetode er heuristikken rullende horisont (rolling horizon heuristic, forkortet RHH) implementert. RHH fikserer gradvis binærvariablene gjennom en iterativ tilnærming som deler planleggingshorisonten i delperioder. Begge løsningsmetodene implementeres ved hjelp av kommersiell programvare, med testinstanser generert fra NKs produksjonsdata. Hensikten med heuristikkene er å redusere beregningstiden samtidig som det opprettholdes tilstrekkelig løsningskvalitet.

De to løsningsmetodene utfyller hverandre i avveiningen mellom løsningskvalitet og løsningstid. C&I heuristikken klarer å løse det fullstendige problemet innen ni minutter. RHH, derimot, krever omtrent 20 timer kjøretid, men oppnår løsninger av betydelig høyere kvalitet. Hvilken løsningsmetode som er best, avhenger av formålet med implementeringen.

En rekke økonomiske analyser har blitt utført ved hjelp av RHH. Et interessant resultat fra disse analysene var at NK kan senke grensen for den tillatte aldersforskjellen mellom foreldrehøner som leverer egg til en kyllingflokk. Dermed kan de oppnå strengt bedre løsninger grunnet lavere dødelighet blant kyllingene. Videre kan endring av ukentlige klekkedager gi betydelige kostnadsbesparelser. Denne potensielle gevinsten må imidlertid vektes mot de eventuelle kostnadene for helgetillegg og ekstra arbeid. Til slutt viste sammenligninger med dagens produksjonsplaner hos NK at løsningen av CFSASP ved hjelp av de foreslåtte løsningsmetodene økte kostnadseffektiviteten betraktelig. Dette siste funnet legger vekt på verdien av optimeringsbasert beslutningsstøtte for planlegging av NKs kyllingproduksjon. Fremtidig forskning bør sikte på videreutvikling og forbedring av både matematisk modell og løsningsmetoder.

The production of broilers, i.e. chickens bred for slaughter, is a global industry growing year by year. This master's thesis examines the case of broiler production at the Norwegian company Norsk Kylling (NK). Several supply chain stages are examined, from reception of fertilized eggs at the hatchery to collection of full-grown chickens for slaughter. Through vertical integration, all these supply chain stages are considered simultaneously. This ensures a holistic approach. The aim of this thesis is to mathematically model an optimization problem for broiler production, and develop solution methods that solve the problem efficiently. Optimization models can serve as a valuable tool for decision support for production schedulers at NK. Furthermore, the proposed models and methods can contribute to research on optimization of broiler production and the livestock industry in general.

A static and deterministic optimization problem is established in collaboration with company representatives from NK. This problem is denoted as the Chicken Flock Sizing, Allocation and Scheduling Problem, abbreviated CFSASP. The CFSASP is mathematically modelled as a mixed-integer problem that determines the incubation of eggs, allocation of chicken flocks to broiler farms, and collection of full-grown chickens for slaughter. The objective function minimizes the actual costs of discarding eggs and compensating farms receiving an insufficient amount of chickens, and the alternative cost of unhatched eggs. In addition, penalty costs are added for chickens deviating from the target slaughter weight, and over- and under-deliveries of demand at the slaughterhouse. Based on ground rules and preferable standards, several constraints restrict the solution space for feasible schedules. An important contribution from the mathematical model is the inclusion of end effects for the transition between planning periods.

The CFSASP is highly complex, and the full-scale problem is impossible to solve to optimality within a reasonable time frame. Therefore, solution methods have been developed. The construct-and-improve (C&I) heuristic first constructs numerous feasible solutions, then improves the best ranked of these solutions through tweaking a certain amount of the binary variables. As an alternative solution method, rolling horizon heuristics (RHHs) are developed. An RHH gradually fixes binary variables through an iterative approach dividing the planning horizon into sub-periods. Both solution methods are implemented using commercial software, with test instances generated from NK's production data. The purpose of the heuristics is to reduce computation time while maintaining sufficient solution quality.

The two solution methods deliver complementary performances regarding the trade-off between solution quality and computation time. The C&I heuristic is able to solve the full-scale problem within nine minutes. The RHH, on the other hand, requires approximately 20 hours of run time, but achieves solutions of significantly higher quality. Depending on the purpose for implementation, different solution methods might be preferable.

A number of economic analyses are performed using the RHH. One interesting finding from these analyses was that NK can enforce stricter age difference limits between parent hens for each chicken flock, and obtain strictly better solutions with lower mortality rates for the chickens. Second, altering the weekly hatching days can yield considerable cost savings. However, this potential gain must be weighted against the potential costs for additional work and higher weekend wages. Lastly, comparisons with NK's current production plans revealed that solving the CFSASP using the proposed solution methods significantly improved cost efficiency. This last finding emphasizes the value of optimization-based decision support for the scheduling of broiler production at NK. Future research should aim towards further development and improvement of both the mathematical model and the solution methods.