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

AUTOR(ES)
DATA DE PUBLICAÇÃO

2008

RESUMO

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 of this 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. Representative Models 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 fixing variables 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.

ASSUNTO(S)

engenharia de produção teses. logística empresarial teses.

ACESSO AO ARTIGO

Documentos Relacionados