Multi-period job selection: Planning work loads to maximize profit

We examine the profitability of job selection decisions over a number of periods when current orders exceed capacity with the objective of maximizing profit (per-job revenue net of processing costs, minus weighted lateness costs), and when rejecting a job will result in no future jobs from that customer. First we present an optimal dynamic programming algorithm, taking advantage of the structure of the problem to reduce the computational burden. Next we develop a number of myopic heuristics and run computational tests using the DP as benchmark for small problems and the best heuristic as benchmark for larger problems. We find one heuristic that produces near-optimal results for small problems, is tractable for larger problems, and requires the same information as the dynamic program (current and future orders), and another that produces good results using historical information. Our results have implications for when it is more or less worthwhile to expend resources to maintain past records and obtain future information about orders. The purpose of this paper is to investigate trade-offs between accepting or rejecting job orders, completing processing on time and guaranteeing timelines with money-back guarantees, when job selection decisions will affect future orders. These issues are important to firms that must balance short- and long-term profitability and maintain their customer base in competitive markets. We present a multi-period model that can be solved optimally with a dynamic program, and develop several heuristics which we evaluate with computational studies. We find that our heuristics that use either historical information or future estimates of sales produce good results relatively large problems without the computational limitation of the optimal procedure. Our studies provide insights into when it is worthwhile for a firm to keep (and process) historical sales information, and seek accurate estimates of future orders.