Single-machine scheduling with piece-rate maintenance and interval constrained position-dependent processing times

摘要

This paper investigates single-machine scheduling problems with piece-rate machine maintenance and interval constrained actual processing time. The actual processing time of a job is a general function of the normal job processing time and the position in job sequence, and it is required to restrict in given interval otherwise earliness or tardiness penalty should be paid. The maintenance duration studied in the paper is a time-dependent linear function. The objective is to find jointly the optimal frequency to perform maintenances and the optimal job sequence to minimize the total cost, which is a linear function of the makespan, total earliness and total tardiness. There is shown that the problem can be optimally solved in O(n4) time. There is also shown that two special cases of the problem can be optimally solved by lower order algorithms.