A human–machine interaction approach of block erection schedule with three-dimensional spatial constraints

Abstract

When the spatial constraints are taken into account, the problem about dispatch and optimization of block erection in shipbuilding becomes more complicated. A human–machine interaction approach is proposed and extended to quickly find an approximate optimal solution. First, a steer genetic algorithm enables users to guide the computing to an effective iterative direction and leverages the computing. The model of block erection dispatch to the crane is a parallel machine scheduling problem with spatial constraints. The genetic crossover operators can be guided according to the activities of block erection in shipbuilding. Two criteria are presented to justify the effectiveness of the proposed algorithm and a fitness function is given to represent the makespan. Moreover, three-dimensional spatial constraints, which affect the parallel machine scheduling problem heavily, are visualized. A better erection path can be obtained dynamically, when the users are in an immersive environment. Finally, a three-dimensional layout prototype system of block erection is developed with real size, embedded with an interactive genetic algorithm optimization to solve this problem with the objective of minimizing makespan.

Keywords

human–machine interaction genetic algorithm scheduling parallel machines shipbuilding

Get full access to this article

View all access options for this article.

References

Aho

Mäkinen

(2006) On a parallel machine scheduling problem with precedence constraints. Journal of Scheduling 9(5): 493–495.

Alcan

Başlıgil

(2011) An application with non-identical parallel machines using genetic algorithm with the help of fuzzy logic. Proceedings of the World Congress on Engineering 45(1): 272–280.

Bao

Wang

(2014) A steerable GA method for block erection of shipbuilding in virtual environment. Lecture Notes in Computer Science 8683: 286–293.

Caprace

Petcu

Velarde

. (2013) Optimization of shipyard space allocation and scheduling using heuristic algorithm. Journals of Marine Science and Technology 18(3): 404–417.

Chekuri

Motwani

Natarajan

. (2001) Approximation techniques for average completion time scheduling. SIAM Journal on Computing 31(1): 146–166.

Gasior

Seredynski

(2013) Multi-objective parallel machines scheduling for fault-tolerant cloud systems. In: Kołodziej

Di Martino

Talia

. (eds) Algorithms and Architectures for Parallel Processing: Part 1. Cham: Springer, pp. 247–256.

Herrmann

Proth

Sauer

(1997) Heuristics for unrelated machine scheduling with precedence constraints. European Journal of Operational Research 102(3): 528–537.

Joo

Kim

(2014) Block transportation scheduling under delivery restriction in shipyard using meta-heuristic algorithms. Expert Systems with Applications 41(6): 2851–2858.

Klau

Lesh

Marks

. (2002) The HuGS platform: a toolkit for interactive optimization. In:Proceedings of the working conference on advanced visual interfaces, pp. 324–330. Available at: https://www.eecs.harvard.edu/~michaelm/postscripts/avi2002.pdf

10.

Klau

Lesh

Marks

. (2010) Human-guided search. Journal of Heuristics 16(3): 289–310.

11.

Lee

Park

. (1997) Developing scheduling systems for Daewoo shipbuilding: DAS project. European Journal of Operational Research 97(2): 380–395.

12.

Zhao

(2014) An integrated change propagation scheduling approach for product design. Concurrent Engineering 22(4): 347–360.

13.

Jian

Yan

. (2009) Aircraft tooling collaborative design based on multi-agent and PDM. Concurrent Engineering 17(2): 139–146.

14.

Lin

(2004) Parallel machine scheduling of machine-dependent jobs with unit-length. European Journal of Operational Research 156(1): 261–266.

15.

Lipowski

Lipowska

(2012) Roulette-wheel selection via stochastic acceptance. Physica A: Statistical Mechanics and Its Applications 391(6): 2193–2196.

16.

Malve

Uzsoy

(2007) A genetic algorithm for minimizing maximum lateness on parallel identical batch processing machines with dynamic job arrivals and incompatible job families. Computers & Operations Research 34(10): 3016–3028.

17.

Okumoto

Iseki

(2005) Optimization of steel plate cutting sequence using the tabu search method. Journal of Ship Production 21(2): 134–139.

18.

Park

Lee

Park

. (1996) Modeling and solving the spatial block scheduling problem in a shipbuilding company. Computers & Industrial Engineering 30(3): 357–364.

19.

Rajakumar

Arunachalam

Selladurai

(2006) Workflow balancing in parallel machine scheduling with precedence constraints using genetic algorithm. Journal of Manufacturing Technology Management 17(2): 239–254.

20.

Ramachandra

Elmaghraby

(2006) Sequencing precedence-related jobs on two machines to minimize the weighted completion time. International Journal of Production Economics 100(1): 44–58.

21.

Ruiz-Torres

Paletta

Pérez

(2013) Parallel machine scheduling to minimize the makespan with sequence dependent deteriorating effects. Computers & Operations Research 40(8): 2051–2061.

22.

Varghese

Yoon

(2006) Shipbuilding erection network optimization: a TSP method. Journal of Ship Production 22(3): 139–146.

23.

Yang

Zhang

Yao

(2012) An overlapping-based process model for managing schedule and cost risk in product development. Concurrent Engineering 20(1): 3–17.

24.

Yoon

Varghese

(2007) Looking-forward scheduling approach applied in pre-erection area of a shipyard. Journal of Ship Production 23(1): 30–35.

25.

Zhong

(2012) Optimisation of block erection scheduling based on a Petri net and discrete PSO. International Journal of Production Research 50(20): 5926–5935.