Single Machine Scheduling With Increasing Linear Maintenance Durations

Scheduling in people’s production and life has a wide range of applications.For example,in disaster rescue,dispatch of relief supplies and personnel scheduling;In the transportation sector,Buses,trains arrangements,courier to send goods;In the manufacturing sector,arrangement of plant machinery,job machining sequence;In the service sector,such as timetable arrangements for school teachers,etc.These are scheduling problems encountered in daily life.These examples illustrate the production and life,scheduling problems everywhere.This is why a growing number of researchers involved in research in scheduling theory.Scheduling is a class of combinatorial optimization problems.It is the study of how to allocate scarce resources to the task of making the best within a certain time to complete the task.Many of the literature is based on the factory floor processing machines arrangements for research models.This paper studies a single machine scheduling problem with periodic maintenance activities.In this problem,there is only one machine with periodic maintenance,The length of the time interval between any two consecutive maintenance activities remain unchanged,The amount of time needed to perform one maintenance activity is an increasing linear function of the total processing time of the jobs that are processed after its latest previous maintenance activity.All information of jobs is known,the job can not be interrupted.The objective is to schedule all the jobs to the machine such that the makespan,that is,the completion time of the last finished job,is minimized.The main work of this paper is as follows:1. The worst-case of FFD-LS2 I algorithm has been proved.First, this paper gives an example showing that the worst-case bound of the FFD-LS algorithm can be arbitrarily large.Then makes a detailed analysis on the FFD-LS algorithm worst-case and improves FFD-LS algorithm algorithm obtained FFD-LS2 I and proved the worst-case of FFD-LS2 I algorithm.2. nonapproximability has been proved.After proved the worst-case of FFD-LS2 I algorithm,The authors speculate that the FFD-LS2 I algorithm is the best possible polynomial time approximation algorithm,then proved there is no polynomial time approximation algorithm with a worst-case bound less than 2 for the scheduling problem.And then showed that the FFD-LS2 I algorithm and the FFD-LS algorithm is the best possible algorithm for the respective situations,then given an answer to an open question in one of literature.3. The numerical experiments of this paper verify the FFD-LS2 I algorithm worst-case,and find relationship between the FFD-LS2 I algorithm maximum error, the average error and the number of jobs, the variable, ect.