Relaxação lagrangeana com fixação de variáveis aplicada ao problema de sequenciamento em uma máquina

Abstract

This paper deals with the Single-machine Scheduling Problem. This kind of problem arises in several practical situations, such as the problems of planning operations on machines in a manufacturing industry. The Single-machine Scheduling Problem consists in sorting n jobs to be processed on a single machine. The jobs are independent and the machine can only execute one job at a time. A special case ofthis kind of problem arises when each job is associated with their weight and their release date, where the goal is to minimize weighted cost of time at the beginning of processing the jobs. This problem is a Combinatorial Optimization, and as many of these kinds of problems, it is difficult to be solved. The Integer Linear Programming model studied here to represent the problem, presents time-indexed variables.The time-indexed formulation can be used to represent different types of Scheduling Problems. The relaxation of modelled problems with this feature can generate good limits for the value of the solution of the original problem. However, this formulation shows an important disadvantage, the dimension of the obtained model. RepresentativeModels of small instances have a large number of constraints and variables. Aimed at generating good limits on the value of the solution of the studied problem, it was used a Lagrangean Relaxation, where the Dual Lagrangean Problem adopted is maximized through the Subgradient method. To reduce the number of the necessary variables for the definition of the problem, there is a procedure used for fixingvariables based on the reduced costs of a feasible Lagrangeana solution. Finally, the Integer Programming Problem with the fixed variables by the methodology described above can be solved by a optimization software.