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

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.This study has been partially supported by the Spanish Ministry of Science and Technology, DPI2008-02700, cofinanced by FEDER funds, and by Project PCI08-0048-8577, Consejeria de Ciencia y Tecnologia, Junta de Comunidades de Castilla-La Mancha, and Generalitat Valenciana ACOMP/2009/264.Alvarez-Valdes Olaguibel, R.; Crespo, E.; Manuel Tamarit, J.; Villa Juliá, MF. (2012). Minimizing weighted earliness-tardiness on a single machine with a common due date using quadratic models. TOP. 20(3):754-767. https://doi.org/10.1007/s11750-010-0163-7754767203Alidaee B, Kochenberger G, Ahmadian A (1994) 0–1 Quadratic programming approach for optimum solutions of two scheduling problems. Int J Syst Sci 25:401–408Baker KR, Scudder GD (1990) Sequencing with earliness and tardiness penalties: a review. Oper Res 38:22–36Billionnet A, Elloumi S (2007) Using a mixed integer quadratic programming solver for the unconstrained quadratic 0–1 problem. Math Program 109:55–68Billionnet A, Elloumi S, Plateau MC (2009) Improving the performance of standard solvers for quadratic 0–1 programs by a tight convex reformulation: the QCR method. Discrete Appl Math 157:1185–1197Biskup D, Feldman M (2001) Benchmarks for scheduling on a single machine against restrictive and unrestrictive common due dates. Comput Oper Res 28:787–801Cheng TCE, Kahlbacher HG (1991) A proof for the longest-job-first in one-machine scheduling. Nav Res Log 38:715–720De P, Gosh JB, Wells CE (1990) CON due-date determination and sequencing. Comput Oper Res 17:333–342Feldman M, Biskup D (2003) Single machine scheduling for minimizing earliness and tardiness penalties by meta-heuristic approaches. Comput Ind Eng 44:307–323Józefowska J (2007) Just-in-time scheduling. Springer, BerlinKanet JJ (1981) Minimizing the average deviation of job completion times about a common due date. Nav Res Log 28:643–651Kedad-Sidhoum S, Sourd F (2010) Fast neighborhood search for the single machine earliness–tardiness problem. Comput Oper Res 37:1464–1471Hall NG, Posner ME (1991) Earliness–tardiness scheduling problem, I: Weighted deviation of completion times about a common due date. Oper Res 39:836–846Hall NG, Kubiak W, Sethi SP (1991) Earliness–tardiness scheduling problem, II: Deviation of completion times about a restrictive common due date. Oper Res 39:847–856Hino CM, Ronconi DP, Mendes AB (2005) Minimizing earliness and tardiness penalties in a single-machine problem with a common due date. Eur J Oper Res 55:190–201Hoogeveen JA, van de Velde SL (1991) Scheduling around a small common due date. Eur J Oper Res 55:237–242Liao CJ, Cheng CC (2007) A variable neighbourhood search for minimizing single machine weighted earliness and tardiness with common due date. Comput Ind Eng 52:404–413Lin S-W, Chou S-Y, Ying K-C (2007) A sequential exchange approach for minimizing earliness–tardiness penalties of single-machine scheduling with a common due date. Eur J Oper Res 177:1294–1301Nearchou AC (2008) A differential evolution approach for the common due date early/tardy job scheduling problem. Comput Oper Res 35:1329–1343Oral M, Kettani O (1987) Equivalent formulations of nonlinear integer problems for efficient optimization. Manag Sci 36:115–119Panwalkar SS, Smith ML, Seidman A (1982) Common due date assignment to minimize total penalty for the one machine scheduling problem. Oper Res 30:391–399Plateau MC, Rios-Solis Y (2010) Optimal solutions for unrelated parallel machines scheduling problems using convex quadratic reformulations. Eur J Oper Res 201:729–736Skutella M (2001) Convex quadratic and semidefinite programming relaxations in scheduling. J ACM 48:206–242Sourd F (2009) New exact algorithms for on-machine earliness–tardiness scheduling. INFORMS J Comput 21:167–175Sourd F, Kedad-Sidhoum S (2003) The one machine problem with earliness and tardiness penalties. J Sched 6:533–549Sourd F, Kedad-Sidhoum S (2008) A faster branch-and-bound algorithm for the earliness–tardiness scheduling problem. J Sched 11:49–58Tanaka S, Fujikuma S, Araki M (2009) An exact algorithm for single-machine scheduling without machine idle time. J Sched 12:575–593Webster ST (1997) The complexity of scheduling job families about a common due date. Oper Res Lett 20:65–7