ANALYSIS OF MIXED INTEGER PROGRAMMING FORMULATIONS FOR SINGLE MACHINE SCHEDULING PROBLEMS WITH SEQUENCE DEPENDENT SETUP TIMES AND RELEASE DATES

AUTOR(ES)

Nogueira, Thiago Henrique

FONTE

Pesqui. Oper.

DATA DE PUBLICAÇÃO

09/05/2019

RESUMO

ABSTRACT The scheduling of jobs over a single machine with sequence dependent setups is a classical problem setting that appears in many practical applications in production planning and logistics. In this work, we analyze six mixed-integer formulation paradigms for this classical context considering release dates and two objective functions: the total weighted completion time and the total weighted tardiness. For each paradigm, we present and discuss a MIP formulation, introducing in some cases new constraints to improve performance. A dominance hierarchy in terms of strength of their linear relaxations bounds is developed. We report extensive computational experiments on a variety of instances to capture several aspects of practical situations, allowing a comparison regarding size, linear relaxation and overall performance. Based on the results, discussions and recommendations are made for the considered problems.

Documentos Relacionados

• Evolutionary Algorithms for Parallel Machine Scheduling Problems with Sequence Dependent Setup Times
• A mixed integer programming approach for freight railcar distribution
• Heuristic for flow shop sequencing with separated and sequence independent setup times
• GRAPH PROPERTIES OF MINIMIZATION OF OPEN STACKS PROBLEMS AND A NEW INTEGER PROGRAMMING MODEL
• Proposta de um modelo em programação linear para a solução de problemas de sistemas produtivos job shop com setup dependentes da sequência