Exact Algorithms For Scheduling On Unrelated Machines With Late Work Minimization

Scheduling problems,which have been studied for decades,are one of the most classical problems in combinatorial optimization and operational research.Within the history of scheduling theory,lots of models motivated by real production environments and practical applications have been proposed,and a large number of scholars have been attracted to these models.This thesis mainly focus on the scheduling problem on unrelated machines with late work criterion,in which each job has its own due date,and each machine has a different processing speed for the same job.In addition,preemption is not allowed during the execution.The research target in this thesis is to minimize the late work penalty,rather than a classical makespan.For the general model Rm|d=d_j|Y with arbitrary due dates,a mixed integer programming model is proposed in this thesis and solved by Gurobi.Moreover,to solve the problem,a branch-and-bound algorithm and a PDP algorithm both equipped with the truncation rule,upper and lower bounds techniques are proposed.DPRm algorithm works as a new lower bound in B&B algorithm.DPRm algorithm extends the predecessors'dynamic programming algorithm for solving the simplified model Rm|d=d'|Y with a common due date of all jobs,which only expands the applicability of dynamic programming algorithm,but also proves that Rm|d=d'|Y is a binary NP-complete problem.In this thesis,different experimental scenes are designed to compare the performance of the algorithms.The experimental instances are mainly divided into small-scale instances and large-scale instances.In small-scale instance experiment,PDP algorithm,B&B algorithm and the mixed integer programming model solved by Gurobi are used to solve the problem Rm|d=d_j|Y.The mixed integer programming model is proved to be correct and effective by comparing the three methods.According to the experimental results,it is verified that the PDP algorithm and the B&B algorithm are both quicker than the mixed integer programming model solved by Gurobi.In big-scale instance experiment,the performance of PDP algorithm,B&B algorithm and TS algorithm are compared and analyzed.Although TS algorithm is quite quick,the average value of the ratio between the solution of TS and the optimal solution is114.53%based on the experimental results.Although PDP algorithm and B&B algorithm are both exact algorithms,when the number of jobs and machines is small,the speed of PDP algorithm is better than that of B&B algorithm.When the number of jobs and machines increases,the B&B algorithm shows more excellent performance than the PDP algorithm.