Hybrid heuristic algorithm for multi-objective scheduling problem

doi:10.21629/JSEE.2019.02.12

Journal of Systems Engineering and Electronics ›› 2019, Vol. 30 ›› Issue (2): 327-342.doi: 10.21629/JSEE.2019.02.12

• Systems Engineering • Previous Articles Next Articles

Hybrid heuristic algorithm for multi-objective scheduling problem

Jian'gang PENG*(), Mingzhou LIU(), Xi ZHANG(), Lin LING()

School of Mechanical Engineering, Hefei University of Technology, Hefei 230009, China

Received:2017-05-08 Online:2019-04-01 Published:2019-04-28
Contact: Jian'gang PENG E-mail:jiangang@163.com;LiuMingZhou0551@163.com;isaachft@126.com;linglin8787@123.com
About author:PENG Jiangang was born in 1970. He is currently a Ph.D. and an associate research fellow at School of Mechanical Engineering in Hefei University of Technology, China. His main research interests include production planning and scheduling, quality function deployment, decision-making analysis, fuzzy theory and multi-objective optimization algorithm. E-mail:peng jiangang@163.com|LIU Mingzhou was born in 1968. He is currently a professor and a Ph.D. candidate supervisor in manufacturing process monitoring and control at School of Mechanical Engineering in Hefei University of Technology, China. His main research interests include theory, analysis & decision method of industrial engineering system, monitoring and control of manufacturing process, modeling and simulation of manufacturing system, modern integrated manufacturing system, facilities planning and logistics engineering and computer integrated manufacturing system. E-mail:LiuMingZhou0551@163.com|ZHANG Xi was born in 1985. He received his Ph.D. degree at School of Mechanical Engineering in 2015, Hefei University of Technology, China. His main research interests include production scheduling and intelligent manufacturing, uncertainty and multi-objective optimization. E-mail:isaachft@126.com|LING Lin was born in 1987. She received her Ph.D. degree from Hefei University of Technology in 2014. She works in Hefei University of Technology from 2014. Her research interests include material flow control and intelligent manufacturing system. E-mail:linglin8787@123.com
Supported by:
the National Key Research and Development Program of China(2016YFD0700605);the Fundamental Research Funds for the Central Universities(JZ2016HGBZ1035);the Anhui University Natural Science Research Project(KJ2017A891);This work was supported by the National Key Research and Development Program of China (2016YFD0700605), the Fundamental Research Funds for the Central Universities (JZ2016HGBZ1035), and the Anhui University Natural Science Research Project (KJ2017A891)

Abstract

Abstract:

This research provides academic and practical contributions. From a theoretical standpoint, a hybrid harmony search (HS) algorithm, namely the oppositional global-based HS (OGHS), is proposed for solving the multi-objective flexible job-shop scheduling problems (MOFJSPs) to minimize makespan, total machine workload and critical machine workload. An initialization program embedded in opposition-based learning (OBL) is developed for enabling the individuals to scatter in a well-distributed manner in the initial harmony memory (HM). In addition, the recursive halving technique based on opposite number is employed for shrinking the neighbourhood space in the searching phase of the OGHS. From a practice-related standpoint, a type of dual vector code technique is introduced for allowing the OGHS algorithm to adapt the discrete nature of the MOFJSP. Two practical techniques, namely Pareto optimality and technique for order preference by similarity to an ideal solution (TOPSIS), are implemented for solving the MOFJSP. Furthermore, the algorithm performance is tested by using different strategies, including OBL and recursive halving, and the OGHS is compared with existing algorithms in the latest studies. Experimental results on representative examples validate the performance of the proposed algorithm for solving the MOFJSP.

Key words: flexible job-shop scheduling, harmony search (HS) algorithm, Pareto optimality, opposition-based learning

Jian'gang PENG, Mingzhou LIU, Xi ZHANG, Lin LING. Hybrid heuristic algorithm for multi-objective scheduling problem[J]. Journal of Systems Engineering and Electronics, 2019, 30(2): 327-342.

Figures/Tables 18

Table 1

Fig 1

Fig 2

Fig 3

Fig 4

Fig 5

Table 2

Table 3

Fig 6

Fig 7

Fig 8

Fig 9

Fig 10

Table 4

Table 5

Table 6

Table 7

Table 8

Most appropriate scheduling scheme for problem 20$\times $10 presented by Brandimarte $\mathit{{(f_{1} = 346, }}$ $\mathit{{f_{2} = 226\; 0, }}$ $\mathit{{f_{3} = 342)}}$"

	Operation	$M_k(t_{i, j}, tf_{i, j})$
$i = 1$	$O_{i1}\sim O_{i7}$	M2(87, 97)	M8(99, 116)	M8(116, 130)	M1(131, 141)	M10(142, 160)	M9(160, 166)	M7(166, 175)
$i = 1$	$O_{i8}\sim O_{i14}$	M1(196, 203)	M9(203, 214)	M4(290, 306)	M2(316, 321)	M4(322, 328)	-	-
$i = 2$	$O_{i1}\sim O_{i7}$	M8(0, 17)	M5(17, 23)	M2(57, 67)	M5(74, 83)	M3(122, 133)	M1(141, 149)	M7(149, 154)
$i = 2$	$O_{i8}\sim O_{i14}$	M1(168, 175)	M7(201, 210)	M1(271, 281)	M3(281, 292)	M4(306, 322)	M5(322, 330)	-
$i = 3$	$O_{i1}\sim O_{i7}$	M7(0, 5)	M5(8, 17)	M10(44, 62)	M1(79, 90)	M4(90, 96)	M4(96, 112)	M1(161, 168)
$i = 3$	$O_{i8}\sim O_{i14}$	M1(203, 213)	M5(213, 219)	M3(223, 234)	M3(234, 248)	-	-	-
$i = 4$	$O_{i1}\sim O_{i7}$	M1(26, 34)	M1(34, 41)	M1(41, 47)	M8(130, 144)	M4(144, 160)	M8(175, 192)	M4(197, 204)
$i = 4$	$O_{i8}\sim O_{i14}$	M5(204, 209)	M3(209, 223)	M7(223, 232)	M1(281, 291)	-	-	-
$i = 5$	$O_{i1}\sim O_{i7}$	M8(17, 34)	M4(34, 50)	M5(56, 65)	M10(65, 71)	M4(160, 167)	M2(173, 189)	M7(189, 194)
$i = 5$	$O_{i8}\sim O_{i14}$	M8(209, 223)	M5(223, 229)	M10(229, 239)	M4(239, 245)	M5(245, 254)	M1(291, 299)	M1(307, 314)
$i = 6$	$O_{i1}\sim O_{i7}$	M2(0, 5)	M10(6, 24)	M1(63, 73)	M3(94, 108)	M5(108, 117)	M7(125, 134)	M8(192, 209)
$i = 6$	$O_{i8}\sim O_{i14}$	M8(223, 237)	M2(237, 242)	M7(242, 247)	M1(247, 253)	-	-	-
$i = 7$	$O_{i1}\sim O_{i7}$	M8(34, 48)	M8(48, 65)	M5(65, 74)	M4(74, 90)	M1(106, 116)	M2(125, 130)	M2(135, 140)
$i = 7$	$O_{i8}\sim O_{i14}$	M5(149, 155)	M4(211, 217)	M1(223, 229)	M2(229, 237)	M7(237, 242)	M4(276, 283)	M10(283, 301)
$i = 8$	$O_{i1}\sim O_{i7}$	M1(0, 10)	M10(24, 30)	M5(38, 47)	M7(66, 75)	M9(75, 86)	M2(130, 135)	M7(154, 159)
$i = 8$	$O_{i8}\sim O_{i14}$	M2(159, 164)	M2(164, 172)	M4(217, 223)	M2(267, 277)	M3(292, 303)	M5(306, 312)	-
$i = 9$	$O_{i1}\sim O_{i7}$	M8(65, 82)	M2(82, 87)	M1(90, 100)	M4(112, 128)	M5(128, 134)	M7(134, 143)	M2(145, 153)
$i = 9$	$O_{i8}\sim O_{i14}$	M9(166, 177)	M9(177, 183)	M2(209, 219)	M5(254, 263)	-	-	-
$i = 10$	$O_{i1}\sim O_{i7}$	M4(0, 16)	M1(73, 79)	M3(80, 94)	M2(105, 110)	M9(110, 121)	M9(128, 137)	M5(143, 149)
$i = 10$	$O_{i8}\sim O_{i14}$	M4(204, 211)	M2(219, 229)	M3(270, 281)	M1(314, 322)	M1(322, 332)	-	-
$i = 11$	$O_{i1}\sim O_{i7}$	M9(0, 11)	M5(23, 32)	M2(97, 105)	M4(128, 144)	M1(149, 155)	M5(155, 164)	M3(164, 174)
$i = 11$	$O_{i8}\sim O_{i14}$	M3(185, 199)	M1(237, 247)	M4(247, 254)	-	-	-	-
$i = 12$	$O_{i1}\sim O_{i7}$	M10(0, 6)	M1(10, 16)	M4(50, 66)	M9(66, 72)	M7(75, 80)	M7(80, 89)	M2(140, 145)
$i = 12$	$O_{i8}\sim O_{i14}$	M8(254, 268)	M4(270, 276)	M5(286, 292)	M2(292, 308)	-	-	-
$i = 13$	$O_{i1}\sim O_{i7}$	M2(5, 10)	M3(14, 28)	M9(37, 43)	M5(47, 56)	M2(120, 125)	M4(167, 174)	M1(175, 186)
$i = 13$	$O_{i8}\sim O_{i14}$	M8(237, 254)	M1(254, 261)	M1(261, 271)	M7(271, 280)	-	-	-
$i = 14$	$O_{i1}\sim O_{i7}$	M5(0, 8)	M1(16, 26)	M2(26, 42)	M2(110, 120)	M7(120, 125)	M1(125, 131)	M4(174, 190)
$i = 14$	$O_{i8}\sim O_{i14}$	M4(190, 197)	M7(210, 219)	M3(248, 259)	-	-	-	-
$i = 15$	$O_{i1}\sim O_{i7}$	M1(47, 57)	M1(57, 63)	M2(67, 72)	M2(72, 80)	M5(83, 89)	M9(89, 95)	M2(153, 158)
$i = 15$	$O_{i8}\sim O_{i14}$	M5(164, 169)	M4(223, 239)	M3(259, 270)	M2(277, 287)	M7(287, 292)	-	-
$i = 16$	$O_{i1}\sim O_{i7}$	M8(82, 99)	M1(100, 106)	M3(108, 122)	M9(122, 128)	M8(161, 175)	M7(175, 180)	M7(180, 189)
$i = 16$	$O_{i8}\sim O_{i14}$	M2(189, 194)	M1(229, 237)	M2(242, 252)	M4(254, 270)	M5(270, 278)	M1(332, 339)	M5(339, 344)
$i = 17$	$O_{i1}\sim O_{i7}$	M2(18, 26)	M9(26, 37)	M7(37, 46)	M8(144, 161)	M10(161, 167)	M5(169, 175)	M1(186, 196)
$i = 17$	$O_{i8}\sim O_{i14}$	M7(196, 201)	M2(252, 262)	M10(262, 280)	M4(283, 290)	M3(303, 317)	M1(339, 346)	-
$i = 18$	$O_{i1}\sim O_{i7}$	M2(10, 18)	M4(23, 29)	M5(32, 38)	M10(38, 44)	M3(44, 58)	M5(95, 103)	M9(137, 148)
$i = 18$	$O_{i8}\sim O_{i14}$	M2(194, 204)	M2(262, 267)	M8(285, 299)	M1(299, 307)	-	-	-
$i = 19$	$O_{i1}\sim O_{i7}$	M3(0, 14)	M2(42, 52)	M7(52, 61)	M10(71, 89)	M3(133, 144)	M1(155, 161)	M3(174, 185)
$i = 19$	$O_{i8}\sim O_{i14}$	M2(204, 209)	M5(229, 234)	M5(234, 243)	M2(287, 292)	M5(292, 297)	M5(297, 306)	-
$i = 20$	$O_{i1}\sim O_{i7}$	M4(16, 23)	M2(52, 57)	M7(61, 66)	M3(66, 80)	M5(89, 95)	M1(116, 122)	M5(134, 143)
$i = 20$	$O_{i8}\sim O_{i14}$	M1(213, 223)	M8(268, 285)	M9(285, 291)	M2(308, 316)	M3(317, 328)	M2(328, 344)	-

Table 8

References 63

1	ZUO Y, GU H Y, XI Y G. Modified bottleneck-based heuristic for large-scale job-shop scheduling problems with a single bottleneck. Journal of Systems Engineering and Electronics, 2007, 18 (3): 556- 565. doi: 10.1016/S1004-4132(07)60129-7
2	LI K, YANG S L. Heuristic algorithms for scheduling on uniform parallel machines with heads and tails. Journal of Systems Engineering and Electronics, 2011, 22 (3): 462- 467. doi: 10.3969/j.issn.1004-4132.2011.03.014
3	SAIDI M M, FATTAHI P. Flexible job shop scheduling with tabu search algorithms. International Journal of Advanced Manufacturing Technology, 2007, 32 (5-6): 563- 570. doi: 10.1007/s00170-005-0375-4
4	SHEN L, DAUZÈRE-PÉRÈS S, NEUFELD J S. Solving the flexible job shop scheduling problem with sequence-dependent setup times. European Journal of Operational Research, 2018, 265 (2): 503- 516.
5	LIU Q, CHEKEM F O, ZHAN M, et al. A hybrid fruit fly algorithm for solving flexible job-shop scheduling to reduce manufacturing carbon footprint. Journal of Cleaner Production, 2017, 168, 668- 678. doi: 10.1016/j.jclepro.2017.09.037
6	GAREY M R, JOHNSON D S, SETHI R. The complexity of flow-shop and job-shop scheduling. Mathematics of Operations Research, 1976, 1 (2): 117- 129.
7	BRUCKER P, SCHLIE R. Job-shop scheduling with multipurpose machines. Computing, 1990, 45 (4): 369- 375.
8	BRANDIMARTE P. Routing and scheduling in a flexible jobshop by taboo search. Annals of Operations Research, 1993, 41 (3): 157- 183. doi: 10.1007/BF02023073
9	SEYED H A R, ZANDIEH M. A new biogeography-based optimization (BBO) algorithm for the flexible job shop scheduling problem. International Journal of Advanced Manufacturing Technology, 2012, 58 (9-12): 1115- 1129. doi: 10.1007/s00170-011-3437-9
10	ISHIKAWA S, KUBOTA R, HORIO K. Effective hierarchical optimization by a hierarchical multi-space competitive genetic algorithm for the flexible job-shop scheduling problem. Expert Systems with Applications, 2015, 42 (24): 9434- 9440. doi: 10.1016/j.eswa.2015.08.003
11	YUAN Y, XU H, YANG J D. A hybrid harmony search algorithm for the flexible job shop scheduling problem. Applied Soft Computing, 2013, 13 (7): 3259- 3272. doi: 10.1016/j.asoc.2013.02.013
12	SINGH M R, MAHAPATRA S S. A quantum behaved particle swarm optimization for flexible job shop scheduling. Computers & Industrial Engineering, 2016, 93, 36- 44.
13	MATI Y, REZG N, XIE X L. An integrated greedy heuristic for a flexible job shop scheduling problem. Proc. of the IEEE International Conference on Systems, Man, and Cybernetics, 2001, 2534- 2539.
14	LIU A J, MICHELE P, JOHN F. Scheduling optimization of task allocation in integrated manufacturing system based on task decomposition. Journal of Systems Engineering and Electronics, 2016, 27 (2): 422- 433. doi: 10.1109/JSEE.2016.00043
15	NOUIRI M, BEKRAR A, JEMAI A, et al. An effective and distributed partical swarm optimization algorithm for flexible job-shop scheduling problem. Journal of Intelligent Manufacturing, 2018, 29 (3): 603- 615. doi: 10.1007/s10845-015-1039-3
16	SHEN X N, HAN Y, FU J Z. Robustness measures and robust scheduling for multi-objective stochastic flexible job shop scheduling problems. Soft Computing, 2017, 21 (21): 6531- 6554. doi: 10.1007/s00500-016-2245-4
17	ZHANG Y, WANG J, LIU Y. Game theory based real-time multi-objective flexible job shop scheduling considering environmental impact. Journal of Cleaner Production, 2017, 167 (20): 665- 679.
18	ZITZLER E, THIELE L. Multi-objective evolutionary:a comparative case study and the strength Pareto approach. IEEE Trans. on Evolutionary Computation, 1999, 3 (4): 257- 271. doi: 10.1109/4235.797969
19	CORNE D W, JERRAM N R, KNOWLES J D, et al. PESAII:region-based selection in evolutionary multi-objective optimization. Proc. of the 3rd Annual Conference on Genetic and Evolutionary Computation, 2001, 283- 290.
20	SRINIVAS N, DED K. Multi-objective optimization using non-dominated sorting genetic algorithm. Evolutionary Computation, 1994, 2 (3): 221- 248. doi: 10.1162/evco.1994.2.3.221
21	DEB K, PRATAP A, AGARWAL S, et al. A fast and elitist multi-objective genetic algorithms:NSGA-Ⅱ. IEEE Trans. on Evolutionary Computation, 2002, 6 (2): 182- 197.
22	LI J Q, PAN Q K, XIE S X. A hybrid variable neighborhood search algorithm for solving multi-objective flexible job shop problems. Computer Science and Information Systems, 2010, 7 (4): 907- 930. doi: 10.2298/CSIS090608017L
23	RAHMATI S H A, ZANDIEH M, YAZDANI M. Developing two multi-objective evolutionary algorithms for the multiobjective flexible job shop scheduling problem. International Journal of Advanced Manufacturing Technology, 2013, 64 (5-8): 915- 932. doi: 10.1007/s00170-012-4051-1
24	WANG X J, LI W F, ZHANG Y. An improved multi-objective genetic algorithm for fuzzy flexible job-shop scheduling problem. International Journal of Computer Applications in Technology, 2013, 47 (2-3): 280- 288.
25	ROHANINEJAD M, KHEIRKHAH A. A hybrid multiobjective genetic algorithm based on the ELECTRE method for a capacitated flexible job shop scheduling problem. International Journal of Advanced Manufacturing Technology, 2015, 77 (1-4): 51- 66. doi: 10.1007/s00170-014-6415-1
26	JIA S, HU Z. Path-relinking tabu search for the multi-objective flexible job shop scheduling problem. Computers & Operations Research, 2014, 47 (9): 11- 26.
27	ZHANG G H, SHAO X Y, LI G, et al. An effective hybrid particle swarm optimization algorithm for multi-objective flexible job-shop scheduling problem. Computers & Industrial Engineering, 2009, 56 (4): 1309- 1318.
28	VILCOT G, BILLAUT J C. A tabu search algorithm for solving a multicriteria flexible job shop scheduling problem. International Journal of Production Research, 2011, 49 (23): 6963- 6980. doi: 10.1080/00207543.2010.526016
29	LI J Q, PAN Q K, SUGANTHAN P N, et al. A hybrid tabu search algorithm with an efficient neighborhood structure for the flexible job shop scheduling problem. International Journal of Advanced Manufacturing Technology, 2011, 52 (5-8): 683- 697. doi: 10.1007/s00170-010-2743-y
30	KAPLANOGLU V. An object-oriented approach for multiobjective flexible job-shop scheduling problem. Expert System with Applications, 2016, 45 (1): 71- 84.
31	XIA W J, WU Z M. An effective hybrid optimization approach for multi-objective flexible job-shop scheduling problems. Computers & Industrial Engineering, 2005, 48 (2): 409- 425.
32	LOW C YY, YIP Y, WU T H. Modeling and heuristics of FMS scheduling with multiple objectives. Computers & Operations Research, 2006, 33 (3): 674- 694.
33	GAO K Z, SUGANTHAN P N, PAN Q K, et al. Paretobased grouping discrete harmony search algorithm for multiobjective flexible job shop scheduling. Information Sciences, 2014, 289 (24): 76- 90.
34	TAN K C, CHIAMS S C, MAMUN A A, et al. Balancing exploration and exploitation with adaptive variation for evolutionary multi-objective optimization. European Journal of Operational Research, 2009, 197 (2): 701- 713.
35	KACEM I, HAMMADI S, BORNE P. Approach by localization and multi-objective evolutionary optimization for flexible job-shop scheduling problems. IEEE Trans. on Systems, Man and Cybernetics, 2002, 32 (l): l- 13.
36	ALTANNAR C, PANOS M, PARDALOS. A survey of recent developments in multi-objective optimization. Annals of Operations Research, 2007, 154 (1): 29- 50. doi: 10.1007/s10479-007-0186-0
37	BAUMGARTNER U, MAGELE C, RENHART W. Pareto optimality and particle swarm optimization. IEEE Trans. on Magnetics, 2004, 40 (2): 1172- 1175. doi: 10.1109/TMAG.2004.825430
38	PARETO V. Manual of political economy. SCHWIER A S Trans. New York: Anguitus M. Kelly, 1971.
39	KONAK A, COIT D W, SMITH A E. Multi-objective optimization using genetic algorithms:a tutoria. Reliability Engineering and System Safety, 2006, 91 (9): 992- 1007. doi: 10.1016/j.ress.2005.11.018
40	GEEM Z W, KIM J H, LOGANATHAN G V. A new heuristic optimization algorithm:harmony search. Simulation, 2001, 76 (2): 60- 68.
41	LEE K S, GEEM Z W. A new meta-heuristic algorithm for continuous engineering optimization:harmony search theory and practice. Computer Methods in Applied Methanics and Engineering, 2005, 194 (36-38): 3902- 3933. doi: 10.1016/j.cma.2004.09.007
42	MAHDAVI M, FESANGHARY M, DAMANGIR E. An improved harmony search algorithm for solving optimization problems. Applied Mathematics and Computation, 2007, 188 (2): 1567- 1579.
43	MAHAMED G H O, MEHRDAD M. Global-best harmony search. Applied Mathematics and Computation, 2008, 198 (2): 643- 656.
44	TIZHOOSH H R. Opposition-based learning:a new scheme for machine intelligence. Proc. of the International Conference on Computational Intelligence for Modeling, Control and Automation, and International Conference on Intelligent Agents, Web Technologies and Internet Commerce, 2005, 1, 695- 701.
45	WANG H, LIU Y, ZENG S Y, et al. Opposition-based particle swarm algorithm with Cauchy mutation. Proc. of the IEEE Congress on Evolutionary Computation, 2007, 4750- 4756.
46	SHAHZAD F, BAIG A R, MASOOD S, et al. Oppositionbased particle swarm optimization with velocity clamping. Advances in computational intelligence. Berlin, Heidelberg: Springer, 2009, 61: 339-348.
47	RAHNAMAYAN S, TIZHOOSH H R, SALAM M. Opposition-based differential evolution. IEEE Trans. on Evolutionary Computation, 2008, 12 (1): 64- 79. doi: 10.1109/TEVC.2007.894200
48	ERGEZER M, SIMON D, DU D. Oppositional biogeographybased optimization. Proc. of the IEEE International Conference on Systems, Man and Cybernetics, 2009, 1009- 1014.
49	ERGEZER M, SIMON D. Oppositional biogeography-based optimization for combinatorial problems. Proc. of the IEEE Congress on Evolutionary Computation, 2011, 1496- 1503.
50	GEN M, TSUJIMURA Y, KUBOTA E. Solving job-shop scheduling problem using genetic algorithms. Proc. of the 16th International Conference on Computer and Industrial Engineering, 1994, 576- 579.
51	BEAN J C. Genetic algorithms and random keys for sequencing and optimization. ORSA Journal on Computing, 1994, 6 (2): 154- 160.
52	OUYANG H B, GAO L Q, ZOU D X, et al. Exploration ability study of harmony search algorithm and its modification. Control Theory & Applications, 2014, 31 (1): 57- 65.
53	TAN K C, YANG Y J, GOH C K. A distributed cooperative coevolutionary algorithm for multi-objective optimization. IEEE Trans. on Evolutionary Computation, 2006, 10 (5): 527- 549. doi: 10.1109/TEVC.2005.860762
54	DEB K, THIELE L, LAUMANNS M, et al. Scalable multiobjective optimization test problems. Proc. of the Congress on Evolutionary Computation, 2002, 825- 830.
55	LI H, ZHANG Q F. Multi-objective optimization problems with complicated Pareto sets, MOEA/D and NSGA-Ⅱ. IEEE Trans. on Evolutionary Computation, 2009, 13 (2): 284- 302.
56	KACEM I, HAMMADI S, BORNE P. Pareto-optimality approach for flexible job-shop scheduling problems:hybridization of evolutionary algorithms and fuzzy logic. Mathematics and Computers in Simulation, 2002, 60 (3-5): 245- 276. doi: 10.1016/S0378-4754(02)00019-8
57	BAGHERI A, ZANDIEH M, MAHDAVI I, et al. An artificial immune algorithm for the flexible job-shop scheduling problem. Future Generation Computer Systems, 2010, 26 (4): 533- 541. doi: 10.1016/j.future.2009.10.004
58	WANG X J, GAO L, ZHANG C Y, et al. A multi-objective genetic algorithm based on immune and entropy principle for flexible job-shop scheduling problem. International Journal of Advanced Manufacturing Technology, 2010, 51 (5-8): 757- 767. doi: 10.1007/s00170-010-2642-2
59	LI J Q, PAN Q K, GAO K Z. Pareto-based discrete artificial bee colony algorithm for multi-objective flexible job shop scheduling problems. International Journal of Advanced Manufacturing Technology, 2011, 55 (9-12): 1159- 1169. doi: 10.1007/s00170-010-3140-2
60	OPRICOVIC S, TZENG G H. Compromise solution by MCDM methods:a comparative analysis of VIKOR and TOPSIS. European Journal of Operational Research, 2004, 156 (2): 445- 455.
61	HWANG C L, YOON K. Multiple attribute decision making. Berlin: Springer-Verlag, 1981.
62	SHEN F, MA X, LI Z, et al. An extended intuitionistic fuzzy TOPSIS method based on a new distance measure with an application to credit risk evaluation. Information Sciences, 2018, 428, 105- 119. doi: 10.1016/j.ins.2017.10.045
63	SILVIA C, ANTONELLA C, JOAQUÍN I, et al. K-out-of-n systems:an exact formula for the stationary availability and multi-objective configuration design based on mathematical programming and TOPSIS. Journal of Computational and Applied Mathematics, 2018, 330 (1): 1007- 1015.

Job	Operation	$M_{1}$	$M_{2}$	$M_{3}$
$J_{1}$	$O_{11}$	3	-	2
	$O_{12}$	5	2	3
	$O_{13}$	-	2	4
$J_{2}$	$O_{21}$	4	5	3
$J_{2}$	$O_{22}$	7	-	9
$J_{3}$	$O_{31}$	4	2	1
	$O_{32}$	-	5	3
	$O_{33}$	4	-	5

Problem	Algorithm	Time/s
Problem	Algorithm	1	2	3	Average
DTLZ1	HS	11.370 1	11.504 6	10.928 2	11.267 6
	HS+OBL	11.733 0	11.669 0	11.797 5	11.733 2
	OGHS	11.080 0	11.153 3	11.064 3	11.099 2
DTLZ2	HS	11.142 2	11.116 9	10.970 5	11.076 5
	HS+OBL	11.031 8	10.966 2	11.100 8	11.032 9
	OGHS	11.186 1	11.055 9	11.323 1	11.188 4
DTLZ3	HS	11.059 4	10.894 9	11.180 0	11.044 8
	HS+OBL	11.127 5	11.278 7	10.986 8	11.131 0
	OGHS	11.275 6	10.867 7	11.225 6	11.123 0
DTLZ4	HS	11.226 3	10.967 8	10.802 0	10.998 7
	HS+OBL	11.054 1	11.339 2	10.878 1	11.090 5
	OGHS	11.187 7	11.312 8	11.200 1	11.233 5
DTLZ7	HS	11.864 5	10.802 2	11.920 9	11.529 2
	HS+OBL	11.348 2	11.101 3	12.288 2	11.579 2
	OGHS	10.903 1	11.395 0	11.062 1	11.120 1

Problem	Algorithm	GD
Problem	Algorithm	1	2	3	Average
DTLZ1	HS	0.018 3	0.014 0	0.007 8	0.013 4
	HS+OBL	0.013 3	0.014 4	0.007 8	0.011 8
	OGHS	0.009 7	0.010 0	0.008 9	0.009 5
DTLZ2	HS	0.017 1	0.017 0	0.018 1	0.017 4
	HS+OBL	0.015 4	0.014 9	0.017 8	0.016 0
	OGHS	0.015 7	0.016 4	0.016 3	0.016 1
DTLZ3	HS	0.021 7	0.060 7	0.081 1	0.054 5
	HS+OBL	0.018 6	0.022 7	0.021 5	0.020 9
	OGHS	0.019 3	0.021 3	0.020 3	0.020 3
DTLZ4	HS	0.101 5	0.051 1	0.078 7	0.077 1
	HS+OBL	0.075 0	0.058 3	0.061 7	0.065 0
	OGHS	0.055 0	0.059 7	0.052 2	0.055 6
DTLZ7	HS	0.043 4	0.064 3	0.050 2	0.052 6
	HS+OBL	0.023 7	0.056 5	0.052 3	0.044 2
	OGHS	0.021 6	0.033 1	0.035 6	0.030 1

Problem	Algorithm	Value	Generation
Problem	Algorithm	Value	100	500	3 000
DTLZ1	HS	Mean	0.109 6	0.060 4	0.056 0
	HS	Variance	0.001 9	0.000 5	0.001 5
	HS+OBL	Mean	0.084 0	0.060 8	0.047 7
	HS+OBL	Variance	0.001 1	0.000 5	0.000 7
	OGHS	Mean	0.088 5	0.060 8	0.034 7
	OGHS	Variance	0.001 0	0.000 7	0.000 5
DTLZ2	HS	Mean	0.123 9	0.099 5	0.091 3
	HS	Variance	0.007 1	0.002 7	0.003 1
	HS+OBL	Mean	0.111 4	0.097 9	0.096 2
	HS+OBL	Variance	0.006 1	0.003 0	0.002 8
	OGHS	Mean	0.104 3	0.091 3	0.091 6
	OGHS	Variance	0.003 4	0.002 5	0.002 3
DTLZ3	HS	Mean	0.366 5	0.238 9	0.119 0
	HS	Variance	0.026 8	0.008 4	0.004 6
	HS+OBL	Mean	0.184 2	0.148 4	0.105 9
	HS+OBL	Variance	0.007 4	0.005 3	0.004 2
	OGHS	Mean	0.148 5	0.103 3	0.097 1
	OGHS	Variance	0.004 0	0.002 9	0.002 9
DTLZ4	HS	Mean	0.083 4	0.053 5	0.049 5
	HS	Variance	0.020 0	0.005 9	0.005 4
	HS+OBL	Mean	0.068 2	0.052 4	0.048 4
	HS+OBL	Variance	0.009 3	0.004 6	0.003 2
	OGHS	Mean	0.063 1	0.049 9	0.040 1
	OGHS	Variance	0.010 0	0.006 1	0.002 6
DTLZ7	HS	Mean	1.413 9	1.048 6	0.249 3
	HS	Variance	0.091 0	0.112 5	0.010 9
	HS+OBL	Mean	0.900 9	0.636 0	0.253 7
	HS+OBL	Variance	0.083 6	0.063 6	0.008 5
	OGHS	Mean	0.662 0	0.508 8	0.223 6
	OGHS	Variance	0.038 1	0.033 2	0.005 8

Brandimarte problem		AIA	P-DABC										OGHS
Brandimarte problem		AIA	P-DABC										1	2	3	4	5
20$\times $10	$f_{1}$	312	311	313	319	324	411	417	424	431	474	484	346	453	463	466	479
	$f_{2}$	2 591	2 288	2 286	2 280	2 279	2 265	2 253	2 240	2 230	2 223	2 210	2 260	2 215	2 214	2 212	2 210
	$f_{3}$	306	299	311	307	307	349	360	386	402	444	454	342	412	422	438	454

Hybrid heuristic algorithm for multi-objective scheduling problem

RichHTML

PDF (PC)

Knowledge

Abstract

Cite this article

Share this article

Figures/Tables 18

References 63

Related Articles 0

Recommended Articles

Metrics

Comments

Kacem problem		Algorithm
Kacem problem		PSO+SA	AIA	MOGA				P-DABC			OGHS
10$\times $10	$f_{1}$	7	7	8	7	8	7	8	7	8	7	8	7
	$f_{2}$	44	43	42	42	41	45	41	43	42	42	41	43
	$f_{3}$	6	5	5	6	7	5	7	5	5	6	7	5
15$\times $10	$f_{1}$	12	11	11	12	11	–	12	11	–	11	11	–
	$f_{2}$	91	93	91	95	98	–	91	93	–	94	91	–
	$f_{3}$	11	11	11	10	10	–	11	11	–	10	11	–

	Makespan	Total workload	Critical machine workload
Makespan	1.000 0	0.250 0	0.166 7
Total workload	4.000 0	1.000 0	0.333 3
Critical machine workload	6.000 0	3.000 0	1.000 0