Scheduling Agreeable Jobs On A Single Machine To Minimize Weighted Number Of Early And Tardy Jobs

Abstract

The problem of non-preemptive (NP) scheduling of number of jobs on a single machine to minimize weighted number of early and tardy jobs where the earliest start times and latest due date are agreeable (i.e. earliest start time must increase in the same sequence as latest due dates) has been considered. The problem has been shown to be NP complete in the strong sense and finding an optimal solution appeared unlikely. Two greedy heuristic solutions were obtained, and extensive computational trials indicated that the heuristics performed better than other existing solutions.

Journal of Applied Science and Technology Vol. 12 (1&2) 2007: pp. 12-17