A Dynamic Programming Approach for Emergency Vehicle Dispatching Problems
0
조회
0
다운로드
0
인용
0
참고문헌
키워드
초록
In this research, emergency vehicle dispatching problems faced with in the wake of massive natural disasters are considered. Here, the emergency vehicle dispatching problems can be regarded as a single machine stochastic scheduling problems, where the processing times are independently and identically distributed random variables, are considered. The objective of minimizing the expected number of tardy jobs, with distinct job due dates that are independently and arbitrarily distributed random variables, is dealt with. For these problems, optimal static-list policies can be found by solving corresponding assignment problems. However, for the special cases where due dates are exponentially distributed random variables, using a proposed dynamic programming approach is found to be relatively faster than solving the corresponding assignment problems. This so-called Pivot Dynamic Programming approach exploits necessary optimality conditions derived for ordering the jobs partially.
Abstract
In this research, emergency vehicle dispatching problems faced with in the wake of massive natural disasters are considered. Here, the emergency vehicle dispatching problems can be regarded as a single machine stochastic scheduling problems, where the processing times are independently and identically distributed random variables, are considered. The objective of minimizing the expected number of tardy jobs, with distinct job due dates that are independently and arbitrarily distributed random variables, is dealt with. For these problems, optimal static-list policies can be found by solving corresponding assignment problems. However, for the special cases where due dates are exponentially distributed random variables, using a proposed dynamic programming approach is found to be relatively faster than solving the corresponding assignment problems. This so-called Pivot Dynamic Programming approach exploits necessary optimality conditions derived for ordering the jobs partially.
참고문헌 (19)
- S. J. Balut, "Scheduling to Minimize the Number of Late Jobs When Set-Up and Processing Times are Uncertain", Management Science, 19(11), pp.1283~1288 (1973)
- R. A. Blau, "N-Job, One Machine Sequencing Problems under Uncertainty", Management Science, 20(1), pp.101~109 (1973)
- O. J. Boxma, "Minimizing the Expected Weighted Number of Tardy Jobs in Stochastic Flow Shops", Operations Research Letters, 5, pp.119~126 (1986)
- X. Cai, "Stochastic Scheduling on Parallel Machines subject to Random Breakdowns to Minimize Expected Costs for Earliness and Tardy Jobs", Operations Research, 47(3), pp.422~437 (1999)
- C-S. Chang, "Stochatic Modeling and Analysis of Manufacturing Systems" (1994), Springer-Verlag
- P. De, "On the Minimization of the Weighted Number of Tardy Jobs with Random Processing Times and Deadline", Computers and Operations Research, 18, pp.457~463 (1991)
- H. Emmons, "Scheduling Stochastic Jobs with Due Dates on Parallel Machines", European Journal of Operational Research, 47, pp.49~55 (1990)
- M. Held, "A Dynamic Programming Approach to Sequencing Problems", J. SIAM, 10, pp.196~210 (1962)
- W. Jang, "Dynamic Scheduling of Stochastic Jobs on a Single Machine", European Journal of Operational Research, 138, pp.518~530 (2002)
- R. M. Karp, "Complexity of Computer Computations" (1972), Plenum Press
- H. Kise, "On Balut’s Algorithm and NP-Completeness for a Chance-Constrained Scheduling Problem", Management Science, 29(3), pp.384~388 (1983)
- W. Li, "On Stochastic Machine Scheduling with General Distributional Assumptions", European Journal of Operational Research, 105, pp.525~536 (1998)
- M. J. Moore, "An N Job, One Machine Sequencing Algorithm for Minimizing the Number of Late Jobs", Management Science, 15(1), pp.102~109 (1968)
- G. R. Parker, "Discrete Optimization" (1988), Academic Press Inc
- M. Pinedo, "Stochastic Scheduling with Release Dates and Due Dates", Operations Research, 31(3), pp.559~572 (1983)
- M. Pinedo, "Scheduling : Theory, Algorithms, and Systems" (2002), Prentice-Hall Inc
- S. C. Sarin, "Sequencing Jobs on a Single Machine with a Common Due Date and Stochastic Processing Times", European Journal of Operational Research, 51, pp.188~198 (1991)
- H. M. Soroush, "The Stochastic Single Machine Scheduling Problem with Earliness and Tardiness Costs", European Journal of Operational Research, 77, pp.287~302 (1994)
- D. V. Widder, "The Laplace Transform" (1941), Princeton University Press