Abstract
In this paper we show how the problem of job-shop scheduling where the jobs are preemptible can be modeled naturally as a shortest path problem defined on an extension of timed automata, namely stopwatch automata where some of the clocks might be freezed at certain states. Although general verification problems on stopwatch automata are known to be undecidable, we show that due to particular properties of optimal schedules, the shortest path in the automaton belongs to a finite subset of the set of acyclic paths and hence the problem is solvable. We present several algorithms and heuristics for finding the shortest paths in such automata and test their implementation on numerous benchmark examples.
This work was partially supported by the European Community Project IST-2001-35304AME-TIST http://ametist.cs.utwente.nl
By a qualitative run of a timed automaton we mean a sequence of states and transitions without metric timing information.
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
Y. Abdeddaïm and O. Maler, Job-Shop Scheduling using Timed Automata in G. Berry, H. Comon and A. Finkel (Eds.), Proc. CAV’01, 478–492, LNCS 2102, Springer 2001.
K. Altisen, G. Goessler, A. Pnueli, J. Sifakis, S. Tripakis and S. Yovine, A Framework for Scheduler Synthesis, Proc. RTSS’99, 154–163, IEEE, 1999.
R. Alur and D.L. Dill, ATheory ofTimedAutomata, Theoretical Computer Science 126, 183–235, 1994.
E. Asarin and O. Maler, As Soon as Possible: Time Optimal Control for Timed Automata, Proc. HSCC’99, 19–30, LNCS 1569, Springer, 1999.
G. Behrmann, A. Fehnker T.S. Hune, K.G. Larsen, P. Pettersson and J. Romijn, Efficient Guiding Towards Cost-Optimality in UPPAAL, Proc. TACAS 2001, 174–188, LNCS 2031, Springer, 2001.
J. Carlier and E. Pinson, A Practical Use of Jackson’s Preemptive Schedule for Solving the Job-Shop Problem, Annals of Operations Research 26, 1990.
F. Cassez and K.G. Larsen, On the Impressive Power of Stopwatches, in C. Palamidessi (Ed.) Proc. CONCUR’2000, 138–152, LNCS 1877, Springer, 2000.
K. Cerans, Algorithmic Problems in Analysis of Real Time System Specifications, Ph.D. thesis, University of Latvia, Riga, 1992.
E. Fersman, P. Pettersson and W. Yi, Timed Automata with Asynchronous Processes: Schedulability and Decidability, TACAS 2002, this volume, 2002.
M. R. Garey and D. S Johnson, Computers and Intractability,A Guide to the Theory of NP-Completeness,W. H. Freeman and Company, 1979.
J. R. Jackson, Scheduling a Production Line to Minimize Maximum Tardiness, Research Report 43, Management Sciences Research Project, UCLA, 1955.
A.S. Jain and S. Meeran, Deterministic Job-Shop Scheduling: Past, Present and Future, European Journal of Operational Research 113, 390–434, 1999.
Y. Kesten, A. Pnueli, J. Sifakis and S. Yovine, Decidable Integration Graphs, Information and Computation 150, 209–243, 1999.
J. McManis and P. Varaiya, Suspension Automata: A Decidable Class of Hybrid Automata, in D.L Dill (Ed.), Proc. CAV’94, 105–117, LNCS 818, Springer, 1994.
P. Niebert, S. Tripakis S. Yovine, Minimum-Time Reachability for Timed Automata, IEEE Mediteranean Control Conference, 2000.
P. Niebert and S. Yovine, Computing Efficient Operation Schemes for Chemical Plants in Multi-batch Mode, European Journal of Control 7, 440–453, 2001.
C. Le Pape and P. Baptiste, A Constraint-Based Branch-and-Bound Algorithm for Preemptive Job-Shop Scheduling, Proc. of Int.Workshop on Production Planning and Control, Mons, Belgium, 1996.
C. Le Pape and P. Baptiste, An Experimental Comparaison of Constraint-Based Algorithms for the Preemptive Job-shop Sheduling Problem, CP97 Workshop on Industrial Constraint-Directed Scheduling, 1997.
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2002 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Abdeddaïm, Y., Maler, O. (2002). Preemptive Job-Shop Scheduling Using Stopwatch Automata. In: Katoen, JP., Stevens, P. (eds) Tools and Algorithms for the Construction and Analysis of Systems. TACAS 2002. Lecture Notes in Computer Science, vol 2280. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-46002-0_9
Download citation
DOI: https://doi.org/10.1007/3-540-46002-0_9
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-43419-1
Online ISBN: 978-3-540-46002-2
eBook Packages: Springer Book Archive