Decision support for generator maintenance scheduling in the energy sector
Date
2011-12
Authors
Schlunz, Evert Barend
Journal Title
Journal ISSN
Volume Title
Publisher
Stellenbosch : Stellenbosch University
Abstract
ENGLISH ABSTRACT: As the world-wide consumption of electricity continually increases, more and more pressure is
put on the capabilities of power generating systems to maintain their levels of power provision.
The electricity utility companies operating these power systems are faced with numerous challenges
with respect to ensuring reliable electricity supply at cost-e ective rates. One of these
challenges concerns the planned preventative maintenance of a utility's power generating units.
The generator maintenance scheduling (GMS) problem refers to the problem of nding a schedule
for the planned maintenance outages of generating units in a power system (i.e. determining
a list of dates corresponding to the times when every unit is to be shut down so as to undergo
maintenance). This is typically a large combinatorial optimisation problem, subjected to a
number of power system constraints, and is usually difficult to solve.
A mixed-integer programming model is presented for the GMS problem, incorporating constraints
on maintenance windows, the meeting of load demand together with a safety margin,
the availability of maintenance crew and general exclusion constraints. The GMS problem is
modelled by adopting a reliability optimality criterion, the goal of which is to level the reserve
capacity. Three objective functions are presented which may achieve this reliability goal; these
objective functions are respectively quadratic, nonlinear and linear in nature.
Three GMS benchmark test systems (of which one is newly created) are modelled accordingly,
but prove to be too time consuming to solve exactly by means of an o -the-shelf software
package. Therefore, a metaheuristic solution approach (a simulated annealing (SA) algorithm)
is used to solve the GMS problem approximately. A new ejection chain neighbourhood move
operator in the context of GMS is introduced into the SA algorithm, along with a local search
heuristic addition to the algorithm, which results in hybridisations of the SA algorithm.
Extensive experiments are performed on di erent cooling schedules within the SA algorithm,
on the classical and ejection chain neighbourhood move operators, and on the modi cations
to the SA algorithm by the introduction of the local search heuristic. Conclusions are drawn
with respect to the e ectiveness of each variation on the SA algorithm. The best solutions
obtained during the experiments for each benchmark test case are reported. It is found that
the SA algorithm, with ejection chain neighbourhood move operator and a local search heuristic
hybridisation, achieves very good solutions to all instances of the GMS problem.
The hybridised simulated annealing algorithm is implemented in a computerised decision support
system (DSS), which is capable of solving any GMS problem instance conforming to the general
formulation described above. The DSS is found to determine good maintenance schedules when
utilised to solve a realistic case study within the context of the South African power system.
A best schedule attaining an objective function value within 6% of a theoretical lowerbound, is
thus produced.
AFRIKAANSE OPSOMMING: Met die wêreldwye elektrisiteitsverbruik wat voortdurend aan die toeneem is, word daar al hoe meer druk geplaas op die vermoë van kragstelsels om aan kragvoorsieningsaanvraag te voldoen. Nutsmaatskappye wat elektrisiteit opwek, word deur talle uitdagings met betrekking tot betroubare elektrisiteitsverskaffing teen koste-e ektiewe tariewe in die gesig gestaar. Een van hierdie uitdagings het te make met die beplande, voorkomende instandhouding van 'n nutsmaatskappy se kragopwekkingseenhede. Die generator-instandhoudingskeduleringsprobleem (GISP) verwys na die probleem waarin 'n skedule vir die beplande instandhouding van kragopwekkingseenhede binne 'n kragstelsel gevind moet word ('n lys van datums moet tipies gevind word wat ooreenstem met die tye wanneer elke kragopwekkingseenheid afgeskakel moet word om instandhoudingswerk te ondergaan). Hierdie probleem is tipies 'n groot kombinatoriese optimeringsprobleem, onderworpe aan 'n aantal beperkings van die kragstelsel, en is gewoonlik moeilik om op te los. 'n Gemengde, heeltallige programmeringsmodel vir die GISP word geformuleer. Die beperkings waaruit die formulering bestaan, sluit in: venstertydperke vir instandhouding, bevrediging van die vraag na elektrisiteit tesame met 'n veiligheidsgrens, die beskikbaarheid van instandhoudingspersoneel en algemene uitsluitingsbeperkings. Die GISP-model neem as optimaliteitskriterium betroubaarheid en het ten doel om die reserwekrag wat gedurende elke tydperk beskikbaar is, gelyk te maak. Drie doelfunksies word gebruik om laasgenoemde doel te bereik (naamlik doelfunksies wat onderskeidelik kwadraties, nie-lineêr en lineêr van aard is). Drie GISP-maatstaftoetsstelsels (waarvan een nuut geskep is) is dienooreenkomstig gemodelleer, maar dit blyk uit die oplossingstye dat daar onprakties lank gewag sal moet word om eksakte oplossings deur middel van kommersiële programmatuur vir hierdie stelsels te kry. Gevolglik word 'n metaheuristiese oplossingsbenadering ('n gesimuleerde temperingsalgoritme (GTA)) gevolg om die GISP benaderd op te los. 'n Nuwe uitwerpingsketting-skuifoperator word in die konteks van GISP in die GTA gebruik. Verder word 'n lokale soekheuristiek met die GTA vermeng om 'n basteralgoritme te vorm. Uitgebreide eksperimente word uitgevoer op verskeie afkoelskedules binne die GTA, op die klassieke en uitwerpingsketting-skuifoperators en op die verbasterings van die GTA meegebring deur die lokale soekheuristiek. Gevolgtrekkings word oor elke variasie van die GTA se e ektiwiteit gemaak. Die beste oplossings vir elke toetsstelsel wat gedurende die eksperimente verkry is, word gerapporteer. Daar word bevind dat die GTA met uitwerpingsketting-skuifoperator en lokale soekheuristiek-verbastering baie goeie oplossings vir die GISP lewer. Die verbasterde GTA word in 'n gerekenariseerde besluitsteunstelsel (BSS) geïmplementeer wat 'n gebruiker in staat stel om enige GISP van die vorm soos in die wiskundige programmeringsmodel hierbo beskryf, op te los. Daar word bevind dat die BSS goeie skedules lewer wanneer dit gebruik word om 'n realistiese gevallestudie binne die konteks van die Suid-Afrikaanse kragstelsel, op te los. 'n Beste skedule met 'n doelfunksiewaarde wat binne 6% vanaf 'n teoretiese ondergrens is, word ondermeer bepaal.
AFRIKAANSE OPSOMMING: Met die wêreldwye elektrisiteitsverbruik wat voortdurend aan die toeneem is, word daar al hoe meer druk geplaas op die vermoë van kragstelsels om aan kragvoorsieningsaanvraag te voldoen. Nutsmaatskappye wat elektrisiteit opwek, word deur talle uitdagings met betrekking tot betroubare elektrisiteitsverskaffing teen koste-e ektiewe tariewe in die gesig gestaar. Een van hierdie uitdagings het te make met die beplande, voorkomende instandhouding van 'n nutsmaatskappy se kragopwekkingseenhede. Die generator-instandhoudingskeduleringsprobleem (GISP) verwys na die probleem waarin 'n skedule vir die beplande instandhouding van kragopwekkingseenhede binne 'n kragstelsel gevind moet word ('n lys van datums moet tipies gevind word wat ooreenstem met die tye wanneer elke kragopwekkingseenheid afgeskakel moet word om instandhoudingswerk te ondergaan). Hierdie probleem is tipies 'n groot kombinatoriese optimeringsprobleem, onderworpe aan 'n aantal beperkings van die kragstelsel, en is gewoonlik moeilik om op te los. 'n Gemengde, heeltallige programmeringsmodel vir die GISP word geformuleer. Die beperkings waaruit die formulering bestaan, sluit in: venstertydperke vir instandhouding, bevrediging van die vraag na elektrisiteit tesame met 'n veiligheidsgrens, die beskikbaarheid van instandhoudingspersoneel en algemene uitsluitingsbeperkings. Die GISP-model neem as optimaliteitskriterium betroubaarheid en het ten doel om die reserwekrag wat gedurende elke tydperk beskikbaar is, gelyk te maak. Drie doelfunksies word gebruik om laasgenoemde doel te bereik (naamlik doelfunksies wat onderskeidelik kwadraties, nie-lineêr en lineêr van aard is). Drie GISP-maatstaftoetsstelsels (waarvan een nuut geskep is) is dienooreenkomstig gemodelleer, maar dit blyk uit die oplossingstye dat daar onprakties lank gewag sal moet word om eksakte oplossings deur middel van kommersiële programmatuur vir hierdie stelsels te kry. Gevolglik word 'n metaheuristiese oplossingsbenadering ('n gesimuleerde temperingsalgoritme (GTA)) gevolg om die GISP benaderd op te los. 'n Nuwe uitwerpingsketting-skuifoperator word in die konteks van GISP in die GTA gebruik. Verder word 'n lokale soekheuristiek met die GTA vermeng om 'n basteralgoritme te vorm. Uitgebreide eksperimente word uitgevoer op verskeie afkoelskedules binne die GTA, op die klassieke en uitwerpingsketting-skuifoperators en op die verbasterings van die GTA meegebring deur die lokale soekheuristiek. Gevolgtrekkings word oor elke variasie van die GTA se e ektiwiteit gemaak. Die beste oplossings vir elke toetsstelsel wat gedurende die eksperimente verkry is, word gerapporteer. Daar word bevind dat die GTA met uitwerpingsketting-skuifoperator en lokale soekheuristiek-verbastering baie goeie oplossings vir die GISP lewer. Die verbasterde GTA word in 'n gerekenariseerde besluitsteunstelsel (BSS) geïmplementeer wat 'n gebruiker in staat stel om enige GISP van die vorm soos in die wiskundige programmeringsmodel hierbo beskryf, op te los. Daar word bevind dat die BSS goeie skedules lewer wanneer dit gebruik word om 'n realistiese gevallestudie binne die konteks van die Suid-Afrikaanse kragstelsel, op te los. 'n Beste skedule met 'n doelfunksiewaarde wat binne 6% vanaf 'n teoretiese ondergrens is, word ondermeer bepaal.
Description
Thesis (MSc)--Stellenbosch University, 2011.
Keywords
Maintenance -- Planning, Computer integrated manufacturing systems, Simulated annealing, Energy industries, Theses -- Logistics, Dissertations -- Logistics