[go: up one dir, main page]
More Web Proxy on the site http://driver.im/ Skip to main content
Springer Nature Link
Log in

Mathematical modeling and a discrete artificial bee colony algorithm for the welding shop scheduling problem

  • Regular Research Paper
  • Published:
Memetic Computing Aims and scope Submit manuscript

Abstract

The welding process which is one of the most important assembly processes is widespread in the modern manufacturing industry, including aerospace, automotive and engineering machinery. The welding shop scheduling greatly impacts the efficiency of whole production system. However, few studies on the welding shop scheduling problem (WSSP) were reported. In this paper, a mathematical model and an improved discrete artificial bee colony algorithm (DABC) are proposed for the WSSP. Firstly, it is defined where multi-machine can process one job at the same time in the WSSP. Secondly, the mathematical models of WSSP have been constructed. Thirdly, an effective DABC is proposed to solve the WSSP, considering job permutation and machine allocation simultaneously. To improve the performance of proposed DABC algorithm, the effective operators have been designed. Three instances with different scales are used to evaluate the effectiveness of proposed algorithm. The comparisons with other two algorithms including genetic algorithm and grey wolf optimizer are also provided. Experimental results show that the proposed model and algorithm achieve good performance. Finally, the proposed model and DABC algorithm are applied in a real-world girder welding shop from a crane company in China. The results show that proposed model and algorithm reduces 55.17% production time comparing with the traditional algorithm and the scheduled machine allocation provides more reasonable arrangements for workers and machine loads.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
£29.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price includes VAT (United Kingdom)

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2
Fig. 3
Fig. 4
Fig. 5
Fig. 6
Fig. 7
Fig. 8
Fig. 9
Fig. 10
Fig. 11
Fig. 12
Fig. 13
Fig. 14
Fig. 15
Fig. 16
Fig. 17
Fig. 18

Similar content being viewed by others

Explore related subjects

Discover the latest articles, news and stories from top researchers in related subjects.

References

  1. Velazquez K, Estrada E, Gonzalez A (2014) Statistical analysis for quality welding process: an aerospace industry case study. J Appl Sci 14(19):2285–2291

    Article  Google Scholar 

  2. Li X, Lu C, Gao L, Xiao S, Wen L (2018) An effective multiobjective algorithm for energy-efficient scheduling in a real-life welding shop. IEEE T Ind Inform 14(12):5400–5409

    Article  Google Scholar 

  3. Mohammad R, Kobti Z (2012) A memetic algorithm for job shop scheduling using a critical-path-based local search heuristic. Memetic Comp 4:231–245

    Article  Google Scholar 

  4. Lu C, Gao L, Li X, Xiao S (2017) A hybrid multi-objective grey wolf optimizer for dynamic scheduling in a real-world welding industry. Eng Appl Artif Intell 57:61–79

    Article  Google Scholar 

  5. Lin Q, Gao L, Li X, Zhang C (2015) A hybrid backtracking search algorithm for permutation flow-shop scheduling problem. Comput Ind Eng 85:437–446

    Article  Google Scholar 

  6. Wang S, Liu M, Chu C (2015) A branch-and-bound algorithm for two-stage no-wait hybrid flow-shop scheduling. Int J Prod Res 53:1143–1167

    Article  Google Scholar 

  7. Pan Q, Ruiz R (2013) A comprehensive review and evaluation of permutation flowshop heuristics to minimize flowtime. Comput Oper Res 40:117–128

    Article  MathSciNet  Google Scholar 

  8. Li X, Ma S (2017) Multiobjective discrete artificial bee colony algorithm for multiobjective permutation flow shop scheduling problem with sequence dependent setup times. IEEE T Eng Manag 64(2):149–165

    Article  Google Scholar 

  9. Barkaoui M (2018) A co-evolutionary approach using information about future requests for dynamic vehicle routing problem with soft time windows. Memetic Comp 10:307–319

    Article  Google Scholar 

  10. Karaboga D (2005) An idea based on honey bee swarm for numerical optimization. Tech Rep, Comput Eng Dept, Erciyes Univ, Kayseri, Turkey, TR06

  11. Li J, Sang H, Han Y, Wang C, Gao K (2018) Efficient multi-objective optimization algorithm for hybrid flow shop scheduling problems with setup energy consumptions. J Clean Prod 181:584–598

    Article  Google Scholar 

  12. Li X, Gao L, Pan Q, Wan L, Chao K (2018) An effective hybrid genetic algorithm and variable neighborhood search for integrated process planning and scheduling in a packaging machine workshop. IEEE T Syst Man Cy-S. https://doi.org/10.1109/tsmc.2018.2881686

    Article  Google Scholar 

  13. Karaboga D, Akay B (2009) A comparative study of artificial bee colony algorithm. Appl Math Comput 24(1):108–132

    MathSciNet  MATH  Google Scholar 

  14. Tasgetiren M, Pan Q, Suganthan P, Chen A (2010) A discrete artificial bee colony algorithm for the permutation flow shop scheduling problem with total flowtime criterion. In: Proc IEEE congress on evolutionary computation, pp 1–8

  15. Bai J, Liu H (2016) Multi-objective artificial bee algorithm based on decomposition by PBI method. Appl Intell 45(4):976–991

    Article  Google Scholar 

  16. Gao K, Zhang Y, Zhang Y, Su R, Suganthan P (2018) Meta-heuristics for bi-objective urban traffic light scheduling problems. IEEE T Intell Transp. https://doi.org/10.1109/tits.2018.2868728

    Article  Google Scholar 

  17. Gao K, Suganthan P, Pan Q, Tasgetiren M, Sadollah A (2016) Artificial bee colony algorithm for scheduling and rescheduling fuzzy flexible job shop problem with new job insertion. Knowl-Based Syst 109:1–16

    Article  Google Scholar 

  18. Gao K, Suganthan P, Pan Q, Chua T, Chong C, Cai T (2016) An improved artificial bee colony algorithm for multi-objective flexible job shop scheduling problem with fuzzy processing time. Expert Syst Appl 65:52–67

    Article  Google Scholar 

  19. Gong D, Han Y, Sun J (2018) A novel hybrid multi-objective artificial bee colony algorithm for blocking lot-streaming flow shop scheduling problems. Knowl Base Syst 148:115–130

    Article  Google Scholar 

  20. Peng K, Pan Q, Gao L, Zhang B, Pang X (2018) An improved artificial bee colony algorithm for real-world hybrid flowshop rescheduling in steelmaking-refining-continuous casting process. Comput Ind Eng 122:235–250

    Article  Google Scholar 

  21. Karaboga D, Gorkemli B, Ozturk C, Karaboga N (2014) A comprehensive survey: artificial bee colony (ABC) algorithm and applications. Artif Intell Rev 42:1–37

    Article  Google Scholar 

  22. Mirjalili S, Mirjalili S, Lewis A (2014) Grey wolf optimizer. Adv Eng Softw 69:46–61

    Article  Google Scholar 

  23. Brucker P (2007) Multiprocessor tasks scheduling algorithms, 5th edn. Springer-Verlag, Berlin

    MATH  Google Scholar 

  24. Lopes M, Carvalho J (2007) A branch-and-price algorithm for scheduling parallel machines with sequence dependent setup times. Eur J Oper Res 176:1508–1527

    Article  MathSciNet  Google Scholar 

  25. Kalczynski J (2007) On the NEH heuristic for minimizing the makespan in permutation flow shops. OMEGA-Int J Manage S 35(1):53–60

    Article  Google Scholar 

  26. Tasgetiren M, Pan Q, Suganthan P, Oner A (2013) A discrete artificial bee colony algorithm for the no-idle permutation flowshop scheduling problem with the total tardiness criterion. Appl Math Model 37:6758–6779

    Article  MathSciNet  Google Scholar 

  27. Ruiz R, Stutzle T (2007) A simple and effective iterated greedy algorithm for the permutation flowshop scheduling problem. Eur J Oper Res 177:2033–2049

    Article  Google Scholar 

  28. Wang R, Purshouse R, Fleming P (2013) Preference-inspired co-evolutionary algorithms for many-objective optimization. IEEE T Evolut Comput 17:474–494

    Article  Google Scholar 

  29. Wang R, Ishibuchi H, Zhou Z, Liao T, Zhang T (2018) Localized weighted sum method for many-objective optimization. IEEE T Evolut Comput 22:3–18

    Article  Google Scholar 

  30. Li K, Wang R, Zhang T, Ishibuchi H (2018) Evolutionary many-objective optimization: a comparative study of the state-of-the-art. IEEE Access 6:26194–26214

    Article  Google Scholar 

Download references

Acknowledgements

This work was supported by the National Natural Science Foundation of China (Grant Nos. 51775216, 51435009 and 51711530038), the Natural Science Foundation of Hubei Province (Grant No. 2018CFA078) and the program for HUST Academic Frontier Youth Team (Grant No. 2017QYTD04).

Author information

Authors and Affiliations

  1. The State Key Laboratory of Digital Manufacturing Equipment and Technology, School of Mechanical Science and Engineering, Huazhong University of Science and Technology, Wuhan, 430074, China

    Xinyu Li, Shengqiang Xiao & Cuiyu Wang

  2. Department of Industrial Systems Engineering and Management, National University of Singapore, Singapore, Singapore

    Jin Yi

Authors
  1. Xinyu Li
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Shengqiang Xiao
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Cuiyu Wang
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Jin Yi
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Cuiyu Wang.

Additional information

Publisher’s Note

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

Appendix

Appendix

Instance 1 (10 × 5)

Stage 1

Stage 2

Stage 3

Stage 4

Stage 5

Setup/processing

Setup/processing

Setup/processing

Setup/processing

Setup/processing

5

9

4

5

6

24

7

5

4

12

8

13

11

14

7

28

10

7

5

18

10

17

18

22

8

33

12

8

7

24

12

20

25

31

9

35

15

10

8

29

15

25

32

40

10

40

18

12

10

35

18

30

39

49

11

45

21

14

12

41

21

36

46

58

13

51

24

16

13

47

24

40

51

63

14

56

26

18

15

52

8

12

7

8

9

27

10

8

7

15

12

17

15

18

11

32

14

11

9

22

Instance 2 (30 × 5)

Stage 1

Stage 2

Stage 3

Stage 4

Stage 5

Setup/processing

Setup/processing

Setup/processing

Setup/processing

Setup/processing

13

20

21

25

11

36

15

11

10

27

15

24

28

35

12

39

18

14

11

33

19

29

36

44

14

44

22

16

14

39

21

33

42

52

14

48

24

17

15

44

25

39

50

61

17

54

28

19

17

50

30

48

57

71

20

64

32

26

21

60

13

17

12

13

14

32

15

13

12

20

14

21

17

22

13

36

16

15

11

26

18

23

26

28

16

39

20

14

15

30

20

28

33

39

17

43

23

18

16

37

23

33

40

48

18

48

26

20

18

43

26

36

47

55

19

51

29

20

20

47

29

44

54

66

21

59

32

24

21

55

33

49

60

72

23

65

35

27

24

61

14

18

13

14

15

33

16

14

13

21

17

25

20

26

16

40

19

19

14

30

22

29

30

34

20

45

24

20

19

36

21

32

34

43

18

47

24

22

17

41

27

37

44

52

22

52

30

24

22

47

27

39

48

58

20

54

30

23

21

50

33

48

58

70

25

63

36

28

25

59

36

56

63

79

26

72

38

34

27

68

17

25

16

21

18

40

19

21

16

28

20

29

23

30

19

44

22

23

17

34

26

33

34

38

24

49

28

24

23

40

24

32

37

43

21

47

27

22

20

41

27

41

44

56

22

56

30

28

22

51

34

42

55

61

27

57

37

26

28

53

37

52

62

74

29

67

40

32

29

63

44

55

71

78

34

71

46

33

35

67

Instance 3 (60 × 5)

Stage 1

Stage 2

Stage 3

Stage 4

Stage 5

Setup/processing

Setup/processing

Setup/processing

Setup/processing

Setup/processing

5

9

4

5

6

24

7

5

4

12

8

13

11

14

7

28

10

7

5

18

10

17

18

22

8

33

12

8

7

24

12

20

25

31

9

35

15

10

8

29

15

25

32

40

10

40

18

12

10

35

18

30

39

49

11

45

21

14

12

41

21

36

46

58

13

51

24

16

13

47

24

40

51

63

14

56

26

18

15

52

9

13

8

9

10

28

11

9

8

16

11

17

14

18

10

32

13

11

8

22

13

20

21

25

11

36

15

11

10

27

15

24

28

35

12

39

18

14

11

33

19

29

36

44

14

44

22

16

14

39

21

33

42

52

14

48

24

17

15

44

25

39

50

61

17

54

28

19

17

50

30

48

57

71

20

64

32

26

21

60

13

17

12

13

14

32

15

13

12

20

14

21

17

22

13

36

16

15

11

26

18

23

26

28

16

39

20

14

15

30

20

28

33

39

17

43

23

18

16

37

23

33

40

48

18

48

26

20

18

43

26

36

47

55

19

51

29

20

20

47

29

44

54

66

21

59

32

24

21

55

33

49

60

72

23

65

35

27

24

61

14

18

13

14

15

33

16

14

13

21

17

25

20

26

16

40

19

19

14

30

22

29

30

34

20

45

24

20

19

36

21

32

34

43

18

47

24

22

17

41

27

37

44

52

22

52

30

24

22

47

27

39

48

58

20

54

30

23

21

50

33

48

58

70

25

63

36

28

25

59

36

56

63

79

26

72

38

34

27

68

17

25

16

21

18

40

19

21

16

28

20

29

23

30

19

44

22

23

17

34

26

33

34

38

24

49

28

24

23

40

24

32

37

43

21

47

27

22

20

41

27

41

44

56

22

56

30

28

22

51

34

42

55

61

27

57

37

26

28

53

37

52

62

74

29

67

40

32

29

63

44

55

71

78

34

71

46

33

35

67

25

24

24

20

26

39

27

20

24

27

23

28

26

29

22

43

25

22

20

33

30

32

38

37

28

48

32

23

27

39

32

40

45

51

29

55

35

30

28

49

30

45

47

60

25

60

33

32

25

55

38

45

59

64

31

60

41

29

32

56

36

56

61

78

28

71

39

36

28

67

42

58

69

81

32

74

44

36

33

70

29

27

28

23

30

42

31

23

28

30

32

31

35

32

31

46

34

25

29

36

34

41

42

46

32

57

36

32

31

48

30

44

43

55

27

59

33

34

26

53

39

43

56

58

34

58

42

30

34

53

36

48

57

67

29

63

39

32

30

59

39

54

64

76

31

69

42

34

31

65

45

68

72

91

35

84

47

46

36

80

26

37

25

33

27

52

28

33

25

40

36

41

39

42

35

56

38

35

33

46

31

38

39

43

29

54

33

29

28

45

40

48

53

59

37

63

43

38

36

57

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Li, X., Xiao, S., Wang, C. et al. Mathematical modeling and a discrete artificial bee colony algorithm for the welding shop scheduling problem. Memetic Comp. 11, 371–389 (2019). https://doi.org/10.1007/s12293-019-00283-4

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s12293-019-00283-4

Keywords

Search

Navigation