Article Preview
Top1. 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.