mdh.sePublikationer
Ändra sökning
RefereraExporteraLänk till posten
Permanent länk

Direktlänk
Referera
Referensformat
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Annat format
Fler format
Språk
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Annat språk
Fler språk
Utmatningsformat
  • html
  • text
  • asciidoc
  • rtf
A Study of Combinatorial Optimization Problems in Industrial Computer Systems
Mälardalens högskola, Akademin för innovation, design och teknik.ORCID-id: 0000-0003-1597-6738
2009 (Engelska)Doktorsavhandling, sammanläggning (Övrigt vetenskapligt)
Abstract [en]

A combinatorial optimization problem is an optimization problem where the number of possible solutions are finite and grow combinatorially with the problem size. Combinatorial problems exist everywhere in industrial systems. This thesis focuses on solving three such problems which arise within two different areas where industrial computer systems are often used. Within embedded systems and real-time systems, we investigate the problems of allocating stack memory for an system where a shared stacks may be used, and of estimating the highest response time of a task in a system of industrial complexity. We propose a number of different algorithms to compute safe upper bounds on run-time stack usage whenever the system supports stack sharing. The algorithms have in common that they can exploit commonly-available information regarding timing behaviour of the tasks in the system. Given upper bounds on the individual stack usage of the tasks, it is possible to estimate the worst-case stack behaviour by analysing the possible and impossible preemption patterns. Using relations on offset and precedences, we form a preemption graph, which is further analysed to find safe upper-bounds on the maximal preemptions chain in the system. For the special case where all tasks exist in a single static schedule and share a single stack, we propose a polynomial algorithm to solve the problem. For generalizations of this problem, we propose an exact branch-and-bound algorithm for smaller problems and a polynomial heuristic algorithm for cases where the branch-and-bound algorithm fails to find a solution in reasonable time. All algorithms are evaluated in comprehensive experimental studies. The polynomial algorithm is implemented and shipped in the developer tool set for a commercial real-time operating system, Rubus OS. The second problem we study in the thesis is how to estimate the highest response time of a specified task in a complex industrial real-time system. The response-time analysis is done using a best-effort approach, where a detailed model of the system is simulated on input constructed using a local search procedure. In an evaluation on three different systems we can see that the new algorithm were able to produce higher response times much faster than what has previously been possible. Since the analysis is based on simulation and measurement, the results are not safe in the sense that they are always higher or equal to the true response time of the system. The value of the method lies instead in that it makes it possible to analyse complex industrial systems which cannot be analysed accurately using existing safe approaches. The third problem is in the area of maintenance planning, and focus on how to dynamically plan maintenance for industrial systems. Within this area we have focused on industrial gas turbines and rail vehicles.  We have developed algorithms and a planning tool which can be used to plan maintenance for gas turbines and other stationary machinery. In such problems, it is often the case that performing several maintenance actions at the same time is beneficial, since many of these jobs can be done in parallel, which reduces the total downtime of the unit. The core of the problem is therefore how to (or how not to) group maintenance activities so that a composite cost due to spare parts, labor and loss of production due to downtime is minimized. We allow each machine to have individual schedules for each component in the system. For rail vehicles, we have evaluated the effect of replanning maintenance in the case where the component maintenance deadline is set to reflect a maximum risk of breakdown in a Gaussian failure distribution. In such a model, we show by simulation that replanning of maintenance can reduce the number of maintenance stops when the variance and expected value of the distribution are increased.  For the gas turbine maintenance planning problem, we have evaluated the planning software on a real-world scenario from the oil and gas industry and compared it to the solutions obtained from a commercial integer programming solver. It is estimated that the availability increase from using our planning software is between 0.5 to 1.0 %, which is substantial considering that availability is currently already at 97-98 %.

Ort, förlag, år, upplaga, sidor
Västerås: Mälardalen University Press , 2009.
Serie
Mälardalen University Press Dissertations, ISSN 1651-4238 ; 79
Nationell ämneskategori
Datavetenskap (datalogi)
Forskningsämne
datavetenskap
Identifikatorer
URN: urn:nbn:se:mdh:diva-7381ISBN: 978-91-86135-47-8 (tryckt)OAI: oai:DiVA.org:mdh-7381DiVA, id: diva2:274445
Disputation
2009-12-14, Beta, Högskoleplan 1, Västerås, 14:00 (Engelska)
Opponent
Handledare
Tillgänglig från: 2009-10-29 Skapad: 2009-10-14 Senast uppdaterad: 2018-01-12Bibliografiskt granskad
Delarbeten
1. A Tool for Gas Turbine Maintenance Scheduling
Öppna denna publikation i ny flik eller fönster >>A Tool for Gas Turbine Maintenance Scheduling
Visa övriga...
2009 (Engelska)Ingår i: Proceedings of the 21st Innovative Applications of Artificial Intelligence Conference, IAAI-09, 2009, s. 9-16Konferensbidrag, Publicerat paper (Refereegranskat)
Abstract [en]

We describe the implementation and deployment of a software decision support tool for the maintenance planning of gas turbines. The tool is used to plan the maintenance for turbines manufactured and maintained by Siemens Industrial Turbomachinery AB (SIT AB) with the goal to reduce the direct maintenance costs and the often very costly production losses during maintenance downtime. The optimization problem is formally defined, and we argue that feasibility in it is NP-complete. We outline a heuristic algorithm that can quickly solve the problem for practical purposes, and validate the approach on a real-world scenario based on an oil production facility. We also compare the performance of our algorithm with results from using mixed integer linear programming, and discuss the deployment of the application. The experimental results indicate that downtime reductions up to 65% can be achieved, compared to traditional preventive maintenance. In addition, using our tool is expected to improve availability with up to 1% and reduce the number of planned maintenance days with 12%. Compared to a mixed integer programming approach, our algorithm not optimal, but is orders of magnitude faster and produces results which are useful in practice. Our test results and SIT AB's estimates based on operational use both indicate that significant savings can be achieved by using our software tool, compared to maintenance plans with fixed intervals

Nationell ämneskategori
Teknik och teknologier
Identifikatorer
urn:nbn:se:mdh:diva-7374 (URN)9781577354239 (ISBN)
Konferens
21st Innovative Applications of Artificial Intelligence Conference, IAAI-09; Pasadena, CA; United States; 14 July 2009 through 16 July 2009
Tillgänglig från: 2009-10-14 Skapad: 2009-10-14 Senast uppdaterad: 2014-09-15Bibliografiskt granskad
2. Reducing vehicle maintenance using condition monitoring and dynamic planning
Öppna denna publikation i ny flik eller fönster >>Reducing vehicle maintenance using condition monitoring and dynamic planning
Visa övriga...
2008 (Engelska)Ingår i: In Proc. of the 4th IET Intl. Conf. on Railway Condition Monitoring (RCM’08), June 2008, 2008, Vol. 2216Konferensbidrag, Publicerat paper (Refereegranskat)
Nationell ämneskategori
Elektroteknik och elektronik
Identifikatorer
urn:nbn:se:mdh:diva-7378 (URN)10.1049/ic:20080329 (DOI)2-s2.0-67650538431 (Scopus ID)9780863419270 (ISBN)
Konferens
4th IET International Conference on Railway Condition Monitoring, RCM 2008; Derby; United Kingdom; 18 June 2008 through 20 June 2008
Tillgänglig från: 2009-10-14 Skapad: 2009-10-14 Senast uppdaterad: 2017-02-10Bibliografiskt granskad
3. Bounding Shared-Stack Usage in Systems with Offsets and Precedences
Öppna denna publikation i ny flik eller fönster >>Bounding Shared-Stack Usage in Systems with Offsets and Precedences
Visa övriga...
2008 (Engelska)Ingår i: ECRTS 2008: PROCEEDINGS OF THE 20TH EUROMICRO CONFERENCE ON REAL-TIME SYSTEMS, 2008, s. 276-285Konferensbidrag, Publicerat paper (Refereegranskat)
Abstract [en]

The paper presents two novel methods to bound the stack memory used in preemptive, shared stack, real-time systems. The first method is based on branch-and-bound search for possible preemption patterns, and the second one approximates the first in polynomial time. The work extends previous methods by considering a more general task-model, in which all tasks can share the same stack. In addition, the new methods account for precedence and offset relations. Thus, the methods give tight bounds for a large set of realistic systems. The methods have been implemented and a comprehensive evaluation, comparing our new methods against each other and against existing methods, is presented. The evaluation shows that our exact method can significantly reduce the amount of stack memory needed.

Nationell ämneskategori
Teknik och teknologier
Identifikatorer
urn:nbn:se:mdh:diva-7187 (URN)10.1109/ECRTS.2008.29 (DOI)000258259900026 ()2-s2.0-52049085961 (Scopus ID)978-0-7695-3298-1 (ISBN)
Konferens
20th Euromicro Conference on Real-Time Systems Location: Prague, CZECH REPUBLIC Date: JUL 02-04, 2008
Tillgänglig från: 2009-09-25 Skapad: 2009-09-25 Senast uppdaterad: 2013-12-03Bibliografiskt granskad
4. Best-Effort Simulation-Based Timing Analysis using Hill-Climbing with Random Restarts
Öppna denna publikation i ny flik eller fönster >>Best-Effort Simulation-Based Timing Analysis using Hill-Climbing with Random Restarts
Visa övriga...
2009 (Engelska)Ingår i: In Proc. of RTCSA, Aug. 2009., 2009Konferensbidrag, Publicerat paper (Refereegranskat)
Nationell ämneskategori
Datorsystem
Identifikatorer
urn:nbn:se:mdh:diva-7377 (URN)
Konferens
RTCSA, Aug. 2009.
Tillgänglig från: 2009-10-14 Skapad: 2009-10-14 Senast uppdaterad: 2017-03-06Bibliografiskt granskad
5. Optimization of condition-based maintenance for industrial gas turbines: Requirements and results
Öppna denna publikation i ny flik eller fönster >>Optimization of condition-based maintenance for industrial gas turbines: Requirements and results
Visa övriga...
2009 (Engelska)Ingår i: Proceedings of the ASME Turbo Expo Volume 5, 2009, s. 455-464Konferensbidrag, Publicerat paper (Refereegranskat)
Abstract [en]

In oil and gas applications, the careful planning and execution of preventive maintenance is important due to the high costs associated with shutdown of critical equipment. Optimization and lifetime management for equipment such as gas turbines is therefore crucial in order to achieve high availability and reliability. In this paper, a novel condition-based gas turbine maintenance strategy is described and evaluated. Using custom-madegas turbine maintenance planning software, maintenance is repeatedly reoptimized to fit into the time intervals where production losses are least costly and result in the lowest possible impact. The strategy focuses on accurate online lifetime estimates for gas turbine components, where algorithms predicting future maintenance requirements are used to produce maintenance deadlines. This ensures that the gas turbines are maintained in accordance with the conditions on site. To show the feasibility and economic effects of a customer-adapted maintenance planning process, the maintenance plan for a gas turbine used in a real-world scenario is optimized using a combinatorial optimization algorithm and input from gas turbine operation data, maintenance schedules and operator requirements. The approach was validated through the inspection of a reference gas turbine after a predetermined time interval. It is shown that savings may be substantial compared to a traditional preventivemaintenance plan. In the evaluation, typical cost reductions range from 25 to 65 %. The calculated availability increase in practice is estimated to range from 0.5 to 1 %. In addition, down-time reductions of approximately 12 % are expected, due solely to improved planning. This indicates significant improvements.

Nationell ämneskategori
Teknik och teknologier
Identifikatorer
urn:nbn:se:mdh:diva-7379 (URN)9780791848869 (ISBN)
Konferens
2009 ASME Turbo Expo; Orlando, FL; United States; 8 June 2009 through 12 June 2009
Tillgänglig från: 2009-10-14 Skapad: 2009-10-14 Senast uppdaterad: 2013-12-03Bibliografiskt granskad
6. Determining Maximum Stack Usage in Preemptive Shared Stack Systems
Öppna denna publikation i ny flik eller fönster >>Determining Maximum Stack Usage in Preemptive Shared Stack Systems
Visa övriga...
2006 (Engelska)Ingår i: Proceedings - Real-Time Systems Symposium, 2006, s. 445-453Konferensbidrag, Publicerat paper (Refereegranskat)
Abstract [en]

This paper presents a novel method to determine the maximum stack memory used in preemptive, shared stack, real-time systems. We provide a general and exact problem formulation applicable for any preemptive system model based on dynamic (run-time) properties. We also show how to safely approximate the exact stack usage by using static (compile time) information about the system model and the underlying run-time system on a relevant and commercially available system model: A hybrid, statically and dynamically, scheduled system.

Comprehensive evaluations show that our technique significantly reduces the amount of stack memory needed compared to existing analysis techniques. For typical task sets a decrease in the order of 70% is typical.

Nationell ämneskategori
Teknik och teknologier
Identifikatorer
urn:nbn:se:mdh:diva-6946 (URN)10.1109/RTSS.2006.18 (DOI)000244448800041 ()2-s2.0-38949169176 (Scopus ID)9780769527611 (ISBN)
Konferens
27th IEEE International Real-Time Systems Symposium, RTSS 2006; Rio de Janeiro; Brazil; 5 December 2006 through 8 December 2006
Tillgänglig från: 2009-09-25 Skapad: 2009-09-25 Senast uppdaterad: 2014-05-30Bibliografiskt granskad

Open Access i DiVA

fulltext(4600 kB)784 nedladdningar
Filinformation
Filnamn FULLTEXT03.pdfFilstorlek 4600 kBChecksumma SHA-512
e92eb09250781b9b641c2381849fe765789673c01bb705692134472639c7c5bde525f10d3b27efcae1726bd85e87131a518b70985e49d670a9c3ee103241e36a
Typ fulltextMimetyp application/pdf

Personposter BETA

Bohlin, Markus

Sök vidare i DiVA

Av författaren/redaktören
Bohlin, Markus
Av organisationen
Akademin för innovation, design och teknik
Datavetenskap (datalogi)

Sök vidare utanför DiVA

GoogleGoogle Scholar
Totalt: 785 nedladdningar
Antalet nedladdningar är summan av nedladdningar för alla fulltexter. Det kan inkludera t.ex tidigare versioner som nu inte längre är tillgängliga.

isbn
urn-nbn

Altmetricpoäng

isbn
urn-nbn
Totalt: 555 träffar
RefereraExporteraLänk till posten
Permanent länk

Direktlänk
Referera
Referensformat
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Annat format
Fler format
Språk
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Annat språk
Fler språk
Utmatningsformat
  • html
  • text
  • asciidoc
  • rtf