Abstract
A relevant class of real-world scheduling problems, e.g. for assembly lines, service centres but also for surgeries in operation rooms are characterised by contiguous tasks. These tasks are non-preemptive, non-overlapping, and especially without any time gaps. All tasks are performed without any breaks between any two tasks. Each task will start immediately after its direct predecessor, if there is any.
For these contiguous task scheduling problems a specialised search algorithm called Reduce-To-The-Opt is presented and its correctness is proved. Applied to trivial problems, where any linear ordering of the tasks solves the problem, this search algorithm also performs in linear time with respect to the number of tasks. For practical optimization problems, where the tasks have to be ordered optimally with respect to an objective function, runtime comparisons have shown that Reduce-To-The-Opt performs much better than a well-known heuristic-based search algorithm often used for the more general job-shop scheduling problems and even better than simple depth-first search because only the minimal value of each variable has to be selected instead of all possible values.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
CHIP System Documentation – Volume 1 – CHIP++ Reference Manual. Parc Club Orsay Université, 4, rue Jean Rostand, 91893 ORSAY Cedex, France, version 5.4 (August 2001)
Apt, K.R.: From chaotic iteration to constraint propagation. In: Degano, P., Gorrieri, R., Marchetti-Spaccamela, A. (eds.) ICALP 1997. LNCS, vol. 1256, pp. 36–55. Springer, Heidelberg (1997)
Baptiste, P., le Pape, C., Nuijten, W.: Constraint-Based Scheduling. International Series in Operations Research & Management Science, vol. 39. Kluwer Academic Publishers, Dordrecht (2001)
Beldiceanu, N., Carlsson, M.: Sweep as a generic pruning technique applied to the non-overlapping rectangles constraint. In: Walsh, T. (ed.) CP 2001. LNCS, vol. 2239, pp. 377–391. Springer, Heidelberg (2001)
Carlier, J., Pinson, E.: Adjustments of heads and tails for the job-shop problem. European Journal of Operational Research (78), 146–161 (1994)
Caseau, Y., Laburthe, F.: Improved CLP scheduling with task intervals. In: van Hentenryck, P. (ed.) Proceedings of the Eleventh International Conference on Logic Programming, ICLP 1994, pp. 369–383. MIT Press, Cambridge (1994)
Colombani, Y.: Constraint programming: an efficient and practical approach to solving the job-shop problem. In: Freuder, E.C. (ed.) CP 1996. LNCS, vol. 1118, pp. 149–163. Springer, Heidelberg (1996)
Hoche, M., Müller, H., Schlenker, H., Wolf, A.: firstcs - A Pure Java Constraint Programming Engine. In: Hanus, M., Hofstedt, P., Wolf, A. (eds.) 2nd International Workshop on Multiparadigm Constraint Programming Languages – MultiCPL 2003, September 29 (2003), Online available at uebb.cs.tu-berlin.de/MultiCPL03/Proceedings.MultiCPL03.RCoRP03.pdf
ILOG SA, 9, rue de Verdun, BP 85, 94253 Gentilly Cedex, France. ILOG Scheduler – User’s Manual, version 5.0 (July 2000)
International Computers Limited and Imperical College London. ECLiPSe Constraint Library Manual, release 5.7 (December 2003)
Intelligent Systems Laboratory. SICStus Prolog User’s Manual. Swedish Institute of Computer Science, PO Box 1263, SE-16429 Kista, Sweden, release 3.11.0 (October 2003)
Martin, P.D., Shmoys, D.B.: A new approach to computing optimal schedules for the job-shop scheduling problem. In: Proceedings of the 5th Conference on Integer Programming and Combinatorical Optimization (1996)
Prosser, P.: Hybrid algorithms for the constraint satisfaction problem. Computational Intelligence 9(3), 268–299 (1993); (Also available as Technical Report AISL-46-91, Stratchclyde, 1991)
Schlenker, H.: Reduce-To-The-Max: Ein schneller Algorithmus für Multi- Ressourcen-Probleme. In: Bry, F., Geske, U., Seipel, D. (eds.) 14. Workshop Logische Programmierung, January 26-28. GMD Report, vol. 90, pp. 55–64 (2000)
Schulte, C., Smolka, G.: Finite Domain Constraint Programming in OZ – A Tutorial. The Mozart Programming System, version 1.2.5, January 25 (2003)
Wolf, A.: Pruning while sweeping over task intervals. In: Rossi, F. (ed.) CP 2003. LNCS, vol. 2833, pp. 739–753. Springer, Heidelberg (2003)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2004 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Wolf, A. (2004). Reduce-To-The-Opt – A Specialized Search Algorithm for Contiguous Task Scheduling. In: Apt, K.R., Fages, F., Rossi, F., Szeredi, P., Váncza, J. (eds) Recent Advances in Constraints. CSCLP 2003. Lecture Notes in Computer Science(), vol 3010. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-24662-6_12
Download citation
DOI: https://doi.org/10.1007/978-3-540-24662-6_12
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-21834-0
Online ISBN: 978-3-540-24662-6
eBook Packages: Springer Book Archive