Parallel Machine Scheduling With Learning Effect And Deteriorating Jobs In A JIT System

This paper considers some problems of common due date assignment and parallel machine scheduling with learning effect and deteriorating jobs in a JIT production environment,and studies the problem of minimizing the weighted sum of earliness,tardiness and due date and the problem of minimizing the sum of earliness cost,due date cost and the weighted number of tardy jobs respectively.and the objective is to determine the optimal due date and the optimal schedule simultaneously to minimize the objective function f(d,?).Based on the existing conclusions in the literatures,we first make a theoretical analys,is of the algorithm complexity for problems,and then we search for polynomial time optimal algorith-m for special cases.Firstly,for the problem Pm|pj =(pj0+bsj)rn|?(?Ej+?Tj)and the problem Pm|pj=pm0raj+bsj|?(?Ej+?Tj),we can give a optimal solu-tion in O(nm log n)and O(nm+2)respectively.Then,for the problem of minimizing the weighted sum of earliness and the number of tardy jobs ?(?Ej +ejUj),we study the two processing time models in the above problem respectively and prove that both their optimal solutions can be given in O(nm-3)time by transforming these problems to assignment problems.Lastly,we propose a FPTAS for the problem of parallel machine scheduling with deteriorating jobs and the limit of grade of service Pm|pj =pj0 +bjlj,GOS|?cjUj+ ?d,and its time complexity is O(n2m-2Lm+2/em+1).Some extensions of the problems are also given respectively.