Single Machine Scheduling with Deadlines to Minimize Maximum Earliness

This paper discusses the problem that n jobs with their own deadlines have to be processed on a single machine considering the idle insert.The objective is to find a job sequence and determine jobs' starting times so as to minimize the maximum earliness.Since tardy jobs are prohibited,it's possible that there is no feasible sequence for the problem.We consider the feasibility primarily.If the problem is feasible,we first pre-determine a sequence and develop an algorithm to compute jobs' starting times,and then judge whether it's optimal or not.If optimality can't be determined directly,a polynomial time algorithm is developed to achieve optimality through attempting to adjust the jobs constantly from the pre-determined sequence initially.