k-optimal solution sets for some polynomially solvable scheduling problems

Abstract A k-optimal solution set Ω = {S 1 ,…,S k } of a given scheduling problem is a set of schedules such that no schedule S which is not contained in Ω is better than any S i , i = 1,…, k . k -optimal sets are useful in offering alternatives to a single optimal schedule. In this paper algorithms are presented which compute k -optimal sets for various scheduling problems for which the optimal schedule can be computed in polynomial time.