Minimizing weighted earliness–tardiness on a single machine with a common due date using quadratic models

Ramon Alvarez-Valdes ^[1] ; Enric Crespo ^[1] ; Jose Manuel Tamarit ^[1] ; Fulgencia Villa ^[2]
1. [1] Universitat de València
  
  Universitat de València
  
  Valencia, España
2. [2] Universidad Politécnica de Valencia
  
  Universidad Politécnica de Valencia
  
  Valencia, España
Localización: Top, ISSN-e 1863-8279, ISSN 1134-5764, Vol. 20, Nº. 3, 2012, págs. 754-767
Idioma: inglés
Enlaces
- Texto completo (pdf)
Resumen
- In this paper we study the problem of minimizing weighted earliness and tardiness on a single machine when all the jobs share the same due date. We propose two quadratic integer programming models for solving both cases of unrestricted and restricted due dates, an auxiliary model based on unconstrained quadratic integer programming and an algorithmic scheme for solving each instance, according to its size and characteristics, in the most efficient way. The scheme is tested on a set of well-known test problems. By combining the solutions of the three models we prove the optimality of the solutions obtained for most of the problems. For large instances, although optimality cannot be proved, we actually obtain optimal solutions for all the tested instances.