Premium
Scheduling independent jobs on nonuniform, unequal processors
Author(s) -
Bernardo John J.,
Lin KunSi
Publication year - 1984
Publication title -
journal of operations management
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 3.649
H-Index - 191
eISSN - 1873-1317
pISSN - 0272-6963
DOI - 10.1016/0272-6963(84)90018-4
Subject(s) - tardiness , computer science , scheduling (production processes) , mathematical optimization , job shop scheduling , time complexity , retard , heuristic , algorithm , parallel computing , mathematics , schedule , artificial intelligence , psychology , psychiatry , operating system
The problem of scheduling n independent jobs on a single processor to minimize the total tardiness of the assignment has attracted much attention. Solution algorithms, both exact and approximate, have been reported, but no polynomial time exact algorithm has yet been found, nor has the problem been proven NP‐complete. In this paper we consider the more general case of scheduling n independent jobs on m unequal processors to minimize total tardiness. Since this problem is more complex than the corresponding single‐processor problem, no polynomial‐time algorithm is in sight. For problems of this nature, approximate algorithms may be more valuable than exact algorithms in terms of applications. A heuristic algorithm is developed to solve the multiple‐processor problem. Computational experiments show that the heuristic algorithm is efficient, fast, and easy to implement.