Heuristic approach to task scheduling: ‘Weight’ and ‘improve’ algorithms

This work deals with the development of a heuristic algorithm to schedule a group of tasks to a predetermined number of resources. The tasks are characterized by fixed starting times and known durations. A task cannot be performed simultaneously on more than one resource, each resource having a capacity of one task at a time. Such a problem can be represented by a ‘quasi’ graph coloring formulation, having to color the graph nodes (tasks) with insufficient number of colors (resources). Many production-oriented problems have these properties, and these are some of the examples: (1) delivery fleet scheduling, (2) maintenance crew and machine scheduling, (3) personnel scheduling. A two-stage heuristic method is defined and its reasoning illustrated, based on economic principles. The efficiency of a solution by the ‘weight’ and ‘improve’ method is tested by comparing it to other known heuristic methods. The algorithm proposed is found to be far superior to other algorithms when tested with a large-scale problem set. The results of this work indicate the possibility of the algorithms’ easy implementation and incorporation into concurrent resource scheduling softwares. The algorithms have been implemented on a microcomputer and were used to solve transportation-resource problems.