Scheduling deteriorating jobs on a single machine to minimize the maximum processing times

Abstract

In many real-world scheduling problems the processing time of a job is a variable and depends on a function of its starting time. The origin of the mathematical modelling of these types of sequencing problems is new and most studies have concentrated on minimizing the makespan, and minimizing the total completion times. This paper addresses the problem of sequencing a set of n independent jobs on a single machine when the processing time of a job is a linear function of its starting time, with the objective of minimizing the maximum processing times. A heuristic algorithm for the problem is presented. The effectiveness of the algorithm is computationally tested. The algorithm can optimally solve the problem for some important special cases.