Single-pass and approximate dynamic-programming algorithms for order acceptance and capacity planning

This paper investigates dynamic order acceptance and capacity planning under limited reg-ular and non-regular resources. Our goal is to maximize the profits of the accepted projects within a finite planning horizon. The way in which the projects are planned affects their payout time and, as a consequence, the reinvestment revenues as well as the available ca-pacity for future arriving projects. In general, project proposals arise dynamically to the organization, and their actual characteristics are only revealed upon arrival. Dynamic so-lution approaches are therefore most likely to obtain good results. Although the problem can theoretically be solved to optimality as a stochastic dynamic program, real-life problem instances are too difficult to be solved exactly within a reasonable amount of time. Efficient and effective heuristics are thus required that supply a response without delay. For this reason, this paper considers both ‘single-pass ’ algorithms as well as approximate dynamic-programming algorithms and investigates their suitability to solve the problem. Simulation experiments compare the performance of our procedures to a first-come, first-served policy that is commonly used in practice