Scheduling lacquer production by reachability analysis - A case study

Gerd Behrmann, Hendrik Brinksma, Martijn Hendriks, Angelika H. Mader

Abstract

We describe a case study on lacquer production scheduling that was performed in the European IST-project AMETIST and was provided by one of the industrial partners. The approach is to derive schedules by means of reachability analysis: with this technique the search mechanism of model checkers, in our case here Uppaal, is used to find feasible or optimal schedules. The advantage of this approach is that the expressiveness of timed automata allows to model scheduling problems of different kinds, unlike many classical approaches, and the problem class is robust against changes in the parameter setting. To fight the typical state space explosion problem a number of standard heuristics have to be used. We discuss the difficulties when modelling an industrial case of this kind, describe the experiments we performed, the heuristics used, and the techniques applied to allow to optimize costs (storage costs, delay costs, etc.) while searching for schedules.
Original languageUndefined
Title of host publication16th IFAC World Congress
EditorsP Horacek, M Simandl, P Zitek
Place of PublicationLaxenburg, Austria
PublisherELSEVIER
PagesMoA17TO3
ISBN (Print)not assigned
DOIs
StatePublished - Jul 2005
Event16th IFAC World Congress 2005 - Prague, Czech Republic

Conference

Conference16th IFAC World Congress 2005
CountryCzech Republic
CityPrague
Period3/07/058/07/05
Internet address

Fingerprint

Costs
Scheduling
Lacquers
Explosions
Experiments

Keywords

  • EWI-689
  • IR-54530
  • METIS-228786

Cite this

Behrmann, G., Brinksma, H., Hendriks, M., & Mader, A. H. (2005). Scheduling lacquer production by reachability analysis - A case study. In P. Horacek, M. Simandl, & P. Zitek (Eds.), 16th IFAC World Congress (pp. MoA17TO3). Laxenburg, Austria: ELSEVIER. DOI: 10.3182/20050703-6-CZ-1902.01433

Behrmann, Gerd; Brinksma, Hendrik; Hendriks, Martijn; Mader, Angelika H. / Scheduling lacquer production by reachability analysis - A case study.

16th IFAC World Congress. ed. / P Horacek; M Simandl; P Zitek. Laxenburg, Austria : ELSEVIER, 2005. p. MoA17TO3.

Research output: Scientific - peer-reviewConference contribution

@inbook{d425425034b74634be3b103fae2772e5,
title = "Scheduling lacquer production by reachability analysis - A case study",
abstract = "We describe a case study on lacquer production scheduling that was performed in the European IST-project AMETIST and was provided by one of the industrial partners. The approach is to derive schedules by means of reachability analysis: with this technique the search mechanism of model checkers, in our case here Uppaal, is used to find feasible or optimal schedules. The advantage of this approach is that the expressiveness of timed automata allows to model scheduling problems of different kinds, unlike many classical approaches, and the problem class is robust against changes in the parameter setting. To fight the typical state space explosion problem a number of standard heuristics have to be used. We discuss the difficulties when modelling an industrial case of this kind, describe the experiments we performed, the heuristics used, and the techniques applied to allow to optimize costs (storage costs, delay costs, etc.) while searching for schedules.",
keywords = "EWI-689, IR-54530, METIS-228786",
author = "Gerd Behrmann and Hendrik Brinksma and Martijn Hendriks and Mader, {Angelika H.}",
note = "Imported from DIES",
year = "2005",
month = "7",
doi = "10.3182/20050703-6-CZ-1902.01433",
isbn = "not assigned",
pages = "MoA17TO3",
editor = "P Horacek and M Simandl and P Zitek",
booktitle = "16th IFAC World Congress",
publisher = "ELSEVIER",

}

Behrmann, G, Brinksma, H, Hendriks, M & Mader, AH 2005, Scheduling lacquer production by reachability analysis - A case study. in P Horacek, M Simandl & P Zitek (eds), 16th IFAC World Congress. ELSEVIER, Laxenburg, Austria, pp. MoA17TO3, 16th IFAC World Congress 2005, Prague, Czech Republic, 3-8 July. DOI: 10.3182/20050703-6-CZ-1902.01433

Scheduling lacquer production by reachability analysis - A case study. / Behrmann, Gerd; Brinksma, Hendrik; Hendriks, Martijn; Mader, Angelika H.

16th IFAC World Congress. ed. / P Horacek; M Simandl; P Zitek. Laxenburg, Austria : ELSEVIER, 2005. p. MoA17TO3.

Research output: Scientific - peer-reviewConference contribution

TY - CHAP

T1 - Scheduling lacquer production by reachability analysis - A case study

AU - Behrmann,Gerd

AU - Brinksma,Hendrik

AU - Hendriks,Martijn

AU - Mader,Angelika H.

N1 - Imported from DIES

PY - 2005/7

Y1 - 2005/7

N2 - We describe a case study on lacquer production scheduling that was performed in the European IST-project AMETIST and was provided by one of the industrial partners. The approach is to derive schedules by means of reachability analysis: with this technique the search mechanism of model checkers, in our case here Uppaal, is used to find feasible or optimal schedules. The advantage of this approach is that the expressiveness of timed automata allows to model scheduling problems of different kinds, unlike many classical approaches, and the problem class is robust against changes in the parameter setting. To fight the typical state space explosion problem a number of standard heuristics have to be used. We discuss the difficulties when modelling an industrial case of this kind, describe the experiments we performed, the heuristics used, and the techniques applied to allow to optimize costs (storage costs, delay costs, etc.) while searching for schedules.

AB - We describe a case study on lacquer production scheduling that was performed in the European IST-project AMETIST and was provided by one of the industrial partners. The approach is to derive schedules by means of reachability analysis: with this technique the search mechanism of model checkers, in our case here Uppaal, is used to find feasible or optimal schedules. The advantage of this approach is that the expressiveness of timed automata allows to model scheduling problems of different kinds, unlike many classical approaches, and the problem class is robust against changes in the parameter setting. To fight the typical state space explosion problem a number of standard heuristics have to be used. We discuss the difficulties when modelling an industrial case of this kind, describe the experiments we performed, the heuristics used, and the techniques applied to allow to optimize costs (storage costs, delay costs, etc.) while searching for schedules.

KW - EWI-689

KW - IR-54530

KW - METIS-228786

U2 - 10.3182/20050703-6-CZ-1902.01433

DO - 10.3182/20050703-6-CZ-1902.01433

M3 - Conference contribution

SN - not assigned

SP - MoA17TO3

BT - 16th IFAC World Congress

PB - ELSEVIER

ER -

Behrmann G, Brinksma H, Hendriks M, Mader AH. Scheduling lacquer production by reachability analysis - A case study. In Horacek P, Simandl M, Zitek P, editors, 16th IFAC World Congress. Laxenburg, Austria: ELSEVIER. 2005. p. MoA17TO3. Available from, DOI: 10.3182/20050703-6-CZ-1902.01433