Abstract
This paper considers single machine scheduling with an aging effect in which the processing time of a job depends on its position in a sequence. It is assumed that aging ratios are job-dependent and machine can be maintained some times in a schedule. After a maintenance activity, machine will be restored to its initial condition. The processing of jobs and the maintenance activities of machine are scheduled simultaneously. The objective is to schedule the jobs and the maintenance activities, so as to minimize the makespan. We provide a polynomial time algorithm to solve the problem.
1. Introduction
In the classical scheduling problems it is assumed that the processing times of jobs are constant. However, there are many situations where the processing times of the job may be dependent on their positions in the sequence [1]. This phenomenon is called learning effect or aging effect. In a learning environment, the later a given job is scheduled in the sequence, the shorter its processing time; while in an aging environment, the later a given job is scheduled in the sequence, the longer its processing time.
