A SINGLE-MACHINE DETERIORATING JOB SCHEDULING PROBLEM WITH A NON-REGULAR CRITERION

In scheduling environments with deterioration, a job processed later consumes more time than that same job when processed earlier. The deteriorating job scheduling problems have been widely studied in the last two decades. However, no result of the completion time variance has been reported. In this study, we consider the variance of job completion time minimization problem on a single machine. It is assumed that the job processing time is a simple linear function of its starting time. We show that an optimal schedule is V-shaped with respect to the job deteriorating rates. A heuristic algorithm utilized the V-shaped property is then proposed, and a computational experiment shows that the proposed heuristic algorithm is quite accurate.