Digitala Vetenskapliga Arkivet

Change search
Refine search result
12345 1 - 50 of 211
CiteExportLink to result list
Permanent link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
Rows per page
  • 5
  • 10
  • 20
  • 50
  • 100
  • 250
Sort
  • Standard (Relevance)
  • Author A-Ö
  • Author Ö-A
  • Title A-Ö
  • Title Ö-A
  • Publication type A-Ö
  • Publication type Ö-A
  • Issued (Oldest first)
  • Issued (Newest first)
  • Created (Oldest first)
  • Created (Newest first)
  • Last updated (Oldest first)
  • Last updated (Newest first)
  • Disputation date (earliest first)
  • Disputation date (latest first)
  • Standard (Relevance)
  • Author A-Ö
  • Author Ö-A
  • Title A-Ö
  • Title Ö-A
  • Publication type A-Ö
  • Publication type Ö-A
  • Issued (Oldest first)
  • Issued (Newest first)
  • Created (Oldest first)
  • Created (Newest first)
  • Last updated (Oldest first)
  • Last updated (Newest first)
  • Disputation date (earliest first)
  • Disputation date (latest first)
Select
The maximal number of hits you can export is 250. When you want to export more records please use the Create feeds function.
  • 1.
    Andersson, Tim
    et al.
    Mälardalen University, School of Innovation, Design and Engineering, Embedded Systems. ASSA ABLOY.
    Ahlskog, Mats
    Mälardalen University, School of Innovation, Design and Engineering, Innovation and Product Realisation.
    Olsson, Tomas
    RISE Research Institutes of Sweden, Västerås, 72212, Sweden.
    Bohlin, Markus
    Mälardalen University, School of Innovation, Design and Engineering, Innovation and Product Realisation.
    Sample size prediction for anomaly detection in locks2023In: Procedia CIRP, Elsevier B.V. , 2023, p. 870-874Conference paper (Refereed)
    Abstract [en]

    Artificial intelligence in manufacturing systems is currently most used for quality control and predictive maintenance. In the lock industry, quality control of final assembled cylinder lock is still done by hand, wearing out the operators' wrists and introducing subjectivity which negatively affects reliability. Studies have shown that quality control can be automated using machine-learning to analyse torque measurements from the locks. The resulting performance of the approach depends on the dimensionality and size of the training dataset but unfortunately, the process of gathering data can be expensive so the amount collected data should therefore be minimized with respect to an acceptable performance measure. The dimensionality can be reduced with a method called Principal Component Analysis and the training dataset size can be estimated by repeated testing of the algorithms with smaller datasets of different sizes, which then can be used to extrapolate the expected performance for larger datasets. The purpose of this study is to evaluate the state-of-the-art methods to predict and minimize the needed sample size for commonly used machine-learning algorithms to reach an acceptable anomaly detection accuracy using torque measurements from locks. The results show that the learning curve with the best fit to the training data does not always give the best predictions. Instead, performance depends on the amount of data used to create the curve and the particular machine-learning algorithm used. Overall, the exponential and power-law functions gave the most reliable predictions and the use of principal component analysis greatly reduced the learning effort for the machine-learning algorithms. With torque measurements from 50-150 locks, we predicted a detection accuracy of over 95% while the current method of using the human tactile sense gives only 16% accuracy.

    Download full text (pdf)
    fulltext
  • 2.
    Andersson, Tim
    et al.
    Mälardalen University, School of Innovation, Design and Engineering, Embedded Systems. ASSA ABLOY.
    Bohlin, Markus
    Mälardalen University, School of Innovation, Design and Engineering, Innovation and Product Realisation.
    Ahlskog, Mats
    Mälardalen University, School of Innovation, Design and Engineering, Innovation and Product Realisation.
    Olsson, Tomas
    Mälardalen University, School of Innovation, Design and Engineering, Embedded Systems.
    Interpretable ML model for quality control of locks using counterfactual explanations2024Conference paper (Refereed)
    Abstract [en]

    This paper presents an interpretable machinelearning model for anomaly detection in door locks using torque data. The model aims to replace the human tactile sense in the quality control process, reducing repetitive tasks and improving reliability. The model achieved an accuracy of 96%, however, to gain social acceptance and operators' trust, interpretability of the model is crucial. The purpose of this study was to evaluate anapproach that can improve interpretability of anomalousclassifications obtained from an anomaly detection model. Weevaluate four instance-based counterfactual explanators, three of which, employ optimization techniques and one uses, a less complex, weighted nearest neighbor approach, which serve as ourbaseline. The former approaches, leverage a latent representation of the data, using a weighted principal component analysis, improving plausibility of the counter factual explanations andreduces computational cost. The explanations are presentedtogether with the 5-50-95th percentile range of the training data, acting as a frame of reference to improve interpretability. All approaches successfully presented valid and plausible counterfactual explanations. However, instance-based approachesemploying optimization techniques yielded explanations withgreater similarity to the observations and was therefore concluded to be preferable despite the higher execution times (4-16s) compared to the baseline approach (0.1s). The findings of this study hold significant value for the lock industry and can potentially be extended to other industrial settings using timeseries data, serving as a valuable point of departure for further research.

    Download full text (pdf)
    fulltext
  • 3.
    Andersson, Tim
    et al.
    Mälardalen University, School of Innovation, Design and Engineering, Embedded Systems. ASSA ABLOY.
    Bohlin, Markus
    Mälardalen University, School of Innovation, Design and Engineering, Innovation and Product Realisation.
    Ahlskog, Mats
    Mälardalen University, School of Innovation, Design and Engineering, Innovation and Product Realisation.
    Olsson, Tomas
    Mälardalen University, School of Innovation, Design and Engineering, Embedded Systems. RISE RESEARCH INSTITUTES OF SWEDEN, Sweden.
    Interpretable ML model for quality control of locks using counterfactual explanations2024Conference paper (Refereed)
    Abstract [en]

    This paper presents an interpretable machinelearning model for anomaly detection in door locks using torque data. The model aims to replace the human tactile sense in the quality control process, reducing repetitive tasks and improving reliability. The model achieved an accuracy of 96%, however, to gain social acceptance and operators' trust, interpretability of the model is crucial. The purpose of this study was to evaluate anapproach that can improve interpretability of anomalousclassifications obtained from an anomaly detection model. Weevaluate four instance-based counterfactual explanators, three of which, employ optimization techniques and one uses, a less complex, weighted nearest neighbor approach, which serve as ourbaseline. The former approaches, leverage a latent representation of the data, using a weighted principal component analysis, improving plausibility of the counter factual explanations andreduces computational cost. The explanations are presentedtogether with the 5-50-95th percentile range of the training data, acting as a frame of reference to improve interpretability. All approaches successfully presented valid and plausible counterfactual explanations. However, instance-based approachesemploying optimization techniques yielded explanations withgreater similarity to the observations and was therefore concluded to be preferable despite the higher execution times (4-16s) compared to the baseline approach (0.1s). The findings of this study hold significant value for the lock industry and can potentially be extended to other industrial settings using timeseries data, serving as a valuable point of departure for further research.

    Download full text (pdf)
    fulltext
  • 4.
    Andersson, Tim
    et al.
    Mälardalen University, Sweden.
    Bohlin, Markus
    Mälardalen University, Sweden.
    Olsson, Tomas
    Mälardalen University, Sweden.
    Ahlskog, Mats
    Mälardalen University, Sweden.
    Comparison of Machine Learning’s- and Humans’- Ability to Consistently Classify Anomalies in Cylinder Locks2022In: APMS 2022: Advances in Production Management Systems. Smart Manufacturing and Logistics Systems: Turning Ideas into Action (Part of the IFIP Advances in Information and Communication Technology book series (IFIPAICT,volume 663)) / [ed] Kim, Duck Young; von Cieminski, Gregor; Romero, David, Springer Nature Switzerland , 2022, p. 27-34Conference paper (Refereed)
    Abstract [en]

    Historically, cylinder locks’ quality has been tested manually by human operators after full assembly. The frequency and the characteristics of the testing procedure for these locks wear the operators’ wrists and lead to varying results of the quality control. The consistency in the quality control is an important factor for the expected lifetime of the locks which is why the industry seeks an automated solution. This study evaluates how consistently the operators can classify a collection of locks, using their tactile sense, compared to a more objective approach, using torque measurements and Machine Learning (ML). These locks were deliberately chosen because they are prone to get inconsistent classifications, which means that there is no ground truth of how to classify them. The ML algorithms were therefore evaluated with two different labeling approaches, one based on the results from the operators, using their tactile sense to classify into ‘working’ or ‘faulty’ locks, and a second approach by letting an unsupervised learner create two clusters of the data which were then labeled by an expert using visual inspection of the torque diagrams. The results show that an ML-solution, trained with the second approach, can classify mechanical anomalies, based on torque data, more consistently compared to operators, using their tactile sense. These findings are a crucial milestone for the further development of a fully automated test procedure that has the potential to increase the reliability of the quality control and remove an injury-prone task from the operators.

  • 5.
    Andersson, Tim
    et al.
    Mälardalen University, School of Innovation, Design and Engineering, Embedded Systems.
    Bohlin, Markus
    Mälardalen University, School of Innovation, Design and Engineering, Innovation and Product Realisation.
    Olsson, Tomas
    Ahlskog, Mats
    Mälardalen University, School of Innovation, Design and Engineering, Innovation and Product Realisation.
    Comparison of Machine Learning’s- and Humans’- Ability to Consistently Classify Anomalies in Cylinder Locks2022In: IFIP Advances in Information and Communication Technology: WG 5.7 International Conference on Advances in Production Management Systems, APMS 2022, Springer Science and Business Media Deutschland GmbH , 2022, p. 27-34Conference paper (Refereed)
    Abstract [en]

    Historically, cylinder locks’ quality has been tested manually by human operators after full assembly. The frequency and the characteristics of the testing procedure for these locks wear the operators’ wrists and lead to varying results of the quality control. The consistency in the quality control is an important factor for the expected lifetime of the locks which is why the industry seeks an automated solution. This study evaluates how consistently the operators can classify a collection of locks, using their tactile sense, compared to a more objective approach, using torque measurements and Machine Learning (ML). These locks were deliberately chosen because they are prone to get inconsistent classifications, which means that there is no ground truth of how to classify them. The ML algorithms were therefore evaluated with two different labeling approaches, one based on the results from the operators, using their tactile sense to classify into ‘working’ or ‘faulty’ locks, and a second approach by letting an unsupervised learner create two clusters of the data which were then labeled by an expert using visual inspection of the torque diagrams. The results show that an ML-solution, trained with the second approach, can classify mechanical anomalies, based on torque data, more consistently compared to operators, using their tactile sense. These findings are a crucial milestone for the further development of a fully automated test procedure that has the potential to increase the reliability of the quality control and remove an injury-prone task from the operators.

  • 6.
    Aronsson, Martin
    et al.
    SICS.
    Bohlin, Markus
    SICS.
    Doganay, Kivanc
    SICS.
    Holst, Anders
    SICS.
    An Integrated Adaptive Maintenance Concept2010Conference paper (Refereed)
    Abstract [en]

    In this paper, we present a novel maintenance concept based on condition monitoring and dynamic maintenance packaging, by showing how to connect the information flow from low-level sensors to high-level operations and planning under uncertainty. Today, condition-based maintenance systems are focused on data collection and custom-made rule based systems for data analysis. In many cases, the focus is on measuring "everything" without considering how to use the measurements. In addition, the measurements are often noisy and the future is unpredictable which adds a lot of uncertainty. As a consequence, maintenance is often planned in advance and not replanned when new condition data is available. This often reduces the benefits of condition monitoring. The concept is based on the combination of robust, dynamically adapted maintenance optimization and statistical data analysis where the uncertainty is considered. This approach ties together low-level data acquisition and high-level planning and optimization. The concept has been illustrated in a context of rail vehicle maintenance, where measurements of brake pad and pantograph contact strip wear is used to predict the near future condition, and plan the maintenance activities.

  • 7.
    Aronsson, Martin
    et al.
    RISE, Swedish ICT, SICS, Decisions, Networks and Analytics lab.
    Bohlin, Markus
    RISE - Research Institutes of Sweden (2017-2019), ICT, SICS.
    Doganay, Kivanc
    RISE, Swedish ICT, SICS.
    Holst, Anders
    RISE, Swedish ICT, SICS, Decisions, Networks and Analytics lab.
    Kjellqvist, Tommy
    Östlund, Stefan
    An Integrated Adaptive Maintenance Concept2010Conference paper (Refereed)
    Abstract [en]

    In this paper, we present a novel maintenance concept based on condition monitoring and dynamic maintenance packaging, by showing how to connect the information flow from low-level sensors to high-level operations and planning under uncertainty. Today, condition-based maintenance systems are focused on data collection and custom-made rule based systems for data analysis. In many cases, the focus is on measuring "everything" without considering how to use the measurements. In addition, the measurements are often noisy and the future is unpredictable which adds a lot of uncertainty. As a consequence, maintenance is often planned in advance and not replanned when new condition data is available. This often reduces the benefits of condition monitoring. The concept is based on the combination of robust, dynamically adapted maintenance optimization and statistical data analysis where the uncertainty is considered. This approach ties together low-level data acquisition and high-level planning and optimization. The concept has been illustrated in a context of rail vehicle maintenance, where measurements of brake pad and pantograph contact strip wear is used to predict the near future condition, and plan the maintenance activities.

  • 8.
    Aronsson, Martin
    et al.
    RISE., Decisions, Networks and Analytics lab.
    Bohlin, Markus
    RISE - Research Institutes of Sweden (2017-2019), SICS, Sweden.
    Kreuger, Per
    RISE., Decisions, Networks and Analytics lab.
    MILP formulations of cumulative constraints for railway scheduling - A comparative study2009In: The Proceedings of the 9th Workshop on Algorithmic Methods and Models for Optimization of Railways (ATMOS), Internationales Begegnungs- und Forschungszentrum für Informatik (IBFI), Schloss Dagstuhl, Germany , 2009, 13Conference paper (Refereed)
    Abstract [en]

    This paper introduces two Mixed Integer Linear Programming (MILP) models for railway traffic planning using a cumulative scheduling constraint and associated pre-processing filters. We compare standard solver performance for these models on three sets of problems from the railway domain and for two of them, where tasks have unitary resource consumption, we also compare them with two more conventional models. In the experiments, the solver performance of one of the cumulative models is clearly the best and is also shown to scale very well for a large scale practical railway scheduling problem.

  • 9.
    Aronsson, Martin
    et al.
    RISE, Swedish ICT, SICS, Decisions, Networks and Analytics lab.
    Bohlin, Markus
    RISE - Research Institutes of Sweden (2017-2019), ICT, SICS.
    Kreuger, Per
    RISE, Swedish ICT, SICS, Decisions, Networks and Analytics lab.
    MILP formulations of cumulative constraints for railway scheduling - A comparative study2009In: The Proceedings of the 9th Workshop on Algorithmic Methods and Models for Optimization of Railways (ATMOS), Internationales Begegnungs- und Forschungszentrum für Informatik (IBFI), Schloss Dagstuhl, Germany , 2009, 13Conference paper (Refereed)
    Abstract [en]

    This paper introduces two Mixed Integer Linear Programming (MILP) models for railway traffic planning using a cumulative scheduling constraint and associated pre-processing filters. We compare standard solver performance for these models on three sets of problems from the railway domain and for two of them, where tasks have unitary resource consumption, we also compare them with two more conventional models. In the experiments, the solver performance of one of the cumulative models is clearly the best and is also shown to scale very well for a large scale practical railway scheduling problem.

    Download full text (pdf)
    FULLTEXT01
  • 10.
    Aronsson, Martin
    et al.
    RISE., Decisions, Networks and Analytics lab.
    Bohlin, Markus
    RISE - Research Institutes of Sweden (2017-2019), SICS, Sweden.
    Kreuger, Per
    RISE., Decisions, Networks and Analytics lab.
    Mixed integer-linear formulations of cumulative scheduling constraints - A comparative study2007Report (Other academic)
    Abstract [en]

    This paper introduces two MILP models for the cumulative scheduling constraint and associated pre-processing filters. We compare standard solver performance for these models on three sets of problems and for two of them, where tasks have unitary resource consumption, we also compare them with two models based on a geometric placement constraint. In the experiments, the solver performance of one of the cumulative models, is clearly the best and is also shown to scale very well for a large scale industrial transportation scheduling problem.

  • 11.
    Aronsson, Martin
    et al.
    RISE, Swedish ICT, SICS, Decisions, Networks and Analytics lab.
    Bohlin, Markus
    RISE - Research Institutes of Sweden (2017-2019), ICT, SICS.
    Kreuger, Per
    RISE, Swedish ICT, SICS, Decisions, Networks and Analytics lab.
    Mixed integer-linear formulations of cumulative scheduling constraints - A comparative study2007Report (Other academic)
    Abstract [en]

    This paper introduces two MILP models for the cumulative scheduling constraint and associated pre-processing filters. We compare standard solver performance for these models on three sets of problems and for two of them, where tasks have unitary resource consumption, we also compare them with two models based on a geometric placement constraint. In the experiments, the solver performance of one of the cumulative models, is clearly the best and is also shown to scale very well for a large scale industrial transportation scheduling problem.

    Download full text (pdf)
    FULLTEXT01
  • 12.
    Bajceta, Aleksandar
    et al.
    Mälardalen University.
    Leon, Miguel
    Mälardalen University, School of Innovation, Design and Engineering, Innovation and Product Realisation.
    Afzal, Wasif
    Mälardalen University, School of Innovation, Design and Engineering, Embedded Systems.
    Lindberg, P.
    Alstom Sweden, Västerås, Sweden.
    Bohlin, Markus
    Mälardalen University, School of Innovation, Design and Engineering, Innovation and Product Realisation.
    Using NLP Tools to Detect Ambiguities in System Requirements - A Comparison Study2022In: CEUR Workshop Proceedings, CEUR-WS , 2022, Vol. 3122Conference paper (Refereed)
    Abstract [en]

    Requirements engineering is a time-consuming process, and it can benefit significantly from automated tool support. Ambiguity detection in natural language requirements is a challenging problem in the requirements engineering community. Several Natural Language Processing tools and techniques have been developed to improve and solve the problem of ambiguity detection in natural language requirements. However, there is a lack of empirical evaluation of these tools. We aim to contribute the understanding of the empirical performance of such solutions by evaluating four tools using the dataset of 180 system requirements from the electric train propulsion system provided to us by our industrial partner Alstom. The tools that were selected for this study are Automated Requirements Measurement (ARM), Quality Analyzer for Requirement Specifications (QuARS), REquirements Template Analyzer (RETA), and Requirements Complexity Measurement (RCM). Our analysis showed that selected tools could achieve high recall. Two of them had the recall of 0.85 and 0.98. But they struggled to achieve high precision. The RCM, an in-house developed tool by our industrial partner Alstom, achieved the highest precision in our study of 0.68. 

  • 13.
    Bashir, Sarmad
    et al.
    Mälardalen University, School of Innovation, Design and Engineering, Innovation and Product Realisation. RISE Research Institutes of Sweden, Västerås, Sweden.
    Abbas, Muhammad
    Mälardalen University, School of Innovation, Design and Engineering, Embedded Systems. RISE Research Institutes of Sweden, Västerås, Sweden.
    Saadatmand, Mehrdad
    Mälardalen University, School of Innovation, Design and Engineering, Embedded Systems.
    Enoiu, Eduard Paul
    Mälardalen University, School of Innovation, Design and Engineering, Embedded Systems.
    Bohlin, Markus
    Mälardalen University, School of Innovation, Design and Engineering, Innovation and Product Realisation.
    Lindberg, Pernilla
    Alstom, Västerås, Sweden.
    Requirement or Not, That is the Question: A Case from the Railway Industry2023In: Lecture Notes In Computer Science, Springer Science and Business Media Deutschland GmbH , 2023, p. 105-121Conference paper (Refereed)
    Abstract [en]

    [Context and Motivation] Requirements in tender documents are often mixed with other supporting information. Identifying requirements in large tender documents could aid the bidding process and help estimate the risk associated with the project. [Question/problem] Manual identification of requirements in large documents is a resource-intensive activity that is prone to human error and limits scalability. This study compares various state-of-the-art approaches for requirements identification in an industrial context. For generalizability, we also present an evaluation on a real-world public dataset. [Principal ideas/results] We formulate the requirement identification problem as a binary text classification problem. Various state-of-the-art classifiers based on traditional machine learning, deep learning, and few-shot learning are evaluated for requirements identification based on accuracy, precision, recall, and F1 score. Results from the evaluation show that the transformer-based BERT classifier performs the best, with an average F1 score of 0.82 and 0.87 on industrial and public datasets, respectively. Our results also confirm that few-shot classifiers can achieve comparable results with an average F1 score of 0.76 on significantly lower samples, i.e., only 20% of the data. [Contribution] There is little empirical evidence on the use of large language models and few-shots classifiers for requirements identification. This paper fills this gap by presenting an industrial empirical evaluation of the state-of-the-art approaches for requirements identification in large tender documents. We also provide a running tool and a replication package for further experimentation to support future research in this area.

  • 14.
    Bohlin, Markus
    RISE - Research Institutes of Sweden, ICT, SICS.
    A Local Search System for Solving Constraint Problems of Declarative Graph-Based Global Constraints2004In: Proceedings of the 15th International Conference on Applications of Declarative Programming and Knowledge Management, 2004, 1Conference paper (Refereed)
    Abstract [en]

    In this paper we present a local search constraint solver in which constraints are expressed using cost functions on graph structures of filter constraints of equal type. A similar theoretical approach has previously been used to model a large number of complex global constraints, which motivates the use of such a model in practice. In a local search context, we view global constraints as complex cost functions, encapsulating the structure of the constraints using a graph of variables, values and filter constraints. This representation gives us a declarative model, which can also be used to efficiently compute a cost as well as conflict levels of the variables in the constraints. We have implemented these ideas in a compositional C++ framework called Composer, which can be used to solve systems of graph-based constraints. We demonstrate the usability of this approach on several well-known global constraints, and show by experimental results on two problems that an approach using a graph basis for global constraint modeling is not only possible in practice, but also competitive with existing constraint-based local search systems.

  • 15.
    Bohlin, Markus
    RISE - Research Institutes of Sweden, ICT, SICS.
    A Local Search System for Solving Constraint Problems of Declarative Graph-Based Global Constraints2005In: Applications of Declarative Programming and Knowledge Management: 15th International Conference on Applications of Declarative Programming and Knowledge Management, INAP 2004, and 18th Workshop on Logic Programming: Revised Selected Papers, Springer , 2005, 1, , p. 308p. 166-184Conference paper (Refereed)
    Abstract [en]

    In this paper we present a local search constraint solver in which constraints are expressed using cost functions on graph structures of filter constraints of equal type. A similar theoretical approach has previously been used to model a large number of complex global constraints, which motivates the use of such a model in practice. In a local search context, we view global constraints as complex cost functions, encapsulating the structure of the constraints using a graph of variables, values and filter constraints. This representation gives us a declarative model, which can also be used to efficiently compute a cost as well as conflict levels of the variables in the constraints. We have implemented these ideas in a compositional C++ framework called Composer, which can be used to solve systems of graph-based constraints. We demonstrate the usability of this approach on several well-known global constraints, and show by experimental results on two problems that an approach using a graph basis for global constraint modeling is not only possible in practice, but also competitive with existing constraint-based local search systems.

  • 16.
    Bohlin, Markus
    Mälardalen University, School of Innovation, Design and Engineering.
    A Study of Combinatorial Optimization Problems in Industrial Computer Systems2009Doctoral thesis, comprehensive summary (Other academic)
    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 %.

    Download full text (pdf)
    FULLTEXT03
  • 17.
    Bohlin, Markus
    RISE - Research Institutes of Sweden, ICT, SICS.
    A Study of Combinatorial Optimization Problems in Industrial Computer Systems2009Doctoral thesis, monograph (Other academic)
    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 %.

    Download full text (pdf)
    FULLTEXT01
  • 18.
    Bohlin, Markus
    RISE - Research Institutes of Sweden, ICT, SICS.
    Constraint satisfaction by local search2002Report (Other academic)
    Abstract [en]

    The constraint satisfaction problem and its derivate, the propositional satisfiability problem (SAT), are fundamental problems in computing theory and mathematical logic. SAT was the first proved NP-complete problem, and although complete algorithms have been dominating the constraint satisfaction field, incomplete approaches based on local search has been successful the last ten years. In this report we give a general framework for constraint satisfaction using local search as well as an different techniques to improve this basic local search framework. We also give an overview of algorithms for problems of constraint satisfaction and optimization using heuristics, and discuss hybrid methods that combine complete methods for constraint satisfaction with local search techniques.

    Download full text (pdf)
    FULLTEXT01
  • 19.
    Bohlin, Markus
    RISE - Research Institutes of Sweden (2017-2019), SICS.
    Constraint satisfaction by local search2002Report (Other academic)
    Abstract [en]

    The constraint satisfaction problem and its derivate, the propositional satisfiability problem (SAT), are fundamental problems in computing theory and mathematical logic. SAT was the first proved NP-complete problem, and although complete algorithms have been dominating the constraint satisfaction field, incomplete approaches based on local search has been successful the last ten years. In this report we give a general framework for constraint satisfaction using local search as well as an different techniques to improve this basic local search framework. We also give an overview of algorithms for problems of constraint satisfaction and optimization using heuristics, and discuss hybrid methods that combine complete methods for constraint satisfaction with local search techniques.

  • 20.
    Bohlin, Markus
    Mälardalen University, Department of Computer Science and Engineering.
    Design and implementation of a graph-based constraint model for local search2004Licentiate thesis, comprehensive summary (Other scientific)
  • 21.
    Bohlin, Markus
    et al.
    RISE - Research Institutes of Sweden, ICT, SICS.
    Bruce, Lars
    Redesign of the Oz Compiler2002Report (Other academic)
    Abstract [en]

    This master of science thesis describes a new design and its implementation for an Oz compiler. The project is based on the existing Oz compiler. The new compiler is designed more modular, with separate software components that can be replaced and modified locally. A prototype has been implemented, but further development is necessary. We give an overview of the language Oz, its features and the underlying calculus. The features of Oz regarding object orientation, functional programming, logic and constraint programming are also discussed. The liveness analysis and register allocation problems in general and regarding Oz specific compilers are analyzed, together with current and future optimizations suitable for the Mozart platform. The design of the new compiler and information about the old one is presented, and future work regarding the compiler, optimizations, and analysis phases is discussed. Appendices describing the interfaces between the phases of the compiler is included, together with documentation regarding the internal code formats used.

    Download full text (pdf)
    FULLTEXT01
  • 22.
    Bohlin, Markus
    et al.
    Mälardalen University, School of Innovation, Design and Engineering, Innovation and Product Realisation. RISE - Research Institutes of Sweden (2017-2019), SICS.
    Bruce, Lars
    Redesign of the Oz Compiler2002Report (Other academic)
    Abstract [en]

    This master of science thesis describes a new design and its implementation for an Oz compiler. The project is based on the existing Oz compiler. The new compiler is designed more modular, with separate software components that can be replaced and modified locally. A prototype has been implemented, but further development is necessary. We give an overview of the language Oz, its features and the underlying calculus. The features of Oz regarding object orientation, functional programming, logic and constraint programming are also discussed. The liveness analysis and register allocation problems in general and regarding Oz specific compilers are analyzed, together with current and future optimizations suitable for the Mozart platform. The design of the new compiler and information about the old one is presented, and future work regarding the compiler, optimizations, and analysis phases is discussed. Appendices describing the interfaces between the phases of the compiler is included, together with documentation regarding the internal code formats used.

  • 23.
    Bohlin, Markus
    et al.
    RISE - Research Institutes of Sweden (2017-2019), ICT, SICS.
    Dahms, Florian
    RWTH Aachen, Germany.
    Flier, Holger
    ETH Zürich, Switzerland.
    Gestrelius, Sara
    RISE, Swedish ICT, SICS.
    Optimal Freight Train Classification using Column Generation2012Conference paper (Refereed)
    Abstract [en]

    We consider planning of freight train classification at hump yards using integer programming. The problem involves the formation of departing freight trains from arriving trains subject to scheduling and capacity constraints. To increase yard capacity, we allow the temporary storage of early freight cars on specific mixed-usage tracks. The problem has previously been modeled using a direct integer programming model, but this approach did not yield lower bounds of sufficient quality to prove optimality. In this paper, we formulate a new extended integer programming model and design a column generation approach based on branch-and-price to solve problem instances of industrial size. We evaluate the method on historical data from the Hallsberg hump yard in Sweden, and compare the results with previous approaches. The new method managed to find optimal solutions in all of the 192 problem instances tried. Furthermore, no instance took more than 13 minutes to solve to optimality using fairly standard computer hardware.

  • 24.
    Bohlin, Markus
    et al.
    Swedish Institute of Computer Science, Sweden.
    Dahms, FlorianRWTH Aachen, Chair of Operations Research, Germany.Flier, HolgerETH Zürich, Institute of Theoretical Computer Science, Switzerland.Sara, GestreliusSwedish Institute of Computer Science, Sweden.
    Optimal Freight Train Classification using Column Generation2012Collection (editor) (Refereed)
  • 25.
    Bohlin, Markus
    et al.
    Swedish Institute of Computer Science, SICS.
    Doganay, Kivanc
    Swedish Institute of Computer Science, SICS.
    Kreuger, P.
    Swedish Institute of Computer Science, SICS.
    Steinert, R.
    KTH.
    Wärja, Mathias
    Siemens Industrial Turbomachinery AB.
    Searching for Gas Turbine Maintenance Schedules2010In: The AI Magazine, ISSN 0738-4602, Vol. 31, no 1, p. 21-36Article in journal (Refereed)
    Abstract [en]

    Preventive maintenance schedules occurring in industry are often suboptimal with regard to maintenance coal-location, loss-of-production costs and availability. We describe the implementation and deployment of a software decision support tool for the maintenance planning of gas turbines, with the goal of reducing the direct maintenance costs and the often costly production losses during maintenance downtime. The optimization problem is formally defined, and we argue that the feasibility version 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 integer 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, the use of our tool is expected to improve availability with up to 1% and reduce the number of planned maintenance days by 12%. Compared to a integer programming approach, our algorithm is not optimal, but is much 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.

  • 26.
    Bohlin, Markus
    et al.
    RISE - Research Institutes of Sweden (2017-2019), ICT, SICS.
    Doganay, Kivanc
    RISE, Swedish ICT, SICS.
    Kreuger, Per
    RISE, Swedish ICT, SICS, Decisions, Networks and Analytics lab.
    Scheduling Gas Turbine Maintenance Based on Condition Data2009In: Proceedings of the 21st Innovative Applications of Artificial Intelligence Conference, 2009, 6Conference paper (Refereed)
  • 27.
    Bohlin, Markus
    et al.
    Swedish Institute of Computer Science, SICS.
    Doganay, Kivanc
    Swedish Institute of Computer Science, SICS.
    Kreuger, Per
    Swedish Institute of Computer Science, SICS.
    Steinert, Rebecca
    Swedish Institute of Computer Science, SICS.
    Wärja, Mathias
    Siemens Industrial Turbomachinery AB.
    A Tool for Gas Turbine Maintenance Scheduling2009In: Proceedings of the 21st Innovative Applications of Artificial Intelligence Conference, IAAI-09, 2009, p. 9-16Conference paper (Refereed)
    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

  • 28.
    Bohlin, Markus
    et al.
    RISE - Research Institutes of Sweden (2017-2019), ICT, SICS.
    Doganay, Kivanc
    RISE, Swedish ICT, SICS.
    Kreuger, Per
    RISE, Swedish ICT, SICS, Decisions, Networks and Analytics lab.
    Steinert, Rebecca
    RISE, Swedish ICT, SICS, Decisions, Networks and Analytics lab.
    Wärja, Mathias
    A Tool for Gas Turbine Maintenance Scheduling2009In: Proceedings of the Twenty-First Conference on Innovative Applications of Artificial Intelligence (IAAI'09), IEEE Computer Society , 2009, 20Conference paper (Refereed)
    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.

    Download full text (pdf)
    fulltext
  • 29.
    Bohlin, Markus
    et al.
    RISE - Research Institutes of Sweden (2017-2019), ICT, SICS.
    Doganay, Kivanc
    RISE, Swedish ICT, SICS.
    Kreuger, Per
    RISE, Swedish ICT, SICS, Decisions, Networks and Analytics lab.
    Steinert, Rebecca
    RISE, Swedish ICT, SICS, Decisions, Networks and Analytics lab.
    Wärja, Mathias
    Searching for Gas Turbine Maintenance Schedules2010In: AI Magazine, Vol. 31, no 1, p. 21-36Article in journal (Refereed)
    Abstract [en]

    Preventive maintenance schedules occurring in industry are often suboptimal with regard to maintenance coal-location, loss-of-production costs and availability. We describe the implementation and deployment of a software decision support tool for the maintenance planning of gas turbines, with the goal of reducing the direct maintenance costs and the often costly production losses during maintenance downtime. The optimization problem is formally defined, and we argue that the feasibility version 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 integer 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, the use of our tool is expected to improve availability with up to 1% and reduce the number of planned maintenance days by 12%. Compared to a integer programming approach, our algorithm is not optimal, but is much 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.

  • 30.
    Bohlin, Markus
    et al.
    RISE - Research Institutes of Sweden (2017-2019), SICS, Sweden.
    Ekman, Jan
    RISE., Decisions, Networks and Analytics lab.
    Holst, Anders
    RISE., Decisions, Networks and Analytics lab.
    The opportunistic replacement and inspection problem for components with a stochastic life time2011Report (Other academic)
    Abstract [en]

    The problem of finding efficient maintenance and inspection schemes in the case of components with a stochastic life time is studied and a mixed integer programming solution is proposed. The problem is compared with the two simpler problems of which the studied problem is a generalisation: The opportunistic replacement problem, assuming components with a deterministic life time and The opportunistic replacement problem for components with a stochastic life time, for maintenance schemes without inspections.

  • 31.
    Bohlin, Markus
    et al.
    RISE - Research Institutes of Sweden (2017-2019), ICT, SICS.
    Ekman, Jan
    RISE, Swedish ICT, SICS, Decisions, Networks and Analytics lab.
    Holst, Anders
    RISE, Swedish ICT, SICS, Decisions, Networks and Analytics lab.
    The opportunistic replacement and inspection problem for components with a stochastic life time2011Report (Other academic)
    Abstract [en]

    The problem of finding efficient maintenance and inspection schemes in the case of components with a stochastic life time is studied and a mixed integer programming solution is proposed. The problem is compared with the two simpler problems of which the studied problem is a generalisation: The opportunistic replacement problem, assuming components with a deterministic life time and The opportunistic replacement problem for components with a stochastic life time, for maintenance schemes without inspections.

    Download full text (pdf)
    FULLTEXT01
  • 32. Bohlin, Markus
    et al.
    Flier, Holger
    Optimal Freight Train Classification using Column Generation2012In: 12th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems, September 13, 2012, Ljubljana, Slovenia, 2012, p. 10-22Conference paper (Refereed)
  • 33.
    Bohlin, Markus
    et al.
    RISE - Research Institutes of Sweden, ICT, SICS.
    Flier, Holger
    Maue, Jens
    Matúš, Mihalák
    Track Allocation in Freight-Train Classification with Mixed Tracks2011Conference paper (Refereed)
    Abstract [en]

    We consider the process of forming outbound trains from cars of inbound trains at rail-freight hump yards. Given the arrival and departure times as well as the composition of the trains, we study the problem of allocating classification tracks to outbound trains such that every outbound train can be built on a separate classification track. We observe that the core problem can be formulated as a special list coloring problem in interval graphs, which is known to be NP-complete. We focus on an extension where individual cars of different trains can temporarily be stored on a special subset of the tracks. This problem induces several new variants of the list-coloring problem, in which the given intervals can be shortened by cutting off a prefix of the interval. We show that in case of uniform and sufficient track lengths, the corresponding coloring problem can be solved in polynomial time, if the goal is to minimize the total cost associated with cutting off prefixes of the intervals. Based on these results, we devise two heuristics as well as an integer program to tackle the problem. As a case study, we consider a real-world problem instance from the Hallsberg Rangerbangård hump yard in Sweden. Planning over horizons of seven days, we obtain feasible solutions from the integer program in all scenarios, and from the heuristics in most scenarios.

    Download full text (pdf)
    FULLTEXT01
  • 34.
    Bohlin, Markus
    et al.
    Mälardalen University, School of Innovation, Design and Engineering. SICS, Sweden.
    Flier, Holger
    Mälardalen University, School of Innovation, Design and Engineering. ETH, Suisse.
    Maue, Jens
    ETH, Suisse.
    Mihalák, Matúš
    Mälardalen University, School of Innovation, Design and Engineering. ETH, Suisse.
    Hump Yard Track Allocation with Temporary Car Storage2011In: 4th International Seminar on Railway Operations Modelling and Analysis, 2011Conference paper (Refereed)
    Abstract [en]

    In rail freight operation, freight cars need to be separated and reformed into new trains at hump yards. The classification procedure is complex and hump yards constitute bottlenecks in the rail freight network, often causing outbound trains to be delayed. One of the problems is that planning for the allocation of tracks at hump yards is difficult, given that the planner has limited resources (tracks, shunting engines, etc.) and needs to foresee the future capacity requirements when planning for the current inbound trains. In this paper, we consider the problem of allocating classification tracks in a rail freight hump yard for arriving and departing trains with predetermined arrival and departure times. The core problem can be formulated as a special list coloring problem. We focus on an extension where individual cars can temporarily be stored on a special subset of the tracks. An extension where individual cars can temporarily be stored on a special subset of the tracks is also considered. We model the problem using mixed integer programming, and also propose several heuristics that can quickly give feasible track allocations. As a case study, we consider a real-world problem instance from the Hallsberg Rangerbangard hump yard in Sweden. Planning over horizons over two to four days, we obtain feasible solutions from both the exact and heuristic approaches that allow all outgoing trains to leave on time.

  • 35.
    Bohlin, Markus
    et al.
    Mälardalen University, School of Innovation, Design and Engineering.
    Flier, Holger
    ETH Zürich, Institute of Theoretical Computer Science, Switzerland.
    Maue, Jens
    ETH Zürich, Institute of Theoretical Computer Science, Switzerland.
    Mihalák, Matúš
    ETH Zürich, Institute of Theoretical Computer Science, Switzerland.
    Track Allocation in Freight-Train Classification with Mixed Tracks2011In: OpenAccess Series in Informatics, Volume 20, 2011, 2011, p. 38-51Conference paper (Refereed)
    Abstract [en]

    We consider the process of forming outbound trains from cars of inbound trains at rail-freight hump yards. Given the arrival and departure times as well as the composition of the trains, we study the problem of allocating classification tracks to outbound trains such that every outbound train can be built on a separate classification track. We observe that the core problem can be formulated as a special list coloring problem in interval graphs, which is known to be NP-complete. We focus on an extension where individual cars of different trains can temporarily be stored on a special subset of the tracks. This problem induces several new variants of the list-coloring problem, in which the given intervals can be shortened by cutting off a prefix of the interval. We show that in case of uniform and sufficient track lengths, the corresponding coloring problem can be solved in polynomial time, if the goal is to minimize the total cost associated with cutting off prefixes of the intervals. Based on these results, we devise two heuristics as well as an integer program to tackle the problem. As a case study, we consider a real-world problem instance from the Hallsberg Rangerbangard hump yard in Sweden. Planning over horizons of seven days, we obtain feasible solutions from the integer program in all scenarios, and from the heuristics in most scenarios.

  • 36.
    Bohlin, Markus
    et al.
    RISE - Research Institutes of Sweden, ICT, SICS.
    Flier, Holger
    Maue, Jens
    Mihalák, Matúš
    Hump Yard Track Allocation with Temporary Car Storage2011Conference paper (Refereed)
    Abstract [en]

    In rail freight operation, freight cars need to be separated and reformed into new trains at hump yards. The classification procedure is complex and hump yards constitute bottlenecks in the rail freight network, often causing outbound trains to be delayed. One of the problems is that planning for the allocation of tracks at hump yards is difficult, given that the planner has limited resources (tracks, shunting engines, etc.) and needs to foresee the future capacity requirements when planning for the current inbound trains. In this paper, we consider the problem of allocating classification tracks in a rail freight hump yard for arriving and departing trains with predetermined arrival and departure times. The core problem can be formulated as a special list coloring problem. We focus on an extension where individual cars can temporarily be stored on a special subset of the tracks. An extension where individual cars can temporarily be stored on a special subset of the tracks is also considered. We model the problem using mixed integer programming, and also propose several heuristics that can quickly give feasible track allocations. As a case study, we consider a real-world problem instance from the Hallsberg Rangerbangård hump yard in Sweden. Planning over horizons over two to four days, we obtain feasible solutions from both the exact and heuristic approaches that allow all outgoing trains to leave on time.

    Download full text (pdf)
    FULLTEXT01
  • 37.
    Bohlin, Markus
    et al.
    RISE - Research Institutes of Sweden, ICT, SICS.
    Flier, Holger
    Maue, Jens
    Mihalák, Matúš
    Hump Yard Track Allocation with Temporary Car Storage2010Report (Other academic)
    Abstract [en]

    In rail freight operation, freight cars need to be separated and reformed into new trains at hump yards. The classification procedure is complex and time consuming, and hump yards often constitute bottlenecks in the rail freight network. One of the problems is that planning for the allocation of tracks at hump yards is difficult, given that the planner has limited resources (tracks, shunting engines, etc.) and needs to foresee the future capacity requirements when planning for the current inbound trains. In this paper, we consider the problem of allocating classification tracks in a rail freight hump yard for arriving and departing trains. Arrival and departure times are predetermined and may originate in timetables or estimated arrival and departure times (in case of disturbances in the rail system). The core problem can be formulated as a special list coloring problem. We focus on an extension where individual cars can temporarily be stored on a special subset of the tracks. We model the problem using mixed integer programming, and also propose several heuristics that can quickly give feasible track allocations. As a case study, we consider a real-world problem instance from the Hallsberg Rangerbangård hump yard in Sweden. Planning over horizons over two to four days, we obtain feasible solutions from both the exact and heuristic approaches that allow all outgoing trains to leave on time.

    Download full text (pdf)
    FULLTEXT01
  • 38.
    Bohlin, Markus
    et al.
    RISE - Research Institutes of Sweden (2017-2019), SICS, Sweden.
    Flier, Holger
    Maue, Jens
    Mihalák, Matúš
    Hump Yard Track Allocation with Temporary Car Storage2010Report (Other academic)
    Abstract [en]

    In rail freight operation, freight cars need to be separated and reformed into new trains at hump yards. The classification procedure is complex and time consuming, and hump yards often constitute bottlenecks in the rail freight network. One of the problems is that planning for the allocation of tracks at hump yards is difficult, given that the planner has limited resources (tracks, shunting engines, etc.) and needs to foresee the future capacity requirements when planning for the current inbound trains. In this paper, we consider the problem of allocating classification tracks in a rail freight hump yard for arriving and departing trains. Arrival and departure times are predetermined and may originate in timetables or estimated arrival and departure times (in case of disturbances in the rail system). The core problem can be formulated as a special list coloring problem. We focus on an extension where individual cars can temporarily be stored on a special subset of the tracks. We model the problem using mixed integer programming, and also propose several heuristics that can quickly give feasible track allocations. As a case study, we consider a real-world problem instance from the Hallsberg Rangerbangård hump yard in Sweden. Planning over horizons over two to four days, we obtain feasible solutions from both the exact and heuristic approaches that allow all outgoing trains to leave on time.

  • 39.
    Bohlin, Markus
    et al.
    RISE - Research Institutes of Sweden, ICT, SICS.
    Forsgren, Malin
    Utvärdering av simulerat dynamiskt underhåll för spårbundna fordon2008Report (Other academic)
    Abstract [sv]

    Rapporten beskriver ett antal provkörningar av TIMM-demonstratorn utförda för att undersöka hur antalet besök i verkstaden varierar givet en förväntad underhållsvinst från CBM. TIMM-demonstratorn är en programvara framtagen för att under drift planera in underhållsbesök för ett antal simulerade fordon i spårtrafik, där underhållsbehovet styrs av dynamiskt varierande mätvärden på fordonen.

    Download full text (pdf)
    FULLTEXT01
    Download full text (ps)
    FULLTEXT02
  • 40.
    Bohlin, Markus
    et al.
    RISE - Research Institutes of Sweden (2017-2019), SICS, Sweden.
    Forsgren, Malin
    Utvärdering av simulerat dynamiskt underhåll för spårbundna fordon2008Report (Other academic)
    Abstract [sv]

    Rapporten beskriver ett antal provkörningar av TIMM-demonstratorn utförda för att undersöka hur antalet besök i verkstaden varierar givet en förväntad underhållsvinst från CBM. TIMM-demonstratorn är en programvara framtagen för att under drift planera in underhållsbesök för ett antal simulerade fordon i spårtrafik, där underhållsbehovet styrs av dynamiskt varierande mätvärden på fordonen.

  • 41.
    Bohlin, Markus
    et al.
    SICS.
    Forsgren, Malin
    SICS.
    Holst, Anders
    SICS.
    Levin, Björn
    SICS.
    Aronsson, Martin
    SICS.
    Steinert, Rebecca
    SICS.
    Reducing vehicle maintenance using condition monitoring and dynamic planning2008In: In Proc. of the 4th IET Intl. Conf. on Railway Condition Monitoring (RCM’08), June 2008, 2008, Vol. 2216Conference paper (Refereed)
  • 42.
    Bohlin, Markus
    et al.
    RISE - Research Institutes of Sweden (2017-2019), ICT, SICS.
    Forsgren, Malin
    RISE - Research Institutes of Sweden (2017-2019), ICT, SICS.
    Holst, Anders
    RISE, Swedish ICT, SICS, Decisions, Networks and Analytics lab.
    Levin, Björn
    RISE - Research Institutes of Sweden (2017-2019), ICT, SICS.
    Aronsson, Martin
    RISE, Swedish ICT, SICS, Decisions, Networks and Analytics lab.
    Steinert, Rebecca
    RISE, Swedish ICT, SICS, Decisions, Networks and Analytics lab.
    Reducing vehicle maintenance using condition monitoring and dynamic planning2008In: Proceedings of the 4th IET International Conference on Railway Condition Monitoring (RCM'08), 2008, 1Conference paper (Refereed)
  • 43.
    Bohlin, Markus
    et al.
    RISE - Research Institutes of Sweden (2017-2019), SICS, Sweden.
    Gestrelius, Sara
    RISE., SICS.
    Optimerad rangering: slutsatser och resultat från projektet RANPLAN2013Report (Other academic)
    Abstract [sv]

    Sammanfattning Rapporten innehåller kortfattade slutsatser och resultat från en studie genomförd i projektet RANPLAN, som har utförts av SICS Swedish ICT AB på uppdrag av Trafikverket under åren 2010-2013. Fokus är på Hallsbergs rangerbangård, men resultaten är tillämpbara även på andra rangerbangårdar med vall. Datorkörningar visar att blanddragen kan öka kapaciteten på rangerbangårdar väsentligt, mätt i antalet samtidiga tåg som kan hanteras, till en kostnad av en ökad mängd vagnsrörelser. I en jämförande datorstudie av simulering och optimering framgick också att de optimala planerna var betydligt effektivare, mätt i antalet vagnsrörelser, än de simulerade planerna. Resultaten pekar tydligt på att datorstödd optimering av planeringsprocessen för rangerbangårdar både är praktiskt möjligt och kan ge stora effektivitetsvinster.

  • 44.
    Bohlin, Markus
    et al.
    RISE - Research Institutes of Sweden (2017-2019), ICT, SICS.
    Gestrelius, Sara
    RISE, Swedish ICT, SICS.
    Optimerad rangering: slutsatser och resultat från projektet RANPLAN2013Report (Other academic)
    Abstract [sv]

    Sammanfattning Rapporten innehåller kortfattade slutsatser och resultat från en studie genomförd i projektet RANPLAN, som har utförts av SICS Swedish ICT AB på uppdrag av Trafikverket under åren 2010-2013. Fokus är på Hallsbergs rangerbangård, men resultaten är tillämpbara även på andra rangerbangårdar med vall. Datorkörningar visar att blanddragen kan öka kapaciteten på rangerbangårdar väsentligt, mätt i antalet samtidiga tåg som kan hanteras, till en kostnad av en ökad mängd vagnsrörelser. I en jämförande datorstudie av simulering och optimering framgick också att de optimala planerna var betydligt effektivare, mätt i antalet vagnsrörelser, än de simulerade planerna. Resultaten pekar tydligt på att datorstödd optimering av planeringsprocessen för rangerbangårdar både är praktiskt möjligt och kan ge stora effektivitetsvinster.

    Download full text (pdf)
    FULLTEXT01
  • 45.
    Bohlin, Markus
    et al.
    RISE - Research Institutes of Sweden (2017-2019), SICS.
    Gestrelius, Sara
    RISE., SICS.
    Optimerad rangering: slutsatser och resultat från projektet RANPLAN2013Report (Other academic)
    Abstract [sv]

    Rapporten innehåller kortfattade slutsatser och resultat från en studie genomförd i projektet RANPLAN, som har utförts av SICS Swedish ICT AB på uppdrag av Trafikverket under åren 2010-2013. Fokus är på Hallsbergs rangerbangård, men resultaten är tillämpbara även på andra rangerbangårdar med vall. Datorkörningar visar att blanddragen kan öka kapaciteten på rangerbangårdar väsentligt, mätt i antalet samtidiga tåg som kan hanteras, till en kostnad av en ökad mängd vagnsrörelser. I en jämförande datorstudie av simulering och optimering framgick också att de optimala planerna var betydligt effektivare, mätt i antalet vagnsrörelser, än de simulerade planerna. Resultaten pekar tydligt på att datorstödd optimering av planeringsprocessen för rangerbangårdar både är praktiskt möjligt och kan ge stora effektivitetsvinster.

    Download full text (pdf)
    FULLTEXT01
  • 46.
    Bohlin, Markus
    et al.
    SICS Swedish ICT AB, Sweden.
    Gestrelius, Sara
    SICS Swedish ICT AB, Sweden.
    Dahms, Florian
    RWTH Aachen University, Germany.
    Mihalák, Matúš
    ETH Zürich, Switzerland.
    Flier, Holger
    ETH Zürich, Switzerland.
    Optimization Methods for Multistage Freight Train Formation2015In: Transportation Science, ISSN 0041-1655, E-ISSN 1526-5447, Vol. 50, no 3, p. 823-840Article in journal (Refereed)
  • 47.
    Bohlin, Markus
    et al.
    RISE - Research Institutes of Sweden (2017-2019), ICT, SICS.
    Gestrelius, Sara
    RISE, Swedish ICT, SICS.
    Dahms, Florian
    RWTH Aachen University, Germany.
    Mihalák, Matúš
    ETH Zurich, Switzerland.
    Flier, Holger
    ETH Zurich, Switzerland.
    Optimization Methods for Multistage Freight Train Formation2015In: Transportation Science, ISSN 0041-1655, E-ISSN 1526-5447, Vol. 50, no 3, p. 823-840Article in journal (Refereed)
    Abstract [en]

    This paper considers mathematical optimization for the multistage train formation problem, which at the core is the allocation of classification yard formation tracks to outbound freight trains, subject to realistic constraints on train scheduling, arrival and departure timeliness, and track capacity. The problem formulation allows the temporary storage of freight cars on a dedicated mixed-usage track. This real-world practice increases the capacity of the yard, measured in the number of simultaneous trains that can be successfully handled. Two optimization models are proposed and evaluated for the multistage train formation problem. The first one is a column-based integer programming model, which is solved using branch and price. The second model is a simplified reformulation of the first model as an arc-indexed integer linear program, which has the same linear programming relaxation as the first model. Both models are adapted for rolling horizon planning and evaluated on a five-month historical data set from the largest freight yard in Scandinavia. From this data set, 784 instances of different types and lengths, spanning from two to five days, were created. In contrast to earlier approaches, all instances could be solved to optimality using the two models. In the experiments, the arc-indexed model proved optimality on average twice as fast as the column-based model for the independent instances, and three times faster for the rolling horizon instances. For the arc-indexed model, the average solution time for a reasonably sized planning horizon of three days was 16 seconds. Regardless of size, no instance took longer than eight minutes to be solved. The results indicate that optimization approaches are suitable alternatives for scheduling and track allocation at classification yards.

  • 48.
    Bohlin, Markus
    et al.
    RISE - Research Institutes of Sweden (2017-2019), SICS, Sweden.
    Gestrelius, Sara
    RISE., SICS.
    Dahms, Florian
    Mihalák, Matúš
    Flier, Holger
    Optimized shunting with mixed-usage tracks2013Report (Other academic)
    Abstract [en]

    We consider the planning of railway freight classification at hump yards, where the problem involves the formation of departing freight train blocks from arriving trains subject to scheduling and capacity constraints. The hump yard layout considered consists of arrival tracks of sufficient length at an arrival yard, a hump, classification tracks of non-uniform and possibly non-sufficient length at a classification yard, and departure tracks of sufficient length. To increase yard capacity, freight cars arriving early can be stored temporarily on specific mixed-usage tracks. The entire hump yard planning process is covered in this paper, and heuristics for arrival and departure track assignment, as well as hump scheduling, have been included to provide the neccessary input data. However, the central problem considered is the classification track allocation problem. This problem has previously been modeled using direct mixed integer programming models, but this approach did not yield lower bounds of sufficient quality to prove optimality. Later attempts focused on a column generation approach based on branch-and-price that could solve problem instances of industrial size. Building upon the column generation approach we introduce a direct arc-based integer programming model, where the arcs are precedence relations between blocks on the same classification track. Further, the most promising models are adapted for rolling-horizon planning. We evaluate the methods on historical data from the Hallsberg shunting yard in Sweden. The results show that the new arc-based model performs as well as the column generation approach. It returns an optimal schedule within the execution time limit for all instances but from one, and executes as fast as the column generation approach. Further, the short execution times of the column generation approach and the arc-indexed model make them suitable for rolling-horizon planning, while the direct mixed integer program proved to be too slow for this. Extended analysis of the results shows that mixing was only required if the maximum number of concurrent trains on the classification yard exceeds 29 (there are 32 available tracks), and that after this point the number of extra car roll-ins increases heavily.

  • 49.
    Bohlin, Markus
    et al.
    RISE - Research Institutes of Sweden (2017-2019), ICT, SICS.
    Gestrelius, Sara
    RISE, Swedish ICT, SICS.
    Dahms, Florian
    Mihalák, Matúš
    Flier, Holger
    Optimized shunting with mixed-usage tracks2013Report (Other academic)
    Abstract [en]

    We consider the planning of railway freight classification at hump yards, where the problem involves the formation of departing freight train blocks from arriving trains subject to scheduling and capacity constraints. The hump yard layout considered consists of arrival tracks of sufficient length at an arrival yard, a hump, classification tracks of non-uniform and possibly non-sufficient length at a classification yard, and departure tracks of sufficient length. To increase yard capacity, freight cars arriving early can be stored temporarily on specific mixed-usage tracks. The entire hump yard planning process is covered in this paper, and heuristics for arrival and departure track assignment, as well as hump scheduling, have been included to provide the neccessary input data. However, the central problem considered is the classification track allocation problem. This problem has previously been modeled using direct mixed integer programming models, but this approach did not yield lower bounds of sufficient quality to prove optimality. Later attempts focused on a column generation approach based on branch-and-price that could solve problem instances of industrial size. Building upon the column generation approach we introduce a direct arc-based integer programming model, where the arcs are precedence relations between blocks on the same classification track. Further, the most promising models are adapted for rolling-horizon planning. We evaluate the methods on historical data from the Hallsberg shunting yard in Sweden. The results show that the new arc-based model performs as well as the column generation approach. It returns an optimal schedule within the execution time limit for all instances but from one, and executes as fast as the column generation approach. Further, the short execution times of the column generation approach and the arc-indexed model make them suitable for rolling-horizon planning, while the direct mixed integer program proved to be too slow for this. Extended analysis of the results shows that mixing was only required if the maximum number of concurrent trains on the classification yard exceeds 29 (there are 32 available tracks), and that after this point the number of extra car roll-ins increases heavily.

    Download full text (pdf)
    FULLTEXT01
  • 50.
    Bohlin, Markus
    et al.
    SICS Swedish ICT, Kista, Sweden.
    Gestrelius, Sara
    SICS Swedish ICT, Kista, Sweden.
    Fahimeh, Khoshniyat
    SICS Swedish ICT, Kista, Sweden.
    Simulation of planning strategies for track allocation at marshalling yards2013In: WIT Transactions on Modelling and Simulation, Volume 55, 2013, Ashurst, Southampton: WIT Press, 2013, Vol. 55, p. 465-475Conference paper (Refereed)
    Abstract [en]

    Planning the operational procedures in a railway marshalling yard is a complex problem. When a train arrives at a marshalling yard, it is uncoupled at an arrival yard and then its cars are rolled to a classification yard. All cars should eventually be rolled to the classification track that has been assigned to the train they're supposed to depart with. However, there is normally not enough capacity to compound all trains at once. In Sweden, cars arriving before a track has been assigned to their train can be stored on separate tracks called mixing tracks. All cars on mixing tracks will be pulled back to the arrival yard, and then rolled to the classification yard again to allow for reclassification. Today all procedures are planned by experienced dispatchers, but there are no documented strategies or guidelines for efficient manual planning. The aim of this paper is to examine operational planning strategies that could help dispatchers find a feasible marshalling schedule that minimizes unnecessary mixing. In order to achieve this goal, two different online planning strategies have been tested using deterministic and stochastic simulation. The Hallsberg marshalling yard was used as a case study, and was simulated for the time period between December 2010 and May 2011. The first tested strategy simply assigns tracks to trains on a first come-first served basis, while the second strategy uses time limits to determine when tracks should be assigned to departing trains. The online planning algorithms have been compared with an offline optimized track allocation. The results from both the deterministic and the stochastic simulation show that the optimized allocation is better than all online strategies and that the second strategy with a time limit of 32 hours is the best online method.

12345 1 - 50 of 211
CiteExportLink to result list
Permanent link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf