DEVELOPMENT OF A NEW INTEGER PROGRAMMING MODEL AND A LOWER BOUND FOR IDENTICAL PARALLEL MACHINES PROBLEM WITH TOTAL TARDINESS CRITERION MINIMIZATION

Determining eective scheduling in operations sequence is among the important problems of production scheduling. This paper deals with the problem of minimizing total tardiness on a parallel machine with N jobs and m machines. In the literature, there is a lack of suitable mathematical programming of the problem. Hence, this paper presents a mixed integer mathematical model for the problem. Since the problem has been proved as an NP-hard problem, it would be valuable to give a lower bound (LB) with a reasonable computational time. Denoting the processing time of a typical job on the machine, the modied processing time would be .With this modied processing time, the problem can be seen as a single machine; namely, the original processing time is divided by the number of machines and the division is considered as the modied processing time for computations. The problem is reformulated as an assignment problem in which the positions of jobs in the sequence are the locations of the assignment problem. The model presents the lower bound of the problem. To compare thequality(runningtime)oftheintroducedLB,wegeneratedsomerandominstancesoftheproblemfromsmall to large sizes. The optimal solution of the small size instances is obtained through solving the developed mathematical model. To obtain the solution of the medium and large sized instances, a new simulated annealing algorithm is developed. In this algorithm, the crossover operator and mutation have been used to create a neighborhood of simulated annealing algorithm; but for the rst time the crossover operator is used to create neighborhood directly. The results gained from the lower bound are compared with those of lower bound available in the literature. They conrm that the lower bound introduced in this paper gives high quality solutions, and hence, it has superiority to the available LB in the literature.