Universiteit Twente

Cyclische schedules voor transportsystemen
WN 01/35 * 14 juni 2001
promotie mw. ir. C.M.H. Kuijpers, faculteit Toegepaste Wiskunde: Cyclic Machine Scheduling with Tool Transportation In moderne productieomgevingen bevinden zich vaak zeer geavanceerde machines die een groot aantal verschillende bewerkingen uitvoeren en daarbij gebruik maken van allerlei verschillende gereedschappen. Deze gereedschappen zijn soms erg kostbaar. Daarom gebruikt men een gereedschap vaak voor meerdere machines. Er is dan een transportsysteem aanwezig om de gereedschappen tussen de machines heen en weer te transporteren. Zon transportsysteem kan een robot of een lopende band zijn, maar ook een persoon. Als het transportsysteem te laat met een gereedschap bij een machine aankomt, kan de betreffende machine niet verder gaan met de volgende geplande bewerking en komt hij stil te staan. Om de productie te maximaliseren moeten de machines en het transportsysteem dus zo op elkaar worden afgesteld dat de machines zoveel mogelijk kunnen blijven werken. Kuijpers bestudeerde het schedulingprobleem (planningsprobleem) dat optreedt in de hierboven omschreven productieomgevingen. Zij onderzocht vooral cyclische schedules voor dit probleem. Cyclische schedules hebben de eigenschap dat zij geen echt begin- of eindpunt hebben, maar continu kunnen worden herhaald. Het doel is om de gemiddelde productie per tijdseenheid te maximaliseren. Het algemene probleem wordt gemodelleerd als een zogeheten geheeltallig programmeringsprobleem. Voor productieomgevingen met precies twee machines worden allerlei eigenschappen van optimale schedules afgeleid. Voor zulke omgevingen blijkt er altijd een optimaal schedule van een bepaalde structuur te bestaan. Dit resultaat heeft Kuijpers gebruikt voor het ontwikkelen van een algoritme dat veel sneller een optimaal schedule oplevert dan gebeurt wanneer het geheeltallige programmeringsprobleem op een standaardmanier wordt opgelost. Ook wordt een heel snelle heuristiek (benaderingsalgoritme) gegeven, die in vrijwel alle gevallen een optimaal schedule oplevert. promotor prof. dr. U. Faigle
co-promotor dr. ir. W.M. Nawijn
informatie drs. B. Meijering