Research On Identical Machine Scheduling Problems With Preventive Periodical Maintenance

One important characteristic of traditional scheduling research is that machines canalways be used to process jobs. However, in real production scheduling, in order to avoidproduct quality decrease and machine shutdown due to excessive tool wear, one commonlyused method is to conduct preventive maintenance regularly. This thesis mainly studiestwo identical machine scheduling problem with machine maintenance considerations.The first problem is an identical machine scheduling problem with each machine isrequired to be maintained periodically, where all the jobs are available at time zero andthey are non-preemptive, all the jobs are the same except their processing times andnumbers. The objective is to find a schedule so that the sum of the job completion times isminimized. This thesis proposed an algorithm named MSPT based on the classic SPTalgorithm. The idea of the MSPT algorithm is to modify the SPT scheduling by adjustingthe jobs within each machine. Theoretical analysis shows that MSPT algorithm is betterthan the SPT algorithm.Note that the two machines case is the most basic case in parallel machine scheduling,this thesis present specific discussions on the two machine case of the scheduling problemjust mentioned. For moderate sized and small sized jobs, this thesis establishes amathematical programming model. For large sized jobs, this thesis proposes an algorithmnamed MSPTI. The idea of this algorithm is to modify the SPT scheduling byinterchanging jobs within one machine or interchanging jobs between the two machines sothat the idle time of the two machines is as short as possible. Numerical experiment showsthat the bigger maintenance time is, the better the performance of the MSPTI algorithm.The second problem is an two-identical-machine periodically e scheduling problemwith job families and each machine is required to be maintained, where there are twofamilies of jobs, namely special jobs and normal jobs. Each special job can only beprocessed within a certain interval just after some maintenance on the second machine. Allthe jobs are non-preemptive. The objective is to find a schedule so that the makespan isminimized. This thesis proposes an algorithm named MLPT. Numerical experiment showsthat the average error of the MLPT algorithm is less than10%.