Solving Single Machine Total Weighted Tardiness Problem Using Gaussian Process Regression

Authors: Wanatchapong Kongkaew

Abstract:

This paper proposes an application of probabilistic technique, namely Gaussian process regression, for estimating an optimal sequence of the single machine with total weighted tardiness (SMTWT) scheduling problem. In this work, the Gaussian process regression (GPR) model is utilized to predict an optimal sequence of the SMTWT problem, and its solution is improved by using an iterated local search based on simulated annealing scheme, called GPRISA algorithm. The results show that the proposed GPRISA method achieves a very good performance and a reasonable trade-off between solution quality and time consumption. Moreover, in the comparison of deviation from the best-known solution, the proposed mechanism noticeably outperforms the recently existing approaches.

 

Keywords: Gaussian process regression, iterated local search, simulated annealing, single machine total weighted tardiness.

Digital Object Identifier (DOI): doi.org/10.5281/zenodo.1093275

References:

[1] J.K. Lenstra, A.H.G. RinnooyKan, and P. Brucker,"Complexity of machine scheduling problems,”inAnnals of Discrete Mathematics, P. L. Hammer, E. L. Johnson, B. H. Korte, and G. L. Nemhauser, Eds. Amsterdam: Elsevier, 1977, pp. 343–362.
[2] R. Maheswaran and S. G. Ponnambalam, "An investigation on single machine total weighted tardiness scheduling problems,” Int. J. Adv. Manuf. Tech., vol. 22, pp. 243–248, September 2003.
[3] A. Jouglet, P. Baptiste, and J. Carlier, "Exact procedures for single machine total cost scheduling,” in Proc. 2002 IEEE Int. Conf. Systems, Man and Cybernetics, Tunisia, 2002, 4 p.
[4] P. Babu, L. Peridy, and E. Pinson, "A branch and bound algorithm to minimize total weighted tardiness on a single processor,” Ann. Oper. Res., vol. 129, pp. 33–46, July 2004.
[5] M. Wodecki, "A branch-and-bound parallel algorithm for single-machine total weighted tardiness problem,” Int. J. Adv. Manuf. Tech., vol. 37, pp. 996–1004, June 2008.
[6] H. A. J. Crauwels, C. N. Potts, and L. N. Van Wassenhove, "Local search heuristics for single machine total weighted tardiness scheduling problem,” Informs J. Comput., vol. 10, pp. 341–350, Summer 1998.
[7] T. C. E. Cheng, C. T. Ng, J. J. Yuan, and Z. H. Liu, "Single machine scheduling to minimize total weighted tardiness,” Eur. J. Oper. Res., vol. 165, pp. 423–443, September 2005.
[8] W. Bożejko, J. Grabowski, and M. Wodecki, "Block approach—tabu search algorithm for single machine total weighted tardiness problem,” Comput. Ind. Eng., vol. 50, pp. 1–14, May 2006.
[9] Ü. Bilge, M. Kurtulan, and F. Kıraç, "A tabu search algorithm for the single machine total weighted tardiness problem,” Eur. J. Oper. Res., vol. 176, pp. 1423–1435, February 2007.
[10] A. C. Nearchou, "Solving the single machine total weighted tardiness scheduling problem using a hybrid simulated annealing algorithm,” in Proc. 2nd IEEE Int. Conf. Industrial Informatics, New Jersey, 2004, pp. 513–516.
[11] O. Holthaus and C. Rajendran, "A fast ant-colony algorithm for single-machine scheduling to minimize the sum of weighted tardiness of jobs,” J. Oper. Res. Soc., vol.56, pp. 947–953, August 2005.
[12] R. K. Congram, C. N. Potts, and S. L. Van de Velde, "An iterated dynasearch algorithm for the single-machine total weighted tardiness scheduling problem,” Informs J. Comput., vol. 14, 52–67, Winter 2002.
[13] N. Liu, M. Abdelrahman, and S. Ramaswamy, "A genetic algorithm for single machine total weighted tardiness scheduling problem,” Int. J. Intelligent Control and Systems, vol. 10, pp. 218–225, September 2005.
[14] A. Ferrolho and M. Crisostomo, "Single machine total weighted tardiness problem with genetic algorithms,” in Proc. 2007 IEEE/ACS Int. Conf. Computer Systems and Applications, Amman, Jordan, 2007, pp. 1–8.
[15] J. E. C. Arroyo, A. G. Santos, F. L. S. Silva, and A. F. Araújo, "A GRASP with path relinking for the single machine total weighted tardiness problem,” in Proc. 8th Int. Conf. Hybrid Intelligent Systems, Barcelona, Spain, 2008, pp. 726–731.
[16] X. Wang and L. Tang, "A population-based variable neighborhood search for the single machine total weighted tardiness problem,” Comput.Oper. Res., vol. 36, pp. 2105–2110, June 2009.
[17] S. Sabamoniri, K. Asghari, and M. J. Hosseini, "Solving single machine total weighted tardiness problem using variable structure learning automata,” Int. J. Comput. Appl., vol. 56, pp. 37–42, October 2012.
[18] C. E. Rasmussen and C. K. I. Williams, Gaussian Processes for Machine Learning, Cambridge: MIT Press, 2006, ch. 2.
[19] F. H. Sinz, J. Q. Candela, G. H. Bakir, C. E. Rasmussen, and M. O. Franz, "Learning depth from stereo,” in Proc. 26th DAGM Symp. Pattern Recognition, Tübingen, Germany, 2004, pp. 245–252.
[20] A. Krause, A. Singh, and C. Guestrin, "Near-optimal sensor placements in Gaussian processes: theory, efficient algorithms and empirical studies,” J. Mach. Learn. Res., vol. 9, pp. 235–284, February 2008.
[21] J. Yuan, K. Wang, T. Yu, and M. Fang, "Reliable multi-objective optimization of high-speed WEDM process based on Gaussian process regression,” Int. J. Mach. Tool.Manu., vol. 48, pp. 47–60, January 2008.
[22] T. Idé and S. Kato, "Travel-time prediction using Gaussian process regression: a trajectory-based approach,” in Proc. 9th SIAM Int. Conf. Data Mining, Nevada, USA, 2009, pp. 1185–1196.
[23] W. Kongkaew and J. Pichitlamken, "A Gaussian process regression model for the traveling salesman problem,” J. Comput. Sci., vol. 8, pp. 1749–1758, August 2012.
[24] J. J. Kanet and X. Li, "A weighted modified due date rule for sequencing to minimize weighted tardiness,” J. Sched., vol. 7, pp. 261–276, July 2004.
[25] H.R. Lourenço, O.C. Martin, and T. Stützle, "Iterated local search: framework and applications,” in Handbook of Metaheuristics, M. Gendreau and J.Y. Potvin, Eds. New York: Springer-Verlag, 2010, pp. 363–397.
[26] P. Larrañaga, C. M. H. Kuijpers, R. H. Murga, I. Inza, and S. Dizdarevic, "Genetic algorithms for the travelling salesman problem: a review of representations and operators,” Artif. Intell. Rev., vol. 13, pp. 129–170, April 1999.
[27] C. E. Rasmussen and H. Nickisch, "Gaussian processes for machine learning (GPML) toolbox,” J. Mach. Learn. Res., vol. 11, pp. 3011–3015, November 2010.
[28] A.W. Johnson and S.H. Jacobson, "A class of convergent generalized hill climbing algorithms,” Appl. Math.Comput., vol. 125, pp. 359–373, January 2002.
[29] E.H.L. Aarts, J.H.M. Korst, and P.J.M. Van Laarhoven, "Simulated annealing,” in Local Search in Combinatorial Optimization, E. Aarts and J.K. Lenstra, Eds. Princeton: Princeton University Press, 2003, pp. 91–120.
[30] E. Aarts, J. Korst, and W. Michiels, "Simulated annealing,” in Search Methodologies: Introductory Tutorials in Optimization and Decision Support Techniques, E.K. Burke and G. Kendall, Eds. New York: Springer-Verlag, 2005, pp. 187–210.
[31] J.E.Beasley,"OR-Library,”Availablesource: http://people.brunel.ac.uk/~mastjjb/jeb/orlib/wtinfo.html, June 2012.