A Dynamic Programming Approach for Emergency Vehicle Dispatching Problems
2016, 21(9), pp.91-100
Publisher : The Korean Society Of Computer And Information
Research Area : Computer Science
-
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.
-
[journal] S. J. Balut / 1973 / Scheduling to Minimize the Number of Late Jobs When Set-Up and Processing Times are Uncertain / Management Science 19(11) : 1283~1288
[journal] R. A. Blau / 1973 / N-Job, One Machine Sequencing Problems under Uncertainty / Management Science 20(1) : 101~109
[journal] O. J. Boxma / 1986 / Minimizing the Expected Weighted Number of Tardy Jobs in Stochastic Flow Shops / Operations Research Letters 5 : 119~126
[journal] X. Cai / 1999 / Stochastic Scheduling on Parallel Machines subject to Random Breakdowns to Minimize Expected Costs for Earliness and Tardy Jobs / Operations Research 47(3) : 422~437
[book] C-S. Chang / 1994 / Stochatic Modeling and Analysis of Manufacturing Systems / Springer-Verlag
[journal] P. De / 1991 / On the Minimization of the Weighted Number of Tardy Jobs with Random Processing Times and Deadline / Computers and Operations Research 18 : 457~463
[journal] H. Emmons / 1990 / Scheduling Stochastic Jobs with Due Dates on Parallel Machines / European Journal of Operational Research 47 : 49~55
[journal] M. Held / 1962 / A Dynamic Programming Approach to Sequencing Problems / J. SIAM 10 : 196~210
[journal] W. Jang / 2002 / Dynamic Scheduling of Stochastic Jobs on a Single Machine / European Journal of Operational Research 138 : 518~530
[book] R. M. Karp / 1972 / Complexity of Computer Computations / Plenum Press
[journal] H. Kise / 1983 / On Balut’s Algorithm and NP-Completeness for a Chance-Constrained Scheduling Problem / Management Science 29(3) : 384~388
[journal] W. Li / 1998 / On Stochastic Machine Scheduling with General Distributional Assumptions / European Journal of Operational Research 105 : 525~536
[journal] M. J. Moore / 1968 / An N Job, One Machine Sequencing Algorithm for Minimizing the Number of Late Jobs / Management Science 15(1) : 102~109
[book] G. R. Parker / 1988 / Discrete Optimization / Academic Press Inc
[journal] M. Pinedo / 1983 / Stochastic Scheduling with Release Dates and Due Dates / Operations Research 31(3) : 559~572
[book] M. Pinedo / 2002 / Scheduling : Theory, Algorithms, and Systems / Prentice-Hall Inc
[journal] S. C. Sarin / 1991 / Sequencing Jobs on a Single Machine with a Common Due Date and Stochastic Processing Times / European Journal of Operational Research 51 : 188~198
[journal] H. M. Soroush / 1994 / The Stochastic Single Machine Scheduling Problem with Earliness and Tardiness Costs / European Journal of Operational Research 77 : 287~302
[book] D. V. Widder / 1941 / The Laplace Transform / Princeton University Press
-
KCI Citation (0)
66 Viewed
Print this page
Download PDF