Model And Optimization Algorithm For Scheduling Problem With Due Date And Machine Availability Constraints

In this paper,the deterministic machine scheduling problems with due date and machine availability constraints are studied based on manufacturing supply chain,which mean these scheduling problems own known due date and machine availability constraints.When suppliers deliver material too early,it puts pressure on inventories for manufacturer.If suppliers deliver material too late,manufacturer's production schedule will be delayed.In addition,manufacturing shop need to regularly carry out preventive maintenance of machines to ensure the normal operation of production.Therefore,based on delivery time and machine availability constraints,this paper discusses that how manufacturers should decide the sequence of production to maximize production profit.We transform the scheduling problem into a mathematical model to study two optimization objectives.First,calculating to minimize the sum of early and tardy time,the goal is to make manufacturers as punctual as possible on production.Secondly,the sum of the maximum early work is calculated,which can make the manufacturer obtain as much economic profit as possible.Firstly,this paper introduces the theoretical and practical significance of supply chain scheduling.In addition,this paper introduces the status quo and existing achievements of domestic and foreign scholars on the topic,and also expounds the scheduling theory and methods related to this paper in detail.Secondly,this paper presents three scheduling problems based on the constraints of delivery and machine availability.Firstly,the single machine scheduling problem with of minimal the sum of early and tardy time is studied.Secondly,the single machine scheduling problem for maximizing early work is studied.Finally,the parallel machine scheduling problem for maximizing early work is studied.All the above problems are proved to be NP hard problems,and dynamic programming algorithms are proposed in this paper respectively.For parallel machine problems,a full polynomial approximation scheme(FPTAS)is developed based on dynamic programming,and an approximation algorithm with worst-case bound of 2is also proposed.Finally,experiment analysis is given to verify the performance of dynamic programming algorithms in terms of running time.Meanwhile,the performance of the approximation algorithm is verified by the deviation between the optimal solution and the approximation solution.