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

Dhavale N P, Sanjay Verma and Bagchi Amitava

No WP2003-07-03, IIMA Working Papers from Indian Institute of Management Ahmedabad, Research and Publication Department

Abstract: 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.

Date: 2003-07-03
References: Add references at CitEc
Citations: View citations in EconPapers (2)

There are no downloads for this item, see the EconPapers FAQ for hints about obtaining it.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:iim:iimawp:wp01765

Access Statistics for this paper

More papers in IIMA Working Papers from Indian Institute of Management Ahmedabad, Research and Publication Department Contact information at EDIRC.
Bibliographic data for series maintained by ().