A Comparative Study of Scalarization Techniques on the Multi-Objective Single Machine-Scheduling Problem Under Sequence-Dependent Setup Time, Release Date and Due Date Constraints

Zeynep Idil ERZURUM CICEK, (Girilmemişş)
ZEHRA KAMIŞLI ÖZTÜRK (Girilmemişş)
Gazi University Journal of Science
0 0
Yıl: 2020 Cilt: 33 Sayı: 2 Sayfa Aralığı: 429 - 444 Metin Dili: İngilizce DOI: 10.35378/gujs.581780 İndeks Tarihi: 04-11-2020

A Comparative Study of Scalarization Techniques on the Multi-Objective Single Machine-Scheduling Problem Under Sequence-Dependent Setup Time, Release Date and Due Date Constraints

Öz:
In this paper, we considered a two-objective machine-scheduling problem under sequencedependent setup time, release date and due date constraints. The problem is formulated as amulti-objective mixed-integer programming model. Two conflicting objectives are consideredas minimization of maximum completion time (makespan) and total tardiness. Despite themost use of metaheuristics in this kind of multi-objective problems, here, we try to solve theproblem by transforming the two-objectives as a single objective using scalarizationtechniques. Test instances are generated as proposed in the scheduling literature. The solutionsare obtained using Weighted Sum Scalarization, Benson’s Method and Pascoletti−SerafiniMethod. In addition, a comparison of scalarization techniques using Δ performance metric isgiven on the considered problem instances. The obtained results are evaluated and Δ values,which were obtained for Benson’s method, are mostly better than other techniques for thegenerated test problems.
Anahtar Kelime:

Belge Türü: Makale Makale Türü: Araştırma Makalesi Erişim Türü: Erişime Açık
  • [1] Pinedo, M., Scheduling Theory, Algorithms, and Systems. 4th ed. New York, NY, Springer, (2008).
  • [2] Coobineh, F.F., Mohebbi, E., Khoo, H., "A multi-objective tabu search for a single machine scheduling problem with sequence-dependent setup times", European Journal of Operations Research, 175(1):318-337, (2006).
  • [3] Kuo, W.H., Yang, D.L., "Single machine scheduling with past-sequence-dependent setup times and learning effects", Information Processing Letters, 102(1):22-26, (2007).
  • [4] Allahverdi, A., Soroush, H., "The significance of reducing setup times/setup costs", European Journal of Operations Research, 187(3):978-984, (2008).
  • [5] Sioud, A., Gravel, M., Gagn, C., "A hybrid genetic algorithm for single machine scheduling problem with sequence-dependent setup times", Computers and Operation Research, 39:2415-2424, (2012).
  • [6] Liao C.J., Juan H.C., "An ant colony optimization for single-machine tardiness scheduling with sequence-dependent setups", Computers and Operations Research, 34(7):1899-1909, (2007).
  • [7] Tasgetiren M., Pan, Q., Liang, Y., "A discrete differential evolution algorithm for the single machine total weighted tardiness problem with sequence-dependent setup times", Computers and Operations Research, 36(6):1900-1915, (2009).
  • [8] Subramanian A., Battarra, M., Potts, C.N., "An Iterated Local Search heuristic for the single machine total weighted tardiness scheduling problem with sequence-dependent setup times", International Journal of Production Research, 52:2729–2742, (2014).
  • [9] Gonzalez, M.A., Vela, C.R., "An efficient memetic algorithm for total weighted tardiness minimization in a single machine with setups", Applied Soft Computing, 37:506-518, (2015).
  • [10] Luo, X., Chu, F., "A branch and bound algorithm of the single machine schedule with sequencedependent setup times for minimizing total tardiness", Applied Mathematics and Computation, 183(1):575-588, (2006).
  • [11] Jacob, V.V., Arroyo, J.E.C., "ILS heuristic for the single-machine scheduling problem with sequence-dependent family setup times to minimize total tardiness", Journal of Applied Mathematics, 2016:1-15, (2016).
  • [12] Keshevarz T., Savelsbergh, M., Salmasi, N., "A branch-and-bound algorithm for the single machine sequence-dependent group scheduling problem with earliness and tardiness penaltie", Applied Mathematical Modelling, 39(20):6410-6424, (2015).
  • [13] Hinder, O., Mason, A.J., "A novel integer programing formulation for scheduling with family setup times on a single machine to minimize maximum lateness", European Journal of Operational Research, 262(2):411-423, (2017).
  • [14] Kaplanoglu V., "Multi-agent based approach for single machine scheduling with sequencedependent setup times and machine maintenance", Applied Soft Computing, 23:165-179, (2014)
  • [15] Velez-Gallego, M., Maya, J., Montoya-Torres, J., "A beam search heuristicfor scheduling a single machine with release dates and sequence-dependent setup times to minimize the makespan", Computers and Operations Research, 73:132-140, (2016).
  • [16] Duenas, A., Petrovic D., "Multi-objective genetic algorithm for single machine scheduling problem under fuzziness", Fuzzy Optim. Decis. Making, 7(1):87-104, (2006).
  • [17] Wang S., "Bi-objective optimisation for integrated scheduling of single machine with setup times and preventive maintenance planning", International Journal of Production Research, 51(12): 3719– 3733, (2013).
  • [18] Yue, L., Guan, Z., Saif, U., Zhang, F., Wang, H., "Hybrid pareto artificial bee colony algorithm for multi-objective single machine group scheduling problem with sequence-dependent setup times and learning effects", SpringerPlus, 5(1):1593, (2016).
  • [19] Rubaiee, S., Yildirim, M.B., “An energy-aware multiobjective ant colony algorithm to minimize total completion time and energy cost on a single-machine preemptive scheduling”, Computers & Industrial Engineering, 127: 240-252, (2019).
  • [20] Zhang, S., Che, A., Wu, X., Chu, C., “Improved mixed-integer linear programming model and heuristics for bi-objective single-machine batch scheduling with energy cost consideration”, Engineering Optimization, 50:8, 1380-1394, (2018).
  • [21] Eichfelder G., "An adaptive scalarization method in multiobjective optimization", SIAM Journal on Optimization, 19(4):1694-1718, (2009).
  • [22] Ehrgott, M., Gandibleux, X., "Approximate solution methods for multiobjective combinatorial optimization", TOP Journal, 12(1):1-63, (2004).
  • [23] Soleimani-damaneh, M., Zamani, M., "On bensons scalarization in multi-objective optimization", Optim. Lett., 10(8):1757-1762, (2016).
  • [24] Kasimbeyli, R., Kamisli Ozturk, Z., Kasimbeyli, N., Yalcin, G., İcmen Erdem, B., "Comparison of some scalarization methods in multiobjective optimization", Bulletin of the Malaysian Mathematical Sciences Society, (2017).
  • [25] Gass, S., Saaty, T., "The computational algorithm for the parametric objective function", Naval Research Logistics, 12(1):1-89, (1955).
  • [26] Benson H.P., "Existence of efficient solutions for vector maximization problems", Journal of Optimization Theory and Applications , 26(4):569-580, (1978).
  • [27] Gerstewitz C., "Nichtkonvexe dualitat in der vektoroptimierung", Wissensch Zeitschr, 25(3):357- 364, (1983).
  • [28] Tan, K.C., Narasimhan, R., Rubin, P.A., Ragatz, G.L., "A comparison of four methods for minimizing total tardiness on a single processor with sequence-dependent setup times", Omega, 28(3):313-326, (2000).
  • [29] Ragatz G., "A branch-and-bound method for minimum tardiness sequencing on a single processor with sequence-dependent setup times", in Proceedings of the 24th Annual Meeting of the Decision Sciences Institue, 1375-1377, (1993).[
  • 30] Deb, K., Pratap, A., Agrawal, S., Meyarivan, T., "A fast and elitist mul-tiobjective genetic algorithm: Nsga-II", IEEE Transactions on Evolutionary Computation, 6(2):182-197, (2002).
  • [31] Jiang, S., Ong, Y., Zhang, J., Feng, L. "Consistencies and contradictions ofperformance metrics in multiobjective optimization", IEEE Transactions on Cybernetics, 44(12):2391–2404, (2014).
  • [32] Durillo, J., Nebro, A., Garcia-Nieto, J., Alba, E., On the Velocity Updatein Multi-Objective Particle Swarm Optimizers, Editors: Coello, C.A., Dhaenens, C., Jourdan, L. in Multi-Objective Nature Inspired Computing, Studies in Computational Intelligence, Vol 272, Springer, Berlin, Heidelberg, (2010).
  • [33] Jain, Y., Bahandre, S., "Min max normalization based data perturbation method for privacy protection", International Journal of Computer and Communication Technology, 3(4):45-50, (2014).
APA ERZURUM CICEK Z, Kamisli Ozturk Z (2020). A Comparative Study of Scalarization Techniques on the Multi-Objective Single Machine-Scheduling Problem Under Sequence-Dependent Setup Time, Release Date and Due Date Constraints. , 429 - 444. 10.35378/gujs.581780
Chicago ERZURUM CICEK ZEYNEP IDIL,Kamisli Ozturk Zehra A Comparative Study of Scalarization Techniques on the Multi-Objective Single Machine-Scheduling Problem Under Sequence-Dependent Setup Time, Release Date and Due Date Constraints. (2020): 429 - 444. 10.35378/gujs.581780
MLA ERZURUM CICEK ZEYNEP IDIL,Kamisli Ozturk Zehra A Comparative Study of Scalarization Techniques on the Multi-Objective Single Machine-Scheduling Problem Under Sequence-Dependent Setup Time, Release Date and Due Date Constraints. , 2020, ss.429 - 444. 10.35378/gujs.581780
AMA ERZURUM CICEK Z,Kamisli Ozturk Z A Comparative Study of Scalarization Techniques on the Multi-Objective Single Machine-Scheduling Problem Under Sequence-Dependent Setup Time, Release Date and Due Date Constraints. . 2020; 429 - 444. 10.35378/gujs.581780
Vancouver ERZURUM CICEK Z,Kamisli Ozturk Z A Comparative Study of Scalarization Techniques on the Multi-Objective Single Machine-Scheduling Problem Under Sequence-Dependent Setup Time, Release Date and Due Date Constraints. . 2020; 429 - 444. 10.35378/gujs.581780
IEEE ERZURUM CICEK Z,Kamisli Ozturk Z "A Comparative Study of Scalarization Techniques on the Multi-Objective Single Machine-Scheduling Problem Under Sequence-Dependent Setup Time, Release Date and Due Date Constraints." , ss.429 - 444, 2020. 10.35378/gujs.581780
ISNAD ERZURUM CICEK, ZEYNEP IDIL - Kamisli Ozturk, Zehra. "A Comparative Study of Scalarization Techniques on the Multi-Objective Single Machine-Scheduling Problem Under Sequence-Dependent Setup Time, Release Date and Due Date Constraints". (2020), 429-444. https://doi.org/10.35378/gujs.581780
APA ERZURUM CICEK Z, Kamisli Ozturk Z (2020). A Comparative Study of Scalarization Techniques on the Multi-Objective Single Machine-Scheduling Problem Under Sequence-Dependent Setup Time, Release Date and Due Date Constraints. Gazi University Journal of Science, 33(2), 429 - 444. 10.35378/gujs.581780
Chicago ERZURUM CICEK ZEYNEP IDIL,Kamisli Ozturk Zehra A Comparative Study of Scalarization Techniques on the Multi-Objective Single Machine-Scheduling Problem Under Sequence-Dependent Setup Time, Release Date and Due Date Constraints. Gazi University Journal of Science 33, no.2 (2020): 429 - 444. 10.35378/gujs.581780
MLA ERZURUM CICEK ZEYNEP IDIL,Kamisli Ozturk Zehra A Comparative Study of Scalarization Techniques on the Multi-Objective Single Machine-Scheduling Problem Under Sequence-Dependent Setup Time, Release Date and Due Date Constraints. Gazi University Journal of Science, vol.33, no.2, 2020, ss.429 - 444. 10.35378/gujs.581780
AMA ERZURUM CICEK Z,Kamisli Ozturk Z A Comparative Study of Scalarization Techniques on the Multi-Objective Single Machine-Scheduling Problem Under Sequence-Dependent Setup Time, Release Date and Due Date Constraints. Gazi University Journal of Science. 2020; 33(2): 429 - 444. 10.35378/gujs.581780
Vancouver ERZURUM CICEK Z,Kamisli Ozturk Z A Comparative Study of Scalarization Techniques on the Multi-Objective Single Machine-Scheduling Problem Under Sequence-Dependent Setup Time, Release Date and Due Date Constraints. Gazi University Journal of Science. 2020; 33(2): 429 - 444. 10.35378/gujs.581780
IEEE ERZURUM CICEK Z,Kamisli Ozturk Z "A Comparative Study of Scalarization Techniques on the Multi-Objective Single Machine-Scheduling Problem Under Sequence-Dependent Setup Time, Release Date and Due Date Constraints." Gazi University Journal of Science, 33, ss.429 - 444, 2020. 10.35378/gujs.581780
ISNAD ERZURUM CICEK, ZEYNEP IDIL - Kamisli Ozturk, Zehra. "A Comparative Study of Scalarization Techniques on the Multi-Objective Single Machine-Scheduling Problem Under Sequence-Dependent Setup Time, Release Date and Due Date Constraints". Gazi University Journal of Science 33/2 (2020), 429-444. https://doi.org/10.35378/gujs.581780
Sayfa Oluşturulma Tarihi
23-04-2024 14:46

İLETİŞİM

TÜBİTAK ULAKBİM TR Dizin

Yüzüncüyıl, İşçi Blokları Mahallesi

Muhsin Yazıcıoğlu Caddesi No:51/C

06530 Çankaya / ANKARA +90 (312) 298 92 00

trdizin@tubitak.gov.tr

TÜBİTAK ULAKBİM Ulusal Akademik Ağ ve Bilgi Merkezi Cahit Arf Bilgi Merkezi © Tüm Hakları Saklıdır. Gizlilik Politikası Kullanım Şartları