Editorial Board
Publishing Ethics
Author Guide
Submission Prepare Your ManuscriptPeer review
Archive
English version:
Journal of Applied and Industrial Mathematics, 2019, 13:2, 239-249
Volume 26, No 2, 2019, P. 60-78
UDC 519.8
P. A. Kononova and Yu. A. Kochetov
A local search algorithm for the single machine scheduling problem with setups and a storage
Abstract:
We present a new mathematical model for a single machine scheduling problem originated from the tile industry. The model takes into account the sequence-dependent setup times, the minimal batch size, heterogeneous orders of customers, and a stock in storage. As the objective function we use the penalty for tardiness of the customers’ orders and the total storage cost for final products. A mixed-integer linear programming model is applied for small test instances. For real-world applications, we design a randomized tabu search algorithm. The computational results for some test instances from a Novorossiysk company are discussed.
Tab. 3, illustr. 1, bibliogr. 25.
Keywords: tabu search, scheduling, due date, tardiness, setup time.
DOI: 10.33048/daio.2019.26.634
Polina A. Kononova 1,2
Yury A. Kochetov 1,2
1. Sobolev Institute of Mathematics,
4 Koptyug Ave., 630090 Novosibirsk, Russia
2. Novosibirsk State University,
2 Pirogov St., 630090 Novosibirsk, Russia
e-mail: pkononova@math.nsc.ru, jkochet@math.nsc.ru
Received October 11, 2018
Revised February 4, 2019
Accepted February 27, 2019
References
[1] I. A. Davydov, P. A. Kononova, and Yu. A. Kochetov, Local search with an exponential neighborhood for the servers load balancing problem, Diskretn. Anal. Issled. Oper., 21, No. 6, 21–34, 2014 [Russian]. Translated in J. Appl. Ind. Math., 9, No. 1, 27–35, 2015.[2] I. A. Davydov, A. A. Melnikov, and P. A. Kononova, Local search for load balancing problems for servers with large dimension, Avtom. Telemekh., No. 3, 34–50, 2017 [Russian]. Translated in Autom. Remote Control, 78, No. 3, 412–424, 2017.
[3] Yu. A. Kochetov, A. A. Panin, and A. V. Plyasunov, Genetic local search and hardness of approximation for the server load balancing problem, Avtom. Telemekh., No. 3, 51–62, 2017 [Russian]. Translated in Autom. Remote Control, 78, No. 3, 425–434, 2017.
[4] S. M. Lavlinskii, A. A. Panin, and A. V. Plyasunov, A bilevel planning model for public-private partnership, Avtom. Telemekh., No. 11, 89–103, 2015 [Russian]. Translated in Autom. Remote Control, 76, No. 11, 1976–1987, 2015.
[5] A. A. Panin, M. G. Pashchenko, and A. V. Plyasunov, Bilevel competitive facility location and pricing problems, Avtom. Telemekh., No. 4, 153–169, 2014 [Russian]. Translated in Autom. Remote Control, 75, No. 4, 715–727, 2014.
[6] E. H. L. Aarts, J. H. M. Korst, and P. J. M. van Laarhoven, Simulated annealing, in Local Search in Combinatorial Optimization, pp. 91–120, Wiley, Chichester, 1997.
[7] A. Allahverdi, The third comprehensive survey on scheduling problems with setup times/costs, Eur. J. Oper. Res., 246, No. 2, 345–378, 2015.
[8] L.-P. Bigras, M. Gamache, and G. Savard, The time-dependent traveling salesman problem and single machine scheduling problems with sequence dependent setup times, Discrete Optim., 5, No. 4, 685–699, 2008.
[9] J. Brimberg, P. Hansen, and N. Mladenovic, Attraction probabilities in variable neighborhood search, 4OR, 8, No. 2, 181–194, 2010.
[10] P. Brucker, Scheduling Algorithms, Springer, Heidelberg, 2007.
[11] B. Chen, C. N. Potts, and G. J. Woeginger, A review of machine scheduling: complexity, algorithms and approximability, in Handbook of Combinatorial Optimization, Vol. 3, pp. 21–169, Kluwer Acad. Publ., Dordrecht, 1998.
[12] A. Dolgui, A. V. Eremeev, M. Ya. Kovalyov, and P. M. Kuznetsov, Multi-product lot sizing and scheduling on unrelated parallel machines, IIE Trans., 42, No. 7, 514–524, 2010.
[13] A. I. Erzin, N. Mladenovic, and R. V. Plotnikov, Variable neighborhood search variants for min-power symmetric connectivity problem, Comput. Oper. Res., 78, 557–563, 2017.
[14] A. I. Erzin and R. V. Plotnikov, Using VNS for the optimal synthesis of the communication tree in wireless sensor networks, Electron. Notes Discrete Math., 47, 21–28, 2015.
[15] F. Glover and M. Laguna, Tabu Search, Norwell, MA: Kluwer Acad. Publ., 1997.
[16] S. Iellamo, E. V. Alekseeva, L. Chen, M. Coupechoux, and Yu. A. Kochetov, Competitive location in cognitive radio networks, 4OR, 13, No. 1, 81–110, 2015.
[17] J. R. Jackson, Scheduling a production line to minimize maximum tardiness, Res. Rep., No. 43, Univ. Calif., Los Angeles, 1955.
[18] S. L. Janak, Ch. A. Floudas, J. Kallrath, and N. Vormbrock, Production scheduling of a large-scale industrial batch plant. I. Short-term and medium-term scheduling, Ind. Eng. Chem. Res., 45, 8234–8252, 2006.
[19] Yu. A. Kochetov, Facility location: Discrete models and local search methods, Combinatorial Optimization: Methods and Applications, pp. 97–134, IOS Press, Amsterdam, 2011.
[20] Yu. A. Kochetov and A. A. Kondakov, VNS matheuristic for a bin packing problem with a color constraint, Electron. Notes Discrete Math., 58, 39–46, 2017.
[21] B. Korte and J. Vygen, Combinatorial Optimization: Theory and Algorithms, Springer, Heidelberg, 2012 (Algorithms Comb., Vol. 21).
[22] N. Mladenovic, J. Brimberg, P. Hansen, and J. A. Moreno-Pérez, The $p$-median problem: A survey of metaheuristic approaches, Eur. J. Oper. Res., 179, No. 3, 927–939, 2007.
[23] Y. Pochet and L. A. Wolsey, Production Planning by Mixed Integer Programming, Springer, New York, 2006.
[24] W. E. Smith, Various optimizers for single-stage production, Nav. Res. Logist. Q., 3, No. 1–2, 59–66, 1956.
[25] E.-G. Talbi, Metaheuristics: From Design to Implementation, Wiley, Hoboken, NJ, 2009.
