Geodesic
A local search algorithm for the single machine scheduling problem with setups and a storage
Diskretnyj analiz i issledovanie operacij, Tome 26 (2019) no. 2, pp. 60-78.

Voir la notice de l'article provenant de la source Math-Net.Ru

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. 
@article{DA_2019_26_2_a2,
     author = {P. A. Kononova and Yu. A. Kochetov},
     title = {A local search algorithm for the single machine scheduling problem with setups and a storage},
     journal = {Diskretnyj analiz i issledovanie operacij},
     pages = {60--78},
     publisher = {mathdoc},
     volume = {26},
     number = {2},
     year = {2019},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/DA_2019_26_2_a2/}
}
TY  - JOUR
AU  - P. A. Kononova
AU  - Yu. A. Kochetov
TI  - A local search algorithm for the single machine scheduling problem with setups and a storage
JO  - Diskretnyj analiz i issledovanie operacij
PY  - 2019
SP  - 60
EP  - 78
VL  - 26
IS  - 2
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DA_2019_26_2_a2/
LA  - ru
ID  - DA_2019_26_2_a2
ER  - 
%0 Journal Article
%A P. A. Kononova
%A Yu. A. Kochetov
%T A local search algorithm for the single machine scheduling problem with setups and a storage
%J Diskretnyj analiz i issledovanie operacij
%D 2019
%P 60-78
%V 26
%N 2
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DA_2019_26_2_a2/
%G ru
%F DA_2019_26_2_a2
P. A. Kononova; Yu. A. Kochetov. A local search algorithm for the single machine scheduling problem with setups and a storage. Diskretnyj analiz i issledovanie operacij, Tome 26 (2019) no. 2, pp. 60-78. http://geodesic.mathdoc.fr/item/DA_2019_26_2_a2/

[1] I. A. Davydov, P. A. Kononova, Yu. A. Kochetov, “Local search with an exponential neighborhood for the servers load balancing problem”, J. Appl. Ind. Math., 9:1 (2015), 27–35 | DOI | MR | Zbl

[2] I. A. Davydov, A. A. Melnikov, P. A. Kononova, “Local search for load balancing problems for servers with large dimension”, Autom. Remote Control, 78:3 (2017), 412–424 | DOI | MR | Zbl

[3] Yu. A. Kochetov, A. A. Panin, A. V. Plyasunov, “Genetic local search and hardness of approximation for the server load balancing problem”, Autom. Remote Control, 78:3 (2017), 425–434 | DOI | MR | Zbl

[4] S. M. Lavlinskii, A. A. Panin, A. V. Plyasunov, “A bilevel planning model for public-private partnership”, Autom. Remote Control, 76:11 (2015), 1976–1987 | DOI | MR | Zbl

[5] A. A. Panin, M. G. Pashchenko, A. V. Plyasunov, “Bilevel competitive facility location and pricing problems”, Autom. Remote Control, 75:4 (2014), 715–727 | DOI | MR | Zbl

[6] Aarts E. H. L., Korst J. H. M., van Laarhoven P. J. M., “Simulated annealing”, Local search in combinatorial optimization, Wiley, Chichester, 1997, 91–120 | MR | Zbl

[7] Allahverdi A., “The third comprehensive survey on scheduling problems with setup times/costs”, Eur. J. Oper. Res., 246:2 (2015), 345–378 | DOI | MR | Zbl

[8] Bigras L.-P., Gamache M., Savard G., “The time-dependent traveling salesman problem and single machine scheduling problems with sequence dependent setup times”, Discrete Optim., 5:4 (2008), 685–699 | DOI | MR | Zbl

[9] Brimberg J., Hansen P., Mladenović N., “Attraction probabilities in variable neighborhood search”, 4OR, 8:2 (2010), 181–194 | DOI | MR | Zbl

[10] Brucker P., Scheduling algorithms, Springer, Berlin–Heidelberg, 2007 | MR | Zbl

[11] Chen B., Potts C. N., Woeginger G. J., “A review of machine scheduling: Complexity, algorithms and approximability”, Handbook of combinatorial optimization, v. 3, Kluwer Acad. Publ., Dordrecht, 1998, 21–169 | MR | Zbl

[12] Dolgui A., Eremeev A. V., Kovalyov M. Y., Kuznetsov P. M., “Multi-product lot sizing and scheduling on unrelated parallel machines”, IIE Trans., 42:7 (2010), 514–524 | DOI

[13] Erzin A. I., Mladenović N., Plotnikov R. V., “Variable neighborhood search variants for min-power symmetric connectivity problem”, Comput. Oper. Res., 78 (2017), 557–563 | DOI | MR | Zbl

[14] Erzin A. I., Plotnikov R. V., “Using VNS for the optimal synthesis of the communication tree in wireless sensor networks”, Electron. Notes Discret. Math., 47 (2015), 21–28 | DOI | MR | Zbl

[15] Glover F., Laguna M., Tabu Search, Kluwer Acad. Publ., Norwell, MA, 1997 | MR

[16] Iellamo S., Alekseeva E. V., Chen L., Coupechoux M., Kochetov Yu. A., “Competitive location in cognitive radio networks”, 4OR, 13:1 (2015), 81–110 | DOI | MR | Zbl

[17] Jackson J. R., Scheduling a production line to minimize maximum tardiness, Res. Rep. No 43, Univ. Calif., Los Angeles, 1955

[18] Janak S. L., Floudas Ch. A., Kallrath J., Vormbrock N., “Production scheduling of a large-scale industrial batch plant. I. Short-term and medium-term scheduling”, Ind. Eng. Chem. Res., 45 (2006), 8234–8252 | DOI

[19] Kochetov Yu. A., “Facility location: discrete models and local search methods”, Combinatorial optimization. Methods and applications, IOS Press, Amsterdam, 2011, 97–134 | Zbl

[20] Kochetov Yu., Kondakov A. A., “VNS matheuristic for a bin packing problem with a color constraint”, Electron. Notes Discret. Math., 58 (2017), 39–46 | DOI | MR | Zbl

[21] Korte B. H., Vygen J., Combinatorial optimization: Theory and algorithms, Algorithms Comb., 21, Springer, New York, 2012 | MR | Zbl

[22] Mladenović N., Brimberg J., Hansen P., Moreno-Pérez J. A., “The $p$-median problem: A survey of metaheuristic approaches”, Eur. J. Oper. Res., 179:3 (2007), 927–939 | DOI | MR | Zbl

[23] Pochet Y., Wolsey L. A., Production planning by mixed integer programming, Springer, New York, 2005 | MR

[24] Smith W. E., “Various optimizers for single-stage production”, Nav. Res. Logist. Q, 3:1–2 (1956), 59–66 | DOI | MR

[25] Talbi E.-G., Metaheuristics: From design to implementation, Wiley, Hoboken, NJ, 2009 | Zbl