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.
Download Info
To download:
If you experience problems downloading a file, check if you have the
proper application to
view it first. Information about this may be contained
in the File-Format links below. In case of further problems read
the IDEAS help
page. Note that these files are not on the IDEAS
site. Please be patient as the files may be large.
Publisher Info
Paper provided by Indian Institute of Management Ahmedabad, Research and Publication Department in its series IIMA Working Papers with number
2003-07-03.
References listed on IDEAS Please report citation or reference errors to , or , if you are the registered author of the cited work, log in to your RePEc Author Service profile, click on "citations" and make appropriate adjustments.: