Interactive Genetic Algorithms for Optimal Assignment of Blocks into Workspaces of Shipbuilding Industry

Interactive Genetic Algorithms for Optimal Assignment of Blocks into Workspaces of Shipbuilding Industry

Qin Shiming (Department of Industrial Engineering, Ajou University, Suwon, South Korea), Satchidananda Dehuri (Department of Systems Engineering, Ajou University, Suwon, South Korea) and Gi-Nam Wang (Department of Industrial Engineering, Ajou University, Suwon, South Korea)
Copyright: © 2015 |Pages: 19
DOI: 10.4018/IJAEC.2015010102
OnDemand PDF Download:
List Price: $37.50


In this paper one of the fundamental problems of Shipbuilding Industry known as block assignment problem is modeled and solved. The irregular shape of blocks and the inherent intractability of this problem is the primary motivation to use the interactive genetic algorithms with a specialized chromosome level “repair” operator. Without loss of generality, some domain knowledge has been incorporated during the process of exploration and exploitation of an optimal assignment. Therefore the best attributes of objective and subjective evaluation at system level has been realized. The experimental study confirms that the incorporation of the domain knowledge and a new repair operator in interactive genetic algorithms for assigning blocks in workspaces leads to faster convergence and at the same time it reduces the local optimality.
Article Preview

1. Introduction

In a large heavy industry (e.g., Shipbuilding) efficient planning, scheduling/assignment and controls with an aid of modern computational technique based systems engineering approach is vital in achieving high productivity (Park et al., 1996; Lee et al., 1996). Shipbuilding is make-to-order manufacturing, and it takes a long time to complete the products. There are many complicated processes between an order and the final delivery, and a large amount of working capital is required. It is difficult to manage the material, human, facility, and information resources. Therefore, the scheduling/assignment and control of a shipbuilding plant are a very complex task (Garey and Johnson, 1979).

Further, planning and control of the shipyard is a very complicated task because of the vast scope of the problem and the complexities of the problems involved in the decision making. The manual or ad-hoc planning and control system, which has been used, has a limited effect in the shipyard because of the unrealistic and untimely work orders it gives. Moreover, the ad-hoc system cannot respond quickly to the changing conditions, since it takes a long time to find a schedule manually. As a means to handle these problems many shipbuilding companies are moving towards developing efficient systems based on modern computational approach, so that they can compete.

With a motivation of solving very complex tasks of shipbuilding industry like mega-block assembly in a shipyard, we restrict ourselves with block assignment problem which can be realized as the ground level problem. In this problem, we have a pre-defined number of big size workspaces and a predefined number of blocks with irregular shapes. The sizes of the blocks are smaller than the size of the workspaces. Usually the objective is the waste minimization. In geometric viewpoint, how effectively we assigns the blocks into workspaces (i.e., no overlapping between blocks, containment of the blocks inside workspaces) so that the spaces of the workspaces must be utilized maximally. Note that even the problem of checking whether there exists an assignment that satisfies all constraints involved in this problem is very hard. In fact, it can be shown that the bin-packing problem and its variants are a special case of this problem. Since the bin-packing problem is defined as NP-complete, this problem is also NP-complete (Garey and Johnson, 1979). Further, we can also easily prove that this problem is NP-complete by reducibility.

Hence, due to the intractability nature of this block assignment problem and irregular shape of blocks, it is arguably adopted an interactive genetic algorithms (Banzhaf et al., 2006; Takagi, 2001; Parmee, 2003). However, the problem can be solved by canonical genetic algorithms, but three general characteristics that might appear to limit its effectiveness. First the basic selection, crossover, and mutation operators are common to all applications. Second, a canonical genetic algorithm requires extensive experimentation for the specification of several parameters so that appropriate value can be identified. Third canonical genetic algorithm involves a large degree of randomness and different runs may produce different results. Therefore this research is used the flavor of IGA by incorporating problem specific operators and domain knowledge. To the best of our knowledge this is the first attempt of modeling and solving block assignment problem using interactive genetic algorithms.

The rest of the paper is set out as follows. In Section 2, we discuss the background and related work. The block assignment problem is formulated and defined in Section 3. The proposed method and experimental study has been discussed in Sections 4 and 5. Finally, conclusions are drawn in Section 6.

Complete Article List

Search this Journal:
Open Access Articles: Forthcoming
Volume 8: 4 Issues (2017): 3 Released, 1 Forthcoming
Volume 7: 4 Issues (2016)
Volume 6: 4 Issues (2015)
Volume 5: 4 Issues (2014)
Volume 4: 4 Issues (2013)
Volume 3: 4 Issues (2012)
Volume 2: 4 Issues (2011)
Volume 1: 4 Issues (2010)
View Complete Journal Contents Listing