×

Multi-criteria scheduling: an agent-based approach for expert knowledge integration. (English) Zbl 1297.90044

Summary: In this work, we present an agent-based approach to multi-criteria combinatorial optimization. It allows to flexibly combine elementary heuristics that may be optimal for corresponding single-criterion problems.{ }We optimize an instance of the scheduling problem \(1|d_j|\sum C_j\), \(L_{\max}\) and show that the modular building block architecture of our optimization model and the distribution of acting entities enables the easy integration of problem specific expert knowledge. We present a universal mutation operator for combinatorial problem encodings that allows to construct certain solution strategies, such as advantageous sorting or known optimal sequencing procedures. In this way, it becomes possible to derive more complex heuristics from atomic local heuristics that are known to solve fractions of the complete problem. We show that we can approximate both single-criterion problems such as \(P_m|d_j|\sum U_j\) as well as more challenging multi-criteria scheduling problems, like \(P_m||C_{\max}\), \(\sum C_j\) and \(P_m|d_j|C_{\max}\), \(\sum C_j\), \(\sum U_j\). The latter problems are evaluated with extensive simulations comparing the standard multi-criteria evolutionary algorithm NSGA-2 and the new agent-based model.

MSC:

90B35 Deterministic scheduling theory in operations research
90C29 Multi-objective and goal programming
68T05 Learning and adaptive systems in artificial intelligence
90C59 Approximation methods and heuristics in mathematical programming

Software:

jMetal; SPEA2
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Bartz-Beielstein, T.; Lasarczyk, C. W. G.; Preuss, M., Sequential parameter optimization, No. 1, 773-780 (2005), New York
[2] Chen, C. L., & Bulfin, R. L. (1993). Complexity of single machine multi-criteria scheduling problems. European Journal of Operational Research, 70, 115-125. · Zbl 0795.90032 · doi:10.1016/0377-2217(93)90236-G
[3] Coello, C. A. C., Lamont, G. B., & Veldhuizen, D. A. V. (2007). Evolutionary algorithms for solving multi-objective problems. Genetic and evolutionary computation (2nd ed.). New York: Springer. · Zbl 1142.90029
[4] Conover, W. J., Johnson, M. E., & Johnson, M. M. (1981). A comparative study of tests for homogeneity of variances, with applications to the outer continental shelf bidding data. Technometrics, 4(23), 351-361. · doi:10.1080/00401706.1981.10487680
[5] Deb, K. (2001). Multi-objective optimization using evolutionary algorithms. Wiley-interscience series in systems and optimization (1st ed.). New York: Wiley.
[6] Deb, K.; Agrawal, S.; Pratab, A.; Meyarivan, T.; Schoenauer, M. (ed.); etal., A fast elitist non-dominated sorting genetic algorithm for multi-objective optimization: NSGA-II, No. 1917, 849-858 (2000), Berlin
[7] Durillo, J.; Nebro, A.; Alba, E., The jMetal framework for multi-objective optimization: design and architecture, Barcelona, Spain, Berlin
[8] Dutot, P. F.; Rzadca, K.; Saule, E.; Trystram, D., Multi-objective scheduling, 219-251 (2010), Boca Raton · Zbl 1497.90085
[9] Emmerich, M.; Beume, N.; Naujoks, B., An EMO algorithm using the hypervolume measure as selection criterion, 62-76 (2005) · Zbl 1109.68595 · doi:10.1007/978-3-540-31880-4_5
[10] Fligner, M. A., & Killeen, T. J. (1976). Distribution-free two-sample tests for scale. Journal of the American Statistical Association, 71(353), 210-213. · Zbl 0329.62035 · doi:10.1080/01621459.1976.10481517
[11] Garey, M. R., & Johnson, D. S. (1978). “Strong” NP-completeness results: motivation, examples, and implications. Journal of the ACM, 25(3), 499-508. · Zbl 0379.68035 · doi:10.1145/322077.322090
[12] Graham, R. L. (1969). Bounds on multiprocessing timing anomalies. SIAM Journal on Applied Mathematics, 17, 416-429. · Zbl 0188.23101 · doi:10.1137/0117039
[13] Graham, R. L., Lawer, E. L., Lenstra, J. K., & Kan, A. H. G. R. (1979). Optimization and approximation in deterministic sequencing and scheduling: a survey. Annals of Discrete Mathematics, 5, 287-326. · Zbl 0411.90044 · doi:10.1016/S0167-5060(08)70356-X
[14] Grimme, C.; Lepping, J., Designing multi-objective variation operators using a predator-prey approach, No. 4403, 21-35 (2007), Berlin · doi:10.1007/978-3-540-70928-2_6
[15] Grimme, C.; Lepping, J.; Papaspyrou, A.; Thierens, D. (ed.); etal., Exploring the behavior of building blocks for multi-objective variation operator design using predator-prey dynamics, 805-812 (2007), New York
[16] Hoogeveen, H. (2005). Multicriteria scheduling. European Journal of Operational Research, 167(3), 592-623. · Zbl 1154.90458 · doi:10.1016/j.ejor.2004.07.011
[17] Jackson, J. R. (1955). Scheduling a production line to minimize maximum tardiness (Management Science Research Project, Research Report 43), University of California, Los Angeles.
[18] Knowles, J., & Corne, D. (2000). Approximating the nondominated front using the Pareto archived evolution strategies. Evolutionary Computation, 8(2), 149-172. · doi:10.1162/106365600568167
[19] Knowles, J.; Corne, D., Quantifying the effects of objective space dimension in evolutionary multiobjective optimization, 757-771 (2007), Berlin · doi:10.1007/978-3-540-70928-2_57
[20] Laumanns, M.; Rudolph, G.; Schwefel, H. P.; Bäck, T. (ed.); etal., A spatial predator-prey approach to multi-objective optimization: a preliminary study, 241-249 (1998), Berlin · doi:10.1007/BFb0056867
[21] Moore, J. M. (1968). An n job, one machine sequencing algorithm for minimizing the number of late jobs. Management Science, 15, 102-109. · Zbl 0164.20002 · doi:10.1287/mnsc.15.1.102
[22] Pinedo, M. (2009). Scheduling: theory, algorithms, and systems (3rd ed.). Berlin: Springer.
[23] Schwefel, H. P. (1995). Evolution and optimum seeking (1st ed.). New York: Wiley. · Zbl 0800.92129
[24] Smith, W. E. (1956). Various optimizers for single-stage production. Naval Research Logistics Quarterly, 3, 59-66. · doi:10.1002/nav.3800030106
[25] Stein, C., & Wein, J. (1997). On the existence of schedules that are near-optimal for both makespan and total weighted completion time. Operations Research Letters, 21, 115-122. · Zbl 0888.90095 · doi:10.1016/S0167-6377(97)00025-4
[26] Süer, G. A., Báez, E., & Czajkiewicz, Z. (1993). Minimizing the number of tardy jobs in identical machine scheduling. Computers & Industrial Engineering, 25(1-4), 243-246. · doi:10.1016/0360-8352(93)90266-Z
[27] T’kindt, V., & Billaut, J. C. (2006). Multicriteria scheduling. Theory, models and algorithms (2nd ed.). Berlin: Springer. · Zbl 1014.90046
[28] van den Akker, M., & Hoogeveen, H. (2008). Minimizing the number of late jobs in a stochastic setting using a chance constraint. Journal of Scheduling, 11(1), 59-69. · Zbl 1168.90484 · doi:10.1007/s10951-007-0034-8
[29] van Wassenhove, L. N., & Gelders, F. (1980). Solving a bicriterion scheduling problem. European Journal of Operational Research, 2(4), 281-290. · Zbl 0378.90044 · doi:10.1016/0377-2217(78)90043-7
[30] Vincent, T. L., & Grantham, W. J. (1981). Optimality in parametric systems (1st ed.). New York: Wiley. · Zbl 0485.49001
[31] Zitzler, E. (1999). Evolutionary algorithms for multiobjective optimization: methods and applications. Ph.D. thesis, ETH Zürich.
[32] Zitzler, E., & Thiele, L. (1999). Multiobjective evolutionary algorithms: a comparative case study and the strength Pareto approach. IEEE Transactions on Evolutionary Computation, 3(4), 257-271. · doi:10.1109/4235.797969
[33] Zitzler, E., Laumanns, M., & Thiele, L. (2001). SPEA2: Improving the strength Pareto evolutionary algorithm (Technical Report 103). Computer Engineering and Communication Networks Lab (TIK), ETH Zürich.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.