In shipyards, scheduling is carried out with a focus on the dock plan. Therefore, when there are sufficient orders, the load level of a dock has little slack, if any. Even though the shipbuilding industry is in a recession due to the aftereffects of the global economic crisis, the large shipyards in Korea are managing to maintain a sufficient amount of orders for production, and the docks are still running at the maximum load level. Instead, due to the excessive amount of orders, the quays or predecessor processes such as block assembly are overloaded at times. If the block manufacturing process is overloaded, blocks can be outsourced. Many shipyards actually outsourced quite a few blocks when business was booming. However, more efficient utilization of internal resources is necessary for a better profit structure. Thus, research on the scheduling of block manufacturing processes needs to be carried out.

Large Korean shipyards have already built their own scheduling and planning systems. However, for certain tasks, the backbone system only handles the data storage; the actual task is done manually without the backbone system. Block assignment planning is one such task. The load level of these tasks can be reduced by automation or optimization, and they can be integrated and managed by extending the existing scheduling/planning system.

Block assignment planning is one of the midterm planning tasks; it assigns a block to the facility (factory/shop or surface plate) that will actually manufacture the block according to the block characteristics and current situation of the facility. It is one of the most heavily loaded midterm planning tasks. Reducing the overall load of the task is important along with appropriate assignment. In this paper, a diagram-based scenario modeling method is suggested to systematize the block assignment rules and automate the task to improve the block assignment planning efficiency.

There have been few studies that directly studied block assignment planning. Extending the range of interest to scheduling produces various studies of interest. Studies on shipbuilding scheduling can largely be divided into those either establishing the schedule or verifying the established schedule. The former includes many optimization studies, and the latter includes many simulation studies. Establishment and verification of the schedule are closely related.

Lamb et al. (2006) defined entities of production process and production logics through analyzing a shipyard fabrication/ forming shop. Furthermore, they suggested a method that enables us to grasp problems that a production process has by modeling & simulation. Song et al. (2009) analyzed the schedules of small- and medium-sized shipyards and verified that planned ships can be built while the established schedules are followed using simulation technology. Lee et al. (2009) constructed a simulation-based production execution system where the execution schedule was verified by the simulation method. Zhao et al. (2010) studied the hybrid parallel algorithm for scheduling job shop-type processes. Shin et al. (2008) studied layout planning of the ship assembly process using the differential evolution algorithm. The present study has similarities with the work by Shin et al. because they were essentially creating schedules while considering the capacity constraints of space resources. Layout planning of the assembly process is a detailed scheduling activity that is established after block assignment planning, which was the main focus of the present study. Guldogan (2011) studied how to optimize operation allocation to machines. When there are operations and machines with different characteristics, he determined the suitability of a machine to each operation based on expert opinions and assigned the most suitable operation to each machine through optimization using the genetic algorithm. The present study is similar to the procedure in their study, in that they assigned processes (operations) to resources, while block assignment planning assigns resources to products. Studies on scheduling so far mostly dealt with the optimization of the schedules subject to some constraints. However, changes in the constraints or in the model itself were difficult to be reflected. This study defines how to model constraints and automates the block assignment planning. Therefore, the proposed block assignment planning method can respond to the changes promptly.

In the present study, a diagram-based modeling method was used for automation of the block assignment planning in order to visualize the logical flows. Diagram-based methods are often used in process design or in the design of signal processing for the control of mechanical instruments because the logical flow is very important in these activities (Kiritsis and Porchet, 1996; Ramaswamy et al., 1997; Manesis and Akantziotis, 2005). Petri nets are widely used in process planning because they can describe not only the relationships between processes but also the product per se using a token, and a simple simulation can be carried out (Cecil et al., 1992; Venkatesh and Ilyas, 1995; Kiritsis and Porchet, 1996; Ramaswamy et al., 1997; Kiritsis et al., 1999). The Petri net has a wide range of applications; it is also used to model optimization processes (Reddy et al., 2001). Meng (2010) modeled a reconfigurable manufacturing system (RMS) using colored timed object-oriented Petri nets. An RMS is a manufacturing system to cope with the rapidly changing manufacturing environment, which includes both hardware and software. As in the above methods, diagram-based modeling methods play an important role in simplifying existing circumstances or in defining the rules that are written in a natural language in a systematic way. Furthermore, models defined by a diagram can be made into a library and can have high reusability. This study utilizes the advantages of the diagram-based modeling methods and establishes a block assignment planning method.

Process planning defines the process and determines the sequence of processes in order to optimize the efficiency of the manufacturing process plan. Hence, the process definition and sequence determination are separate processes. Once the processes are defined, the relationships and sequences between the processes become important. The Petri net can describe the relationships and sequences between processes very well and can also describe the status change of products using tokens (Kiritsis and Porchet, 1996; Kiritsis et al., 1999). The state diagram is a modeling method that focuses more on the change in states. In the present study, however, the diagram being defined carries out block assignment rule definition and sequence determination at the same time, and the change in states is less important. In contrast, true/false conditions are very important. Thus, a new diagram-based modeling method was defined in this study that considers the aforementioned characteristics and automates block assignment planning.

Ship production planning is a core production management activity that provides criteria for business strategies and profitability decision data via production prediction; productivity is improved through reactions to changes in the production environment. Ship production planning is an important concept because it plans and manages a series of production activities to maximize the profit of the shipyard.

Lee (2007) defined the ship production planning characteristics as follows. First, production is intensive because ship production acquires unit blocks by assembling components and continues to assemble the block until a ship is finally launched from the dock. Second, production is make-to-order; production starts with an order from an owner rather than considering the demand of the market. Third, production is engineer-to-order; shipbuilding does not produce a mass production-type product like general manufacturing industries but starts design and production based on the order from a customer.

Although the classification and definition slightly differ for individual shipyards, the ship production plan is divided into four steps: the production plan, master production schedule, midterm schedule, and short schedule. These depend on the planning area and range. Table 1 presents major decisions made in each step.

Block assignment planning is the process of assigning assembly blocks to shops where blocks can be assembled during the midterm scheduling after the production schedule is fixed. Blocks can be produced in-house or outsourced. In case of a large shipyard, there are many in-house shops available for assembling blocks. Therefore, a scheduler assigns blocks to the most suitable shops considering the characteristics of each block and shop capacity/constraints, so that the productivity is maximized while keeping up the schedule. Fig. 1 presents a conceptual diagram of block assignment planning (Lee et al., 2005).

The block assignment planning problem is very difficult because it is a combinatorial problem of assigning blocks to the shops while considering the characteristics of each block and shop capacity. Shipyards have recognized it as an important problem, and there have been several studies. However, automatic block assignment planning is not easy; most shipyards still carry out block assignment manually. In particular, the shops of the application target shipyard in this study (H heavy industries) were located far apart, as shown in Fig. 2. Therefore, block assignment is a very important problem in terms of the cost and productivity.

The rules for block assignment planning currently in use were organized and categorized by interviewing a block assignment planner. The type of diagram to prepare block assignment automation scenarios was determined.

Table 2 shows the block assignment rules in H heavy industries. Each shop prioritizes blocks belonging to GPE block that are manufactured in the same shop. Each shop determines block priorities according to the space constraints and processing capacities. Based on analysis of the block assignment rules, the rules can be classified into the following three types.

The first rule type is block manufacture priority. Each shop has conditions for preferring blocks based on its characteristics. The conditions for shop No.1 fall in this type. Shop No.1 prefers engine room (E/R) blocks first, followed by stern blocks. The second rule type specifies which shops cannot manufacture certain blocks. For example, shop No.1 cannot manufacture blocks larger than the specified size due to the size limitations at the painting facility. The third rule type is predetermining the shop in the planning stage. For example, all of the blocks that will be assembled into a GPE block at shop No.3 will be manufactured at shop No.3.

Rules can also be classified by the parameters that compose them. Primarily, they can be divided into block constraint rules and shop constraint rules. Then, they are further classified in detail according to the properties, such as block size, block weight, block type, etc. Table 3 presents the result of classification by the parameters. This result is important to define data model for block assignment planning.

Table 4 shows three basic entities with their representation methods and the functions. Decision entity distributes blocks according to certain conditions. Condition entity expresses a true or false logical condition for a decision entity. Contents of a condition entity consist of fundamental arithmetic operations and a comparison operation. Shop entity represents a place where an assigned block will be manufactured. These three entities can present most of block assignment rules, so they are defined as basic entities. Figs. 4 and 5 how algorithm of each entity and relationship between the entities.

Table 5 shows another three entities. They are defined as extended entities. Entities support functions of the basic entities to increase convenience of the modeling. Branching entity distributes blocks according to certain conditions like the decision entity. However, branching entity can distribute blocks to several paths by the corresponding conditions. Therefore, branching entity can replace many decision entities of the same level. The default entity is a virtual shop that has the same shape as the shop entity. Blocks assigned to this entity are assigned by the block assignment algorithm. This algorithm considers GPE shop and load balance of each shop. This helps greatly simplify block assignment scenarios. Fig. 6 shows block assignment algorithm of the default entity. Filter entity also simplifies scenarios by filtering the blocks corresponding to the third rule type given in the section 『Block assignment rule analysis』 earlier. This not only simplifies scenarios but also reduces the overall calculation time by filtering out some blocks from the beginning of a scenario.

When describing the block assignment rules with diagrams, comparing conditions based on the information for the blocks and shops is essential. Therefore, a data model that defines the properties of the blocks and shops is configured so that the conditions included in the block assignment rules can be input. The properties in the data model are used as parameters for the condition entities. Details on the contents of the block and shop data model are tabulated in Table 6. The block data model includes the block number and information on the weight and size of the block. Because the final block assignment result becomes part of the midterm schedule, information on the schedule and shop must be included. The shop data model includes the shop name, shop number, capacity information, size limitation information, etc. to check the constraints of the shop. To balance the loads between the shops, the load factor is included in the properties; this is the quantity assigned to a shop divided by the capacity.

Based on the diagrams (entities) defined earlier and the block assignment rules shown in Table 2, the scenario depicted in Fig. 7 was prepared as a simple verification example. In total, six conditions are reflected in the scenario. In this paper, the default entity algorithm is minimized to assign blocks to the GPE shops to verify function of the modeling entities and flexibility of scenario modeling method.

A block enters the scenario and is examined to determine if its GPE shop is shop No.3 according to the first decision diagram. If it is, the block is assigned to shop No.3; if not, the block proceeds to the branching diagram, where blocks are classified by type according to the three conditional statements. If it is an engine room block, the block is manufactured in shop No.1 or shop No.2. If the engine room block has a height greater than 7.2m, then it must be manufactured in shop No.2. If none of the three conditions applies, the block is assigned to the GPE shop.

A program to assign blocks according to the prepared scenario was developed using the C# programming language. The current program is limited in that it only works as ordered to by the scenario; if there is a change in the scenario, the program needs to be modified. According to the scenario, blocks of about 1-month quantity were assigned. The blocks entered the scenario basically in the order of the block start date; in case of a tie, the heavier block entered first. A total of 21,690tons of blocks were assigned to the shops; the results are shown in Table 7. To compare the result with the results from an actual assignment planner, the mean and standard deviation of the load factor for each shop were calculated and tabulated together.

Because the maximum capacity for each shop differed from one another, simply comparing the assigned quantity was not very meaningful with regard to examining the load balance. Hence, the load factor (assigned quantity/maximum capacity) was calculated, and the standard deviation of the load factor was used as an index of the load balance level. The results of the actual planner produced a mean of 98.8 with a standard deviation of 9.6; this can be interpreted as showing that the maximum capacities of the four shops were utilized well, and the load was balanced well. On the other hand, automatic assignment by the scenario produced a mean of 93.7 with a standard deviation of 77.3. This shows that the load was not balanced well at all. This is also shown by the load factor for each shop. With the automated system, the load factor for shop No.2 was quite low at 65.2, whereas those of shop No.1 and shop No.3 were well over 100, which is impossible in reality. This means that the block assignment planner adjusted the quantities among the four shops by intuition other than the rules in Table 2 reflecting the block characteristics, while the scenario shown in Fig. 7 did not consider the load balancing at all. Thus, a new block assignment scenario was prepared with the load balance condition and is shown in Fig. 8. The load factor conditions for shop No.1 and shop No.3 are shown on the

The load factor conditions for shop No.1 and shop No.3 are shown on the lower left and lower right, respectively, of Fig. 8. In addition, the GPE shop condition for shop No.1 was added under the load factor condition. These three conditions distributed the loads on shop No.1 and shop No.3 to shop No.2 and shop No.4. The results from this new scenario are shown in Table 8. To distinguish the results of the new scenario from those of the original scenario, they have been designated as scenarios 1 and 2, respectively. The results of scenario 2 showed that the load factors of shop No.1 and shop No.3 greatly decreased compared with the results of scenario 1. As a result, the standard deviation of scenario 2 was 8.1, which is far less than that of scenario 1. The results of scenario 2 compare favorably with those of the manual planning presented in Table 7.

Another important issue in block assignment is the logistics. Table 9 shows the number of blocks to be transported from a shop that manufactures an assembly block to a shop that manufactures a GPE block for all three cases: manual result, scenario 1, and scenario 2. Each row represents a GPE block shop, and each column represents an assembly block shop. If the assembly block shop is the same as the GPE block shop for a given block, that block does not need any transport. The subtotal shows the number of assembly blocks to be transported to the GPE block shop for each assembly block shop, and the total shows the number of blocks that need to be transported; it is the sum of the subtotals. Table 9 shows that there were 317 blocks in total: 84, 99, and 87 needed to be transported according to the manual result, scenario 1, and scenario 2, respectively. In the case of scenario 1, the block quantities were concentrated in shop No.1 and shop No.3, as shown previously. As a result, assembly blocks manufactured in shop No.1 and shop No.3 seldom needed a transport, while the transport of the blocks from the other two shops increased; the overall transport quantity increased as well. In scenario 2, the concentrated quantities were distributed, and the number of blocks to be transported also greatly decreased.

A comparison of all three results showed that scenario 1 gave inadequate results with regard to both the load balance and the transport due to the fact that it only reflected the characteristics of the shops. By adding the load balance conditions, scenario 2 gave similar results as the manual results. Although scenario 2 is not an optimal assignment scenario, it is quite meaningful in that it gives similar results in a minute, while manual planning takes about a day.

Through the proposed block assignment planning that utilizes the diagram-based scenario modeling method, it was confirmed that the block assigning rules of shipyards can be represented using diagrams. Furthermore, the result of block assignment planning was comparable with that of an expert in terms of quality and was much better in terms of working hours.

In this study, automation of block assignment planning was suggested to reduce the workload in midterm planning, which is currently carried out by experienced experts. By analyzing the block assignment rules, scenario model entities were defined to present the rules and data models for blocks and shops were defined to examine block and shop information according to the rules. Two scenarios were prepared using the defined diagram-based modeling method for an actual shipyard and compared with a manual block assignment plan. The result showed that automation of block assignment planning is possible; preparation of a sophisticated scenario showed that results similar to those from manual planning can be acquired in much less time. The proposed block assignment planning method can systematically represent the constraints in shipyards and can significantly reduce the block assignment planning working hours. Hence, it can help diversify or concretize the constraints. As future work, it is necessary to improve the validity of the diagram-based representation method of the block assignment rules by verifying more various block assignment scenarios. This study automated the diagram-based scenario modeling method and reduced the block assignment planning working hours, but there is a little room for improvement in terms of quality of the planning result. Therefore, by combining the scenario models and optimization algorithms, a block assignment planning optimization will be carried out.