Take a look at the new version of this page: [ beta version ]. Tell us what you think.

ABSTRACT

Real time dispatching strategies in a dynamic environment is a growing area of interest. Most of current work focuses mainly on two dynamic aspects of the problem, namely dynamic arrival of jobs and dynamic travel time. The degree of dynamism, for example is defined with respect to dynamic arrival of jobs. This paper focuses on another dynamic aspect, namely the duration of tasks. This aspect becomes important when tasks durations are relatively long and, in addition, one has to respect time windows. We characterize the degree of dynamism of such problems and show that it relates with the expected cost of a static scheduler which is reapplied in light of dynamic events. Furthermore, preliminary experiments indicate that the performance of the scheduler can be improved when the expected duration of a task is overestimated.

REFERENCES

• 1: S. Baker. Applying simulated annealing to the workforce management problem. Technical report, British Telecom Laboratories, 1993.
• 2: Russell W. Bent , Pascal Van Hentenryck, Scenario-Based Planning for Partially Dynamic Vehicle Routing with Stochastic Customers, Operations Research, v.52 n.6, p.977-987, November 2004 [doi>10.1287/opre.1040.0124]
• 3: Jürgen Branke , Martin Middendorf , Guntram Noeth , Maged Dessouky, Waiting Strategies for Dynamic Vehicle Routing, Transportation Science, v.39 n.3, p.298-312, August 2005 [doi>10.1287/trsc.1040.0095]
• 4: R. Dorne , C. Voudouris , A. Liret , C. Ladde , D. Lesaint, iSchedule — An Optimisation Tool-Kit Based on Heuristic Search to Solve BT Scheduling Problems, BT Technology Journal, v.21 n.4, p.50-58, 2003 [doi>10.1023/A:1027375302779]
• 5: A.T. Ernst, H. Jiang, M. Krishnamoorthy, and D. Sier. Staff scheduling and rostering: A review of applications, methods and models. European Journal of Operational Research, 153(1):3--27, February 2004.
• 6: Michel Gendreau , Francois Guertin , Jean-Yves Potvin , Eric Taillard, Parallel Tabu Search for Real-Time Vehicle Routing and Dispatching, Transportation Science, v.33 n.4, p.381-390, April 1999 [doi>10.1287/trsc.33.4.381]
• 7: G.L.R.M. Gianpaolo Ghiani, Francesca Guerriero. Real-time vehicle routing: Solution concepts, algorithms and parallel computing strategies. European Journal of Operational Research, 151:1--11, 2003.
• 8: F. Glover and G. Kochenberger. Handbook of Metaheuristics (International Series in Operations Research & Management Science). Springer, 2003.
• 9: Soumia Ichoua , Michel Gendreau , Jean-Yves Potvin, Exploiting Knowledge About Future Demands for Real-Time Vehicle Dispatching, Transportation Science, v.40 n.2, p.211-225, May 2006 [doi>10.1287/trsc.1050.0114]
• 10: O.B.M. Karsten Lund and J.M. Rygaard. Vehicle routing problems with varying degrees of dynamism. Technical report, IMM Department of Mathematical Modelling, The Technical University of Denmark, 1996.
• 11: R. Kolisch and S. Hartmann. Experimental investigation of heuristics for resource-constrained project scheduling: An update. European Journal of Operational Research, 174(1):23--37, October 2006.
• 12: A. Larsen, O.B.G. Madsen, and M.M. Solomon. Partially dynamic vehicle routing--models and algorithms. Journal of the Operational Research Society,, 53(6):637--646, 2002.
• 13: Allan Larsen , Oli B. G. Madsen , Marius M. Solomon, The A Priori Dynamic Traveling Salesman Problem with Time Windows, Transportation Science, v.38 n.4, p.459-472, November 2004 [doi>10.1287/trsc.1030.0070]
• 14: David Lesaint , Christos Voudouris , Nader Azarmi, Dynamic Workforce Scheduling for British Telecommunications plc, Interfaces, v.30 n.1, p.45-56, January 2000 [doi>10.1287/inte.30.1.45.11615]
• 15: J. Lever, M. Wallace, and B. Richards. Constraint logic programming for scheduling and planning. British Telecom Technology Journal, 13(No.1):73--80, 1995.
• 16: C. Muller, E. Magill, and D. Smith. Distributed genetic algorithms for resource allocation. Technical report, Strathclyde University, 1993.
• 17: Warren B. Powell , Michael T. Towns , Arun Marar, On the Value of Optimal Myopic Solutions for Dynamic Routing and Scheduling Problems in the Presence of User Noncompliance, Transportation Science, v.34 n.1, p.67-85, February 2000 [doi>10.1287/trsc.34.1.67.12283]
• 18: M. M. Solomon, Algorithms for the vehicle routing and scheduling problems with time window constraints, Operations Research, v.35 n.2, p.254-265, March-April 1987 [doi>10.1287/opre.35.2.254]
• 19: E. Tsang and C. Voudouris. Fast local search and guided local search and their application to british telecom's workforce scheduling problem. Operations Research Letters, 20(3):119--127, 1997.
• 20: E. Tsang and C. Voudouris. Fast local search and guided local search and their application to british telecom's workforce scheduling problem. Operations Research Letters, Elsevier Science Publishers, Amsterdam, 20(3):119--127, 1997.
• 21: C. Voudouris and E. Tsang. Guided local search. In F. Glover, editor, Handbook of metaheuristics, pages 185--218. Kluwer, 2003.
• 22: R. Yang. Solving a workforce management problem with constraint programming. In The 2nd International Conference on the Practical Application of Constraint Technology, page 373--387, 1996.

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.4 INFORMATION SYSTEMS APPLICATIONS
      H.4.0 General

General Terms:
Algorithms

Keywords:
dynamic scheduling, estimation, planning