Optimal Scheduling Of Lateness Under The Cost Limitation Of Uniform Parallel Machine

This paper considers a scheduling problem of processing jobs on uniform parallel machines.The objective is to minimize the maximum lateness,subject to the constraint that the total cost cannot exceed a given threshold.Machine scheduling problem has always been a hot research topic in the field of manufacturing.In particular,as a popular type of machine in daily life,uniform machines scheduling problems need more attention.The maximum lateness refers to the difference between the customer's waiting time and a order's due date,and is an important manifestation of customer satisfaction.Therefore,the research problems in this paper have important theoretical and practical significance.In this paper,we first study the case that the machine has a fixed use cost,and the goal is to minimize the maximum lateness under the cost constraint.For the case of non-preemptive jobs,a mixed integer programming model is constructed.We first design a heuristic to choose machines for processing jobs,and then we develop an algorithm A₁ to solve this problem,which is based on the traditional LPT（Longest Processing Time First）,ECT（Earliest Completion Time First）,EDD（Earliest Due Date First）algorithm.The worst error bounds of the problem are given,respectively in the parallel machine and uniform parallel machine environments.By given an example,We proved the feasibility of the algorithm.And a large number of random data experiments are carried out to verify the effectiveness of the algorithm.For the preemptive problem,we also develop an algorithm A₂,and an example is given for verification.Based on the previous part,we further expanded the assumption of machine cost.Suppose that the cost of using a machine is related to the processing time,we investigate the problem of minimizing the maximum lateness.For the non-preemptive problem,we establish a mixed integer programming model and design the algorithm A₃ for scheduling jobs on uniform machines.The performance of the proposed algorithm is tested through random data and evaluated against optimal solutions obtained by Lingo.The results indicate that the algorithm is efficient and performs well.For the preemptive problem,we design the heuristic algorithm A₄ and illustrate the execution of the algorithm through an example.