The Unrelated Parallel Machine Scheduling Problem With Constraints

In this thesis,we consider the unrelated parallel machine scheduling problem with constraints(the UPMS-C problem,for short),which is defined as follows.Given a set X={x1,x2,...,xn}of n jobs and a set Y={y1,y2,...,ym}of m machines,each job xi(∈X)has a processing time w(xi,yj)when this job is executed on the machine y j(∈X),the processing time of each job may permit to be different when this job is executed on different machines,where one job can be assigned to be processed on one machine.When one job is executed on a machine,it can not be interrupted.Moreover,we may have the number of jobs executed on one machine y j at least l(y j)and at most b(y j).When one job xi is not executed on any machine,the penalty cost p(xi)will be incurred.It is asked to find a scheme M to assign these n jobs to satisfy the constraints mentioned-above,the objective is to minimize the sum of total completion times of jobs executed plus total penalty costs of jobs not executed.In order to solve the UPMS-C problem,we construct a network with lower and upper bound capacity constraints and transfer this problem to a network flow problem,we then design a Two-stage successive shortest path algorithm in time O(n~4m~2log(nm))to optimally solve the UPMS-C problem,we finally present an example and implement the Two-stage Successive Shortest Path algorithm by programming.