Advanced
Automation of block assignment planning using a diagram-based scenario modeling method
Automation of block assignment planning using a diagram-based scenario modeling method
International Journal of Naval Architecture and Ocean Engineering. 2014. Mar, 6(1): 162-174
Copyright © 2014, The Society of Naval Architects of Korea
This is an Open-Access article distributed under the terms of the Creative Commons Attribution Non-Commercial License (http://creativecommons.org/licenses/by-nc/3.0) which permits unrestricted non-commercial use, distribution, and reproduction in any medium, provided the original work is properly cited.
  • Published : March 31, 2014
Download
PDF
e-PUB
PubReader
PPT
Export by style
Share
Article
Author
Metrics
Cited by
TagCloud
About the Authors
In Hyuck Hwang
Department of Naval Architecture and Ocean Engineering, Seoul National University, Korea
Youngmin Kim
Department of Naval Architecture and Ocean Engineering, Seoul National University, Korea
Dong Kun Lee
Department of Naval Architecture and Ocean Engineering, Mokpo National Maritime University, Korea
Jong Gye Shin
Research Institute of Marine Systems Engineering, Seoul National University, Korea
Abstract
Most shipbuilding scheduling research so far has focused on the load level on the dock plan. This is because the dock is the least extendable resource in shipyards, and its overloading is difficult to resolve. However, once dock scheduling is completed, making a plan that makes the best use of the rest of the resources in the shipyard to minimize any additional cost is also important. 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 and is carried out manually by experienced workers. In this study, a method of representing the block assignment rules using a diagram was suggested through analysis of the existing manual process. A block allocation program was developed which automated the block assignment process according to the rules represented by the diagram. The planning scenario was validated through a case study that compared the manual assignment and two automated block assignment results.
Keywords
INTRODUCTION
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.
LITERATURE REVIEW
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.
BLOCK ASSIGNMENT PLANNING
- Ship production 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.
Production planning in shipyards.
PPT Slide
Lager Image
Production planning in shipyards.
- Block assignment planning
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 ).
PPT Slide
Lager Image
Concept of block assignment planning.
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.
PPT Slide
Lager Image
Example of shop location (Google maps, 2005).
ASSIGNMENT SCENARIO MODELING METHOD
- Block assignment rule analysis
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.
Block allocation rules.
PPT Slide
Lager Image
Block allocation rules.
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.
Classification of rules by parameters that compose the rules.
PPT Slide
Lager Image
Classification of rules by parameters that compose the rules.
- Definition of block assignment scenario modeling entity
To define how to express block assignment rules in a form of diagrams, various diagrams that can show logical flows as block assignment process were analyzed. Some typical diagram representation methods include finite state machine, Petri Nets, sequence flow chart (SFC), flow chart, etc. Finite state machine and Petri Nets are state-centric modeling methods. SFC is a diagram that expresses programmable logic control (PLC) logic. Flow chart is one of the methods that express an algorithm during the course of programming. As mentioned earlier in the literature reviews section, finite state machine and Petri Nets express sequence and relationship between processes quite well, but expression of the conditions that determine progress of processes is hidden intrinsically and hence has low visibility. In case of SFC, conditions can be expressed well, but it is lacking in diagram components to express elements other than conditions ( Fig. 3 ). Flow chart is appropriate to express rules of block assignment, but is lacking in visibility of the components to express the conditions ( Fig. 3 ). Hence, this study defined a diagram-type representation method that is based on the flow chart and also has the condition expression method of SFC.
PPT Slide
Lager Image
Example of SFC (left) and flow chart (right).
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.
Basic entities and diagram of block assignment scenario model.
PPT Slide
Lager Image
Basic entities and diagram of block assignment scenario model.
PPT Slide
Lager Image
Algorithm of basic entity.
PPT Slide
Lager Image
Relationship between basic 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.
Extended entity and diagram of block assignment scenario model.
PPT Slide
Lager Image
Extended entity and diagram of block assignment scenario model.
PPT Slide
Lager Image
Assignment algorithm of a default entity.
- Data model of blocks and shops
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.
Data model of assembly block and shop.
PPT Slide
Lager Image
Data model of assembly block and shop.
CASE STUDY
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.
PPT Slide
Lager Image
Block assignment scenario model (1).
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.2 m , 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,690 tons 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.
Automatic block allocation result (1).
PPT Slide
Lager Image
Automatic block allocation result (1).
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
PPT Slide
Lager Image
Block assignment scenario model (2).
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 .
Automatic block allocation result (2).
PPT Slide
Lager Image
Automatic block allocation result (2).
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.
Count of transported block.
PPT Slide
Lager Image
Count of transported block.
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.
CONCLUSIONS
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.
Acknowledgements
This paper was financially supported by a Simulation-based Production Technology for Ships and Offshore Plants grant funded by Korea government Ministry of Knowledge Economy (MKE) (No. 10035331).
References
Cecil J.A. , Srihari K. , Emerson C.R. 1992 A review of petri net applications in manufacturing The International Journal of Advanced Manufacturing Technology 7 (3) 168 - 177
Guldogan E.U. 2011 An integrated approach to machine selection and operation allocation problem The International Journal of Advanced Manufacturing Technology 55 797 - 805
2005 http://maps.google.co.kr/
Kiritsis D. , Neuendorf K.P. , Xirouchakis P. 1999 Petri net techniques for process planning cost estimation Advances in Engineering Software 30 (6) 375 - 387
Kiritsis D. , Porchet M. 1996 A generic Petri net model for dynamic process planning and sequence optimization Advances in Engineering Software 25 (1) 61 - 71
Lamb T. , Chung H. , Spicknall M. , Shin J.G. , Woo J.H. , Koenig P. 2006 Simulation-based performance improvement for shipbuilding processes Journal of Ship Production 22 (2) 49 - 65
Lee D.H. , Kang Y.W. , Kim H.J. 2005 Block Assignment planning for shipbuilding considering preference shop and load balancing Daewoo Shipbuilding & Marine Engineering Research report 61 (2) 32 - 41
Lee J.M. 2007 An integrated process and measurement framework for planning production of large shipyards Seoul National University
Lee K.K. , Shin J.G. , Ryu C. 2009 Development of simulation based production execution system in a shipyard: a case study for a panel block assembly shop Production Planning & Control 20 (8) 750 - 768
Manesis S. , Akantziotis K. 2005 Automated synthesis of ladder automation circuits based on state-diagrams Advances in Engineering Software 36 (4) 225 - 233
Meng X. 2010 Modeling of reconfigurable manufacturing systems based on colored timed object-oriented Petri nets Journal of Manufacturing Systems 29 (2-3) 81 - 90
Ramaswamy S. , Valavinis K.P. , Barer S. 1997 Petri net extensions for the development of MIMO net models of automated manufacturing systems Journal of Manufacturing Systems 16 (3) 175 - 191
Reddy J.P. , Kumanan S. , Chetty O.V.K. 2001 Application of petri nets and a genetic algorithm to multi-mode multiresource constrained project scheduling The International Journal of Advanced Manufacturing Technology 17 305 - 314
Shin J.G. , Kwon O.H. , Ryu C. 2008 Heuristic and metaheuristic spatial planning of assembly blocks with process schedules in an assembly shop using differential evolution Production Planning & Control 19 (6) 605 - 615
Song Y.J. , Woo J.H. , Shin J.G. 2009 Research on a simulation-based ship production support system for middle sized shipbuilding companies International Journal of Naval Architecture and Ocean Engineering 1 (2) 70 - 77
Venkatesh K. , Ilyas M. 1995 Real time Petri nets for modeling, controlling, and simulation of local area networks in FMS Computers & Industrial Engineering 28 (1) 147 - 162
Zhao Y.W. , Wang H.Y. , Xu X.L. , Wang W.L. 2010 A new hybrid parallel algorithm for consistent-sized batch splitting job shop scheduling on alternative machines with forbidden intervals The International Journal of Advanced Manufacturing Technology 48 (9-12) 1091 - 1105