A desired load distribution model for scheduling of unrelated parallel machines

Scheduling problems concern the allocation of limited resources over time among both parallel and sequential activities. Load balancing has been adopted as an optimization criterion for several scheduling problems. However, in many practical situations, a load-balanced solution may not be feasible or attainable. To deal with this limitation, this paper presents a generic mathematical model of load distribution for resource allocation, called desired load distribution (DLD). The objective is to develop a DLD model for scheduling of unrelated parallel machines that can be used both in centralized resource management settings and in agent-based distributed scheduling systems. The paper describes the proposed DLD model in details, presents a dynamic programming based optimization algorithm for the proposed model, and then discusses its application to agent-based distributed scheduling.