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

Abstract

In this paper, we considered a two-objective machine-scheduling problem under sequence-dependent setup time, release date and due date constraints. The problem is formulated as a multi-objective mixed-integer programming model. Two conflicting objectives are considered as minimization of maximum completion time (makespan) and total tardiness. Despite the most use of metaheuristics in this kind of multi-objective problems, here, we try to solve the problem by transforming the two-objectives as a single objective using scalarization techniques. Test instances are generated as proposed in the scheduling literature. The solutions are obtained using Weighted Sum Scalarization, Benson’s Method and Pascoletti−Serafini Method. In addition, a comparison of scalarization techniques using Δ performance metric is given 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 the generated test problems.

Keywords

• Machine scheduling,Sequence-dependent setup times,Scalarization,Multi-objective optimization,Sequence-dependent setup times

References

1. Pinedo M., Scheduling Theory, Algorithms, and Systems. 4th ed. New York, NY, Springer, (2008).
2. Coobineh F.F., Mohebbi E. and 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. and 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. and Soroush H., "The significance of reducing setup times/setup costst", European Journal of Operations Research, 187(3), 978-984, (2008).
5. Sioud A., Gravel M. and 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. and 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. and 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. and 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. and 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. and Chu F., "A branch and bound algorithm of the single machine schedule with sequence dependent setup times for minimizing total tardiness", Applied Mathematics and Computation, 183(1), 575-588, (2006).
11. Jacob V.V. and 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. and 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. and 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 sequence-dependent setup times and machine maintenance", Applied Soft Computing, 23, 165-179, (2014).
15. Velez-Gallego M., Maya J. and Montoya-Torres J., "A beam search heuristic for 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. and 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. and 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. Eichfelder G., "An adaptive scalarization method in multiobjective optimization", SIAM Journal on Optimization, 19(4), 1694-1718, (2009).
20. Ehrgott M. and Gandibleux X., "Approximate solution methods for multiobjective combinatorial optimization", TOP Journal, 12(1), 1-63, (2004).
21. Soleimani-damaneh M. and Zamani M., "On bensons scalarization in multi-objective optimization", Optim Lett, 10(8), 1757-1762, (2016).
22. Kasimbeyli R., Kamisli Ozturk Z., Kasimbeyli N., Yalcin G. and İcmen Erdem B., "Comparison of some scalarization methods in multiobjective optimization", Bulletin of the Malaysian Mathematical Sciences Society, (2017).
23. Gass S. and Saaty T., "The computational algorithm for the parametric objective function", Naval Research Logistics, 12(1), 1-89, (1955).
24. Benson H.P., "Existence of efficient solutions for vector maximization problems", Journal of Optimization Theory and Applications , 26(4), 569-580, (1978).
25. Gerstewitz C., "Nichtkonvexe dualitat in der vektoroptimierung", Wissensch Zeitschr, 25(3), 357-364, (1983).
26. Tan K.C., Narasimhan R., Rubin P.A. and 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).
27. 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).
28. Jiang S., Ong Y., Zhang J. and Feng L. "Consistencies and contradictions of performance metrics in multiobjective optimization", IEEE Transactions on Cybernetics, 44(12), 2391–2404, (2014).
29. Durillo J., Nebro A., Garcıa-Nieto J. and Alba E., On the Velocity Update in Multi-Objective Particle Swarm Optimizers, Editors: Coello Coello C.A., Dhaenens C. and Jourdan L. in Multi-Objective Nature Inspired Computing, Studies in Computational Intelligence, Vol 272, Springer, Berlin, Heidelberg, (2010). Deb K., Pratap A., Agrawal S. and Meyarivan T., "A fast and elitist multiobjective genetic algorithm: Nsga-II", IEEE Transactions on Evolutionary Computation, 6(2), 182-197, (2002).
30. Jain Y. and Bahandre S., "Min max normalization based data perturbation method for privacy protection", International Journal of Computer and Communication Technology, 2(8), (2011).