본문 바로가기
  • Home

A Dynamic Programming Approach for Emergency Vehicle Dispatching Problems

  • Journal of The Korea Society of Computer and Information
  • Abbr : JKSCI
  • 2016, 21(9), pp.91-100
  • Publisher : The Korean Society Of Computer And Information
  • Research Area : Engineering > Computer Science

Jae Young Choi 1 Kim, Heung-Kyu 2

1아주대학교
2단국대학교

Accredited

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.

Citation status

* References for papers published after 2022 are currently being built.