Single Machine Scheduling with Tardiness Involved Objectives : A Survey

Abstract: This thesis contributes to theoretical and quantitative aspects of machine scheduling. In fact, it is dedicated to the issue of scheduling n jobs on one single machine. The scope is limited to deterministic problems - i.e. those with all data available and known with certainty in advance - with tardiness involved objectives; hence, the common denominator of all problems addressed are jobs with a predetermined due date assigned to. A job is finished on time as long as it is completed before its due date, otherwise it is said to be tardy. Since the single machine utilized is assumed to be restricted to process at most one job at a time, the aim is to find a proper sequence - a schedule - of how to process the jobs in order to best fulfill a certain objective. The contribution of this thesis aims at giving a state of the art survey and detailed review of research effort considering the objectives "minimizing the number of tardy jobs" and "minimizing the weighted number of tardy jobs". Further, the objectives of "minimizing the total tardiness", "minimizing the total weighted tardiness" and "minimizing the maximum tardiness" are adumbrated but reduced to a rough overview of research effort made.