Approximate policy iteration for dynamic resource-constrained project scheduling

Salemi Parizi M., Gocgun Y., Ghate A.

Operations Research Letters, vol.45, no.5, pp.442-447, 2017 (SCI-Expanded) identifier identifier

  • Publication Type: Article / Article
  • Volume: 45 Issue: 5
  • Publication Date: 2017
  • Doi Number: 10.1016/j.orl.2017.06.002
  • Journal Name: Operations Research Letters
  • Journal Indexes: Science Citation Index Expanded (SCI-EXPANDED), Scopus
  • Page Numbers: pp.442-447
  • Keywords: Markov decision processes, Approximate dynamic programming, Queueing
  • Istanbul Medipol University Affiliated: No

Abstract

We study non-preemptive scheduling problems where heterogeneous projects stochastically arrive over time. The projects include precedence-constrained tasks that require multiple resources. Incomplete projects are held in queues. When a queue is full, an arriving project must be rejected. The goal is to choose which tasks to start in each time-slot to maximize the infinite-horizon discounted expected profit. We provide a weakly coupled Markov decision process (MDP) formulation and apply a simulation-based approximate policy iteration method. Extensive numerical results are presented.