Single-Machine Scheduling with Upper Bounded Maintenance Time under the Deteriorating Effect

We consider a single-machine scheduling problem with upper bounded actualprocessing time and upper bounded maintenance time under deteriorating effect. The actualprocessing time of a job is a position-dependent power function. If the actual processing timeof a job exceeds the upper bound, tardiness penalty of the job should be paid. And if themaintenance time exceeds the corresponding upper bound, tardiness penalty of the maintenanceshould also be paid. The maintenance duration studied in the paper is a position-dependentexponential function. The objective is to find jointly the optimal maintenance frequency andthe optimal job sequence to minimize the total cost, which is a linear function of the makespanand the total tardiness. We show that the studied scheduling problem can be transformed as aclassic assignment problem to solve. There is also shown that a special case of the schedulingproblem can be optimally solved by a lower order algorithm