Research On The Algorithms For Early Work Maximization Scheduling Problem

This paper studies the scheduling problem of m(m?2)parallel machines with a common due date to maximize total(weighted)early work.This scheduling problem is considered NP-hard,that is,it is impossible to find an exact algorithm to solve the problem in polynomial time,unless P=NP.Parallel machines mean that multiple processors have a same speed in the system,and each job needs to be processed on any machine.The common due date means that all jobs have a same due date.In this paper,early work means the amount of work executed before the due date.For different models of this problem,different algorithms are proposed in this paper.For the non-weighted model,a fully polynomial time approximation scheme(FPTAS)is proposed,which is applicable not only to two parallel machines but also to any m parallel machines.Its approximation ratio is 1/1-?(? is a small error value)and its time complexity is O((1/?)mnm+1)(m is the number of parallel machines).This paper gives the proof process of FPTAS and implements experiments with polynomial time approximation scheme(PTAS)which was previous result.Compared with PTAS,the experimental results show that the running time of the proposed FPTAS is much better than the PTAS's and the accuracy of the FPTAS is higher for the same ?.For the weighted model,a dynamic programming with pseudo-polynomial time is proposed in this paper.Its time complexity is O(max{nlogn,ndm}).It indicates that problem Pm|dj=d|max(Xw)belongs to NP-hard in the weak sense,even if the weight is considered.Related experiments are carried out on the running time of the algorithm.The experimental results show that when the dynamic programming is sufficient in its memory space,the running time of the algorithm changes slowly with the increase of the number of j obs,and the problem instance with larger scale can be solved in an effective time.