You are required to read and agree to the below before accessing a full-text version of an article in the IDE article repository.
The full-text document you are about to access is subject to national and international copyright laws. In most cases (but not necessarily all) the consequence is that personal use is allowed given that the copyright owner is duly acknowledged and respected. All other use (typically) require an explicit permission (often in writing) by the copyright owner.
For the reports in this repository we specifically note that
- the use of articles under IEEE copyright is governed by the IEEE copyright policy (available at http://www.ieee.org/web/publications/rights/copyrightpolicy.html)
- the use of articles under ACM copyright is governed by the ACM copyright policy (available at http://www.acm.org/pubs/copyright_policy/)
- technical reports and other articles issued by M‰lardalen University is free for personal use. For other use, the explicit consent of the authors is required
- in other cases, please contact the copyright owner for detailed information
By accepting I agree to acknowledge and respect the rights of the copyright owner of the document I am about to access.
If you are in doubt, feel free to contact webmaster@ide.mdh.se
A Study of Combinatorial Optimization Problems in Industrial Computer Systems
Publication Type:
Doctoral Thesis
Publisher:
Mälardalen University Press
Abstract
A combinatorial optimization problem is an optimization problem where the number of possible
solutions is finite and grows 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 a system
where a shared stack 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 behavior 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 behavior by analyzing the possible and impossible preemption patterns. Using
relations on offset and precedences, we form a preemption graph, which is further analyzed 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-andbound
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 was 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 analyze complex industrial systems which cannot be analyzed 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 re-planning 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 re-planning 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 %.
Bibtex
@phdthesis{Bohlin1622,
author = {Markus Bohlin},
title = {A Study of Combinatorial Optimization Problems in Industrial Computer Systems},
number = {79},
month = {November},
year = {2009},
school = {M{\"a}lardalen University Press},
url = {http://www.es.mdu.se/publications/1622-}
}