Formulações matemáticas para o problema de sequenciamento de lotes com penalidades por atraso

Abstract

The problem of scheduling on a single machine, proven to be NP-hard, consists of de ning the job grouping in batches and of the sequence in which these batches will be processed on a machine. Each job is associated with a release date, a processing time, a due date, a priority level in relation to the others and a size. The machine is able to process a group of jobs (batch) simultaneously, provided that the sum of the job sizes belonging to the referred batch does not exceed the machine capacity. Each job must be processed only once and only one batch is processed at a time on the machine. In this work, we consider the objective as the minimization of total weighted tardiness, where the tardiness of a job is the di erence between its completion time and its due date, in case the job processing is nished after its due date and hence is late, or equals zero, otherwise. In the literature, this problem is usually referred to as 1jbatch; rj ; sj ; comptjPwjTj . When all jobs are available to be processed at time zero, the problem is usually represented as 1jbatch; sj ; comptjPwjTj . These problems are still poorly explored in the literature and in addition, cover a large number of variant forms. There are few studies involving the application of exact methods for solving both. Only one mathematical formulation was identi ed in the literature for these problems. Hence, four time-indexed formulations were developed to solve the aforementioned problems, one of which is capable of dealing with both problems. The results achieved by the developed models were compared between themselves and with the results of the model available in the literature. These computational results reveal that two of the proposed models obtained higher performance both in terms of quality of the solution, particularly regarding the achieved lower bounds, and in numbers of open nodes and of proven optimal solutions.