1. Home
  2. Issues
  3. Volume 33, Issue 3 (2022)
  4. Tabu Search Based Hybrid Meta-Heuristic ...

Informatica


Tabu Search Based Hybrid Meta-Heuristic Approaches for Schedule-Based Production Cost Minimization Problem for the Case of Cable Manufacturing Systems
Volume 33, Issue 3 (2022), pp. 499–522
Pub. online: 4 January 2022      Type: Research Article      Open accessOpen Access
Received
1 February 2021
Accepted
1 December 2021
Published
4 January 2022

Abstract

This paper models and solves the scheduling problem of cable manufacturing industries that minimizes the total production cost, including processing, setup, and storing costs. Two hybrid meta-heuristics, which combine simulated annealing and variable neighbourhood search algorithms with tabu search algorithm, are proposed. Applying some case-based theorems and rules, a special initial solution with optimal setup cost is obtained for the algorithms. The computational experiments, including parameter tuning and final experiments over the benchmarks obtained from a real cable manufacturing factory, show superiority of the combination of tabu search and simulated annealing comparing to the other proposed hybrid and classical meta-heuristics.

References

 
Ahmadi, E., Zandieh, M., Farrokh, M., Emami, S.M. (2016). A multi objective optimization approach for flexible job shop scheduling problem under random machine breakdown by evolutionary algorithms. Computers & Operations Research, 73, 56–66.
 
Akbari, M., Rashidi, H. (2016). A multi-objectives scheduling algorithm based on cuckoo optimization for task allocation problem at compile time in heterogeneous systems. Expert Systems with Applications, 60, 234–248.
 
Aliya, F., Fazli, A., Hussain, S.S.B. (2020). Geometric operators based on linguistic interval-valued intuitionistic neutrosophic fuzzy number and their application in decision making. Ann Optim Theory Practices, 3(1), 47–71.
 
Allahverdi, A., Ng, C.T., Cheng, T.C.E., Kovalyov, M.Y. (2008). A survey of scheduling problems with setup times or costs. European Journal of Operational Research, 187, 985–1032.
 
Bellanger, A., Janiak, A., Kovalyov, M.Y., Oulamara, A. (2012). Scheduling an unbounded batching machine with job processing time compatibilities. Discrete Applied Mathematics, 160(1–2), 15–23.
 
Che, A., Zeng, Y., Lyu, K. (2016). An efficient greedy insertion heuristic for energy-conscious single machine scheduling problem under time-of-use electricity tariffs. Journal of Cleaner Production, 129, 565–577.
 
Chu, Y., You, F. (2013). Integration of production scheduling and dynamic optimization for multi-product CSTRs: generalized benders decomposition coupled with global mixed-integer fractional programming. Computers & Chemical Engineering, 58, 315–333.
 
Chu, Y., You, F., Wassick, J.M. (2014). Hybrid method integrating agent-based modeling and heuristic tree search for scheduling of complex batch processes. Computers & Chemical Engineering, 60, 277–296.
 
Dong, M.G., Wang, N. (2012). A novel hybrid differential evolution approach to scheduling of large-scale zero-wait batch processes with setup times. Computers & Chemical Engineering, 45, 72–83.
 
Dugonik, J., Bošković, B., Brest, J., Sepesy Maučec, M. (2019). Improving statistical machine translation quality using differential evolution. Informatica, 30(4), 629–645.
 
Ebrahimi, M., Fatemi Ghomi, S.M.T., Karimi, B. (2014). Hybrid flow shop scheduling with sequence dependent family setup time and uncertain due dates. Applied Mathematical Modelling, 38(9–10), 2490–2504.
 
Fang, Y., Lu, X. (2016). Online parallel-batch scheduling to minimize total weighted completion time on single unbounded machine. Information Processing Letters, 116(8), 526–531.
 
Fernández, P., Lančinskas, A., Pelegrín, B., Žilinskas, J. (2020). A discrete competitive facility location model with minimal market share constraints and equity-based ties breaking rule. Informatica, 31(2), 205–224.
 
Ghadiri Nejad, M., Banar, M. (2018). Emergency response time minimization by incorporating ground and aerial transportation. Annals of Optimization Theory and Practice, 1(1), 43–57.
 
Gomes, H.C., Neves, F.D.A.D., Souza, M.J.F. (2014). Multi-objective metaheuristic algorithms for the resource-constrained project scheduling problem with precedence relations. Computers & Operations Research, 44, 92–104.
 
Guo, Y., Liu, X., Chen, L. (2020). Improved butterfly optimisation algorithm based on guiding weight and population restart. Journal of Experimental & Theoretical Artificial Intelligence, 33, 127–145. https://doi.org/10.1080/0952813X.2020.1725651.
 
Hajiaghaei-Keshteli, M., Aminnayeri, M. (2014). Solving the integrated scheduling of production and rail transportation problem by Keshtel algorithm. Applied Soft Computing, 25, 184–203.
 
Hajiaghaei–Keshteli, M., Aminnayeri, M., Fatemi Ghomi, S.M.T. (2014). Integrated scheduling of production and rail transportation. Computers and Industrial Engineering, 74, 240–256.
 
Hao, J., Liu, M., Jiang, S., Wu, C. (2015). A soft-decision based two-layered scheduling approach for uncertain steelmaking-continuous casting process. European Journal of Operational Research, 244(3), 966–979.
 
Hassanpour, M. (2020). Classification of seven Iranian recycling industries using MCDM models. Annals of Optimization Theory and Practice, 3(4), 37–52.
 
He, J., Li, Q., Xu, D. (2016). Scheduling two parallel machines with machine-dependent availabilities. Computers & Operations Research, 72, 31–42.
 
Hosseini Shirvani, M. (2020). Bi-objective web service composition problem in multi-cloud environment: a bi-objective time-varying particle swarm optimisation algorithm. Journal of Experimental & Theoretical Artificial Intelligence. https://doi.org/10.1080/0952813X.2020.1725652.
 
Hsieh, F.S. (2017). A hybrid and scalable multi-agent approach for patient scheduling based on Petri net models. Applied Intelligence. 47, 1068–1086. https://doi.org/10.1007/s10489-017-0935-y.
 
Hu, W., Wang, H., Yan, L., Du, B. (2016). A swarm intelligent method for traffic light scheduling: application to real urban traffic networks. Applied Intelligence, 44(1), 208–231.
 
Hussain, A., Khan, M.S.A. (2020). Average operators based on spherical cubic fuzzy number and their application in multi-attribute decision making. Annals of Optimization Theory and Practice, 3(4), 83–111.
 
Jamili, A. (2016). Robust job shop scheduling problem: mathematical models, exact and heuristic algorithms. Expert Systems with Applications, 55, 341–350.
 
Ji, M., Ge, J., Chen, K., Cheng, T.C.E. (2013). Single-machine due-window assignment and scheduling with resource allocation, aging effect, and a deteriorating rate-modifying activity. Computers & Industrial Engineering, 66(4), 952–961.
 
Karimi-Nasab, M., Seyedhoseini, S.M. (2013). Multi-level lot sizing and job shop scheduling with compressible process times: a cutting plane approach. European Journal of Operational Research, 231(3), 598–616.
 
Kim, M.Y., Lee, Y.H. (2012). MIP models and hybrid algorithm for minimizing the makespan of parallel machines scheduling problem with a single server. Computers & Operations Research, 39(11), 2457–2468.
 
Kirkpatrick, S., Gelatt, C.D. Jr., Vecchi, M.P. (1983). Optimization by simulated annealing. Science, 220, 671–680.
 
Koulamas, C., Panwalkar, S.S. (2016). The proportionate two-machine no-wait job shop scheduling problem. European Journal of Operational Research, 252(1), 131–135.
 
Ku, W.Y., Beck, J.C. (2016). Mixed integer programming models for job shop scheduling: a computational analysis. Computers & Operations Research, 73, 165–173.
 
Kurdi, M. (2015). A new hybrid island model genetic algorithm for job shop scheduling problem. Computers & Industrial Engineering, 88, 273–283.
 
Lamghari, A., Dimitrakopoulos, R. (2012). A diversified Tabu search approach for the open-pit mine production scheduling problem with metal uncertainty. European Journal of Operational Research, 222(3), 642–652.
 
Lee, W.C., Chuang, M.C., Yeh, W.C. (2012). Uniform parallel-machine scheduling to minimize makespan with position-based learning curves. Computers & Industrial Engineering, 63(4), 813–818.
 
Leite, A., Dimitrakopoulos, R. (2014). Stochastic optimization of mine production scheduling with uncertain ore/metal/waste supply. International Journal of Mining Science and Technology, 24(6), 755–762.
 
Li, X., Gao, L. (2016). An effective hybrid genetic algorithm and tabu search for flexible job shop scheduling problem. International Journal of Production Economics, 174, 93–110.
 
Li, W., Li, J., Zhang, X., Chen, Z. (2015). Penalty cost constrained identical parallel machine scheduling problem. Theoretical Computer Science, 607(2), 181–192.
 
Lu, C.C., Ying, K.C., Lin, S.W. (2014). Robust single machine scheduling for minimizing total flow time in the presence of uncertain processing times. Computers & Industrial Engineering, 74, 102–110.
 
Mahmoodirad, A., Niroomand, S. (2020). Uncertain location–allocation decisions for a bi-objective two-stage supply chain network design problem with environmental impacts. Expert Systems, e12558.
 
Mahmoodirad, A., Heydari, A., Niroomand, S. (2019). An effective hybrid fuzzy programming approach for an entropy-based multi-objective assembly line balancing problem. Informatica, 30(3), 503–528.
 
Martin, S., Ouelhadj, D., Beullens, P., Ozcan, E., Juan, A.A., Burke, E.K. (2016). A multi-agent based cooperative approach to scheduling and routing. European Journal of Operational Research, 254(1), 169–178.
 
Mirshekarian, S., Šormaz, D.N. (2016). Correlation of job-shop scheduling problem features with scheduling efficiency. Expert Systems with Applications, 62, 131–147.
 
Misevičius, A., Kuznecovaitė, D., Platužienė, J. (2018). Some further experiments with crossover operators for genetic algorithms. Informatica, 29(3), 499–516.
 
Mor, B., Mosheiov, G. (2014). Batch scheduling of identical jobs with controllable processing times. Computers & Operations Research, 41, 115–124.
 
Nair, A., Ataseven, C., Habermann, M., Dreyfus, D. (2016). Toward a continuum of measurement scales in Just-in-Time (JIT) research – an examination of the predictive validity of single-item and multiple-item measures. Operations Management Research, 9(1), 35–48.
 
Niroomand, S., Vizvari, B. (2015). Exact mathematical formulations and metaheuristic algorithms for production cost minimization: a case study of the cable industry. International Transactions in Operational Research, 22, 519–544.
 
Niroomand, S., Hadi-Vencheh, A., Mirzaei, N., Molla-Alizadeh-Zavardehi, S. (2016). Hybrid greedy algorithms for fuzzy tardiness/earliness minimization in a special single machine scheduling problem: case study and generalisation. International Journal of Computer Integrated Manufacturing, 29(8), 870–888.
 
Niroomand, S., Bazyar, A., Alborzi, M., Mahmoodirad, A. (2018). A hybrid approach for multi-criteria emergency center location problem considering existing emergency centers with interval type data: a case study. Journal of Ambient Intelligence and Humanized Computing, 9(6), 1999–2008.
 
Niroomand, S., Mahmoodirad, A., Mosallaeipour, S. (2019). A hybrid solution approach for fuzzy multiobjective dual supplier and material selection problem of carton box production systems. Expert Systems, 36(1), e12341.
 
Niu, S.H., Ong, S.K., Nee, A.Y.C. (2013). An improved intelligent water drops algorithm for solving multi-objective job shop scheduling. Engineering Applications of Artificial Intelligence, 26(10), 2431–2442.
 
Parastegari, M., Hooshmand, R.A., Khodabakhshian, A., Vatanpour, M. (2013). AC constrained hydro-thermal generation scheduling problem: Application of Benders decomposition method improved by BFPSO. International Journal of Electrical Power & Energy Systems, 49, 199–212.
 
Pasandideh, S.H.R., Akhavan Niaki, S.T., Asadi, K. (2015). Bi-objective optimization of a multi-product multi-period three-echelon supply chain problem under uncertain environments: NSGA-II and NRGA. Information Sciences, 292, 57–74.
 
Pinedo, M.L. (2008). Scheduling: Theory, Algorithms, and Systems, 3rd ed. Springer, New York.
 
Qu, J., Zhong, X., Li, C.L. (2016). Faster algorithms for single machine scheduling with release dates and rejection. Information Processing Letters, 116(8), 503–507.
 
Quintana, D., Cervantes, A., Saez, Y., Isasi, P. (2017). Clustering technique for large-scale home care crew scheduling problems. Applied Intelligence, 47(2), 443–455.
 
Ozgur, C.O., Bai, L. (2010). Hierarchical composition heuristic for asymmetric sequence dependent single machine scheduling problems. Operations Management Research, 3(1), 98–106.
 
Rahmani, D., Heydari, M. (2014). Robust and stable flow shop scheduling with unexpected arrivals of new jobs and uncertain processing times. Journal of Manufacturing Systems, 33(1), 84–92.
 
Reisi-Nafchi, M., Moslehi, G. (2015). A hybrid genetic and linear programming algorithm for two-agent order acceptance and scheduling problem. Applied Soft Computing, 33, 37–47.
 
Santander-Mercado, A., Jubiz-Diaz, M. (2016). The economic lot scheduling problem: a survey. International Journal of Production Research, 54(16), 4973–4992.
 
Shi, L., Jiang, Y., Wang, L., Huang, D. (2015). A novel two-stage Lagrangian decomposition approach for refinery production scheduling with operational transitions in mode switching. Chinese Journal of Chemical Engineering, 23(11), 1793–1800.
 
Taassori, M., Taassori, M., Niroomand, S., Vizvári, B., Uysal, S., Hadi-Vencheh, A. (2015). OPAIC: an optimization technique to improve energy consumption and performance in application specific network on chips. Measurement, 74, 208–220.
 
Tavana, M., Santos-Arteaga, F.J., Mahmoodirad, A., Niroomand, S., Sanei, M. (2018). Multi-stage supply chain network solution methods: hybrid metaheuristics and performance measurement. International Journal of Systems Science: Operations & Logistics, 5(4), 356–373.
 
Ullah, K., Mahmood, T., Jan, N., Ahmad, Z. (2020). Policy decision making based on some averaging aggregation operators of t-spherical fuzzy sets; a multi-attribute decision making approach. Annals of Optimization Theory and Practice, 3(3), 69–92.
 
Vakhania, N., Hernandez, J.A., Werner, F. (2014). Scheduling unrelated machines with two types of jobs. International Journal of Production Research, 52(13), 3793–3801.
 
Vizvári, B., Guden, H., Nejad M, G. (2018). Local search based meta-heuristic algorithms for optimizing the cyclic flexible manufacturing cell problem. Annals of Optimization Theory and Practice, 1(3), 15–32.
 
Wan, L., Yuan, J. (2013). Single-machine scheduling to minimize the total earliness and tardiness is strongly NP-hard. Operations Research Letters, 41, 363–365.
 
Wolosewicz, C., Dauzère-Pérès, S., Aggoune, R. (2015). A Lagrangian heuristic for an integrated lot-sizing and fixed scheduling problem. European Journal of Operational Research, 244(1), 3–12.
 
Wu, C.C., Lee, W.C., Liou, M.J. (2013). Single-machine scheduling with two competing agents and learning consideration. Information Sciences, 251, 136–149.
 
Xiao, J., Yang, H., Zhang, C., Zheng, L., Gupta, J.N.D. (2015). A hybrid Lagrangian-simulated annealing-based heuristic for the parallel-machine capacitated lot-sizing and scheduling problem with sequence-dependent setup times. Computers & Operations Research, 63, 72–82.
 
Ying, K.C., Lu, C.C., Chen, J.C. (2016). Exact algorithms for single-machine scheduling problems with a variable maintenance. Computers & Industrial Engineering, 98, 427–433.
 
Zhang, L., Wong, T.N. (2016). Solving integrated process planning and scheduling problem with constructive meta-heuristics. Information Sciences, 340–341, 1–16.
 
Zheng, Z.X., Li, J.Q., Han, Y.Y. (2020). An improved invasive weed optimization algorithm for solving dynamic economic dispatch problems with valve-point effects. Journal of Experimental & Theoretical Artificial Intelligence, 32, 805–829. https://doi.org/10.1080/0952813X.2019.1673488.
 
Zhou, S., Liu, M., Chen, H., Li, X. (2016). An effective discrete differential evolution algorithm for scheduling uniform parallel batch processing machines with non-identical capacities and arbitrary job sizes. International Journal of Production Economics, 179, 1–11.
 
Zinder, Y., Walker, S. (2015). Algorithms for scheduling with integer preemptions on parallel machines to minimize the maximum lateness. Discrete Applied Mathematics, 196, 28–53.

Biographies

Daneshdoost Fereshteh

F. Daneshdoost is a lecturer with MSc degree of industrial engineering in Firouzabad Institute of Higher Education, Iran.

Hajiaghaei-Keshteli Mostafa
https://orcid.org/0000-0002-9988-2626
mostafahaji@tec.mx

M. Hajiaghaei-Keshteli is an assistant professor of industrial engineering in University of Science and Technology of Mazandaran, Behshahr, Iran. His research interests are operations research and exact and meta-heuristic solution approaches.

Sahin Ramazan

R. Sahin in an associate professor of industrial engineering in Gazi University in Turkey. He received his PhD degree in industrial engineering from Gazi University. His research interests are operations research, fuzzy theory, and exact and meta-heuristic solution approaches.

Niroomand Sadegh
sadegh.niroomand@yahoo.com

S. Niroomand is an associate professor of industrial engineering in Firouzabad Institute of Higher Education in Iran. He received his PhD degree in industrial engineering from Eastern Mediterranean University (in Turkey), in 2013. His research interests are operations research, fuzzy theory, and exact and meta-heuristic solution approaches.


Full article Related articles Cited by PDF XML
Full article Related articles Cited by PDF XML

Copyright
© 2022 Vilnius University
Open access article under the CC BY license.

Keywords
scheduling theory single machine scheduling cable manufacturing hybrid meta-heuristic tabu search

Funding
This study was supported by Firouzabad Institute of Higher Education, Iran (research project no. 1399.001). The authors are grateful of the financial support.

Metrics
since January 2020
1154

Article info
views

789

Full article
views

675

PDF
downloads

178

XML
downloads


Share


RSS