Maximum Profit Scheduling

The classical scheduling literature considers many problems where a given set of jobs must be processed at minimum cost, subject to various resource constraints. The literature only considers the issue of revenue generation in a very limited way, by allowing a job to remain unprocessed and its revenue contribution to be lost. By contrast, we consider three diverse practical situations where efficient scheduling affects revenue in much more general and realistic ways. First, we study two make-to-order environments where efficient scheduling increases customer goodwill, thus stimulating demand in different ways. Second, we study two make-to-stock environments where efficient scheduling creates inventory, thus also stimulating demand in different ways. Third, we study new product markets where efficient scheduling leads to a company becoming the first mover, and thus acquiring a larger market share. In each case, we provide both a computationally efficient algorithm for scheduling and a proof that a much more efficient algorithm is unlikely to exist. For both the make-to-stock and make-to-order problems, we also describe heuristic approaches that are easy to implement, and we study their average performance. The results show that substantial benefits arise from considering the implications of efficient scheduling for revenue and net profit. The practical impact of our work is to demonstrate the importance of efficient scheduling, not only in controlling cost, but also in increasing revenue and net profit.