Scheduling Partially Ordered Jobs Under Resource Constraints To Optimize Non-Regular Performance Measures

We describe a general best-first tree search scheme that schedules a set of partially ordered jobs under resource constraints to optimize a non-regular performance measure. The scheme has been implemented for two categories of problems. In the first category, jobs have individual duedates, and the objective is to minimize the total weighted earliness-tardiness penalty. Algorithms currently available for solving problems of this type lack the full generality of the scheme proposed here. In the second category, jobs have associated cash flows, and the objective is to maximize the Net Present Value (NPV). Our methods have been implemented in C both on a Linux-based Pentium PC and on a UNIX-based DEC ALPHA workstation, and successfully tested on problem instances derived from benchmark sets such as the PROGEN set and the Patterson set. For the NPV problem, it has been compared experimentally with the existing method of Icmeli and Erenguc. A theoretical proof of optimality is also provided.