A Problem in Bulk Service Scheduling
George L. Nemhauser, P. L. Yu · Operations Research · 1972
Given the operating costs, usage function, and planning horizon of a bulk service system, say a common-carrier transportation system, the objective is to determine the number and the starting times of the services so that the total profit is maximized. For such problems, this paper studies the existence and computability of optimal schedules. It shows that an ϵ-optimal schedule can be found by a discrete optimization on a sufficiently fine grid. It then makes more specific assumptions regarding the dependence of usage on the schedule and presents a dynamic-programming algorithm for the discrete optimization. Finally, an analytic solution is given for a simple case.