Online scheduling on multiple resources under stochastic conditions

• Autorzy: Thomas M. , Szczerbicka H.
• Języki publikacji: EN

Abstrakty

EN

Online scheduling (also known as dynamic scheduling) refers to a real-time coordination of operation processing while new operations are continuously arriving. Despite the attention this area received over last years, little effort has been spent on cases where multiple resources are required for an operation processed. The objective of this paper is the study of different online scheduling techniques specifically in a dynamic, stochastic job shop scheduling with multiple resources. We adopt algorithms for dispatching and optimizing schedulers to this case and provide a quantitative study of their performance under varying stochastic conditions. We also discuss the regret-based algorithm from Bent and Van Hentenryck. While this approach is superior in the case of scheduling single resource, it showed inferior performance in our experiments compared to its underlying optimizing scheduler.

Słowa kluczowe

EN

online scheduling; job shop scheduling; heuristic optimization; multiple resource scheduling

• Wydawca: Oficyna Wydawnicza Politechniki Wrocławskiej
• Czasopismo: Systems Science
• Rocznik: 2007
• Tom: Vol. 33, no 2
• Strony: 23--30
• Opis fizyczny: Bibliogr. 17 poz., wykr.

Twórcy

autor

Thomas M.

autor

Szczerbicka H.

• Leibniz Universitat Hannover, FG Simulation & Modellierung, Welfengarten 1, 30167 Hannover, Germany,

Bibliografia

• [1] Bent R., Van Hentenryck P., Regrets Only! Online Stochastic Optimization under Time Constraints, Proc. 19th National Conf. Artificial Intelligence, 2004, pp. 501-506.
• [2] Bent R., Van Hentenryck P., Upfal E., Online Stochastic Optimization under Time Constraints, (to appear).
• [3] Bierwirth C., Mattfeld D.C., Production Scheduling and Rescheduling with Genetic Algorithms, Evolutionary Computing, 7, No. 1, 1999, pp. 1-17.
• [4] Chang H.S., Givan R., Chong E.K.P., On-line Scheduling via Sampling, Artificial Intelligence Planning Systems, 2000, pp. 62-71.
• [5] Dertouzos M.L., Mok A.K., Multiprocessor Online Scheduling of Hard-Real-Time Tasks, IEEE Trans. Software Engineering, December 1989, pp. 1497-1506.
• [6] Fromherz M.P.J., Constraint-based Scheduling, American Control Conference, Arlington, VA, June 2001.
• [7] Gere W.S., Heuristics in Job Shop Scheduling, Management Science, 13, 1966, pp. 167-190.
• [8] Goyal S.K., Mehta K., Kodali R., Deshmukh S.G., Simulation for Analysis of Scheduling Rules for a Flexible Manufacturing System, Integrated Manufacturing Systems, 6, No. 5, 1996, pp. 21-26.
• [9] Kim J.-H., Chwa K.-Y., On-Line Deadline Scheduling on Multiple Resources, Proc. 7lh Annual Int. Conf. Computing and Combinatorics, August 2001, pp. 443-452.
• [10] Lee J.-H., Online deadline scheduling: Multiple Machines and Randomization, Proc. 15th Annual ACM Symp. Parallel Algorithms and Architectures, June 2003, pp. 19-23.
• [11] Leinberger W., Karypis G., Kumar V., Job Scheduling in the Presence of Multiple Resource Requirements. Proc. ACM/IEEE Conf. Supercomputing, 1999.
• [12] Montana D., A Comparison of Combinatorial Optimization and Dispatch Rules for Online Scheduling, Proc. 2nd Multidisciplinary Conf. Scheduling: Theory and Application, 2005, pp. 353-362.
• [13] Panwalkcr S., Iskander W., A Survey of Scheduling Rules, Operations Research, 25, No. 1, 1977) pp. 45-61.
• [14] Policella N., Scheduling with Uncertainty - A Proactive Approach Using Partial Order Schedules, Ph.D. Thesis, University of Rome “La Sapienza”, March 2005.
• [15] Smith S.F., OPIS: A Methodology and Architecture for Reactive Scheduling, Intelligent Scheduling, 1994, pp. 29-66.
• [16] Sun R.-L., Li H.-X., Xiong Y., Performance-Oriented Integrated Control of Production Scheduling, IEEE Trans. Systems, Man, and Cybernetics, 36, No. 4, 2006, pp. 554-562.
• [17] Thomas M., Szczerbicka H., Evaluating Online Scheduling Techniques in Uncertain Environments, 3rd Multidisciplinary Conf. Scheduling: Theory and Application, (2007), submitted.