Scheduling Systems In Shipbuilding Computer Science Essay

Published: Last Edited:

This essay has been submitted by a student. This is not an example of the work written by our professional essay writers.

In this project, firstly we need to understand the meaning of scheduling in general. Scheduling is organizing and managing a set of tasks, with regards of capacity, capability, and time constraints, such as starting time, precedence, and deadlines. Generally, in every manufacturing environment, orders are frequently coming in and have to be transformed into jobs with associated to priority and due dates. Certain jobs have to be processed in some workshops with given constraints and interdependencies, such as a ship cannot be painted without the hull is being finished; a steel plate can not be welded to the existing structure if it has not been cut according to proper dimension. The jobs may be delayed due to the fact that certain workshops are still busy. Additionally, ship components are usually very big and needs large-enough area to store it. Unexpected events, such as delay processing times, lack or human resource, and lack or material should have to be taken into account because these problems affect the schedules. The whole production planning process, which considers medium to long-term plan and endeavors optimizing the resource allocation has a major effect on schedule. Important data such as demand and resource forecast, technological update and market developments would influence the scheduling process. To analyze and solve scheduling problem, algorithm should be developed to deal with daily situation. Based on the project, spatial scheduling is the most suitable for shipbuilding industry with respect to time scheduling as well.

2.1.1. Scheduling Systems in Shipbuilding

Scheduling in shipbuilding industry is really complicated because all the material, tasks and time should be organized carefully to make all the production process work smoothly with respect to minimized cost. According to Lee et al. journal that discussed about Daewoo Shipbuilding Company is dealing with their scheduling system to make it more optimize. Daewoo Shipbuilding Company is a Korean company, which is considered as the largest shipbuilders in the world with VLCC (Very Large Crude Oil) and container ships as its products. The problem that Daewoo encountered is the complex scheduling system of their production process from the time orders to final delivery. Also the scheduling and control of human resource, material, and facilities are very complex. "Poor Scheduling keeps workers waiting for the prerequisite subassemblies, causes fluctuation of work loads resulting in expensive overtime work, and may cause delay in delivery."(Lee et al.) To solve this scheduling problem, KAIST (Korea Advanced Institute of Science and Technology) and Daewoo are join to perform DAS (Daewoo Shipbuilding Scheduling) Project as a solution approach to make a significant improvement in productivity and reengineering of scheduling. There are several key points in DAS Project:

DAS - ERECT: It is about erection (construction) scheduler at shipyard and it establishes the due date of each block's assembly. It schedules the construction of blocks at the dock.

DAS - CURVE: Curved Block Assembly Shop Scheduler. It schedules its own workshop according to due dates, spatial resources, and manpower.

DAS - PANEL: Paneled Block Assembly Shop Scheduler. It also organizes its own workshop based on due date, spatial and manpower resources.

DAS - MH: Neural Network based Man-hour Estimator

Also, there are several key successes behind DAS project, like the architecture of shipbuilding scheduling, spatial scheduling, dynamic assembly line scheduling, constraint directed graph search, man-hours scheduling, and three-phased development strategy.

For the hierarchy architecture of shipbuilding scheduling, the blocks can be categorized into two types: the flat-bottomed that is assembled in Paneled Block Assembly Shop (PBS) and curved-bottomed that is assembled in Curved Block Assembly Shop (CBS). Several blocks are assembled into larger assembly at Pre-Erection Shop called super blocks to reduce the assembly time in other workshop area. In common shipbuilding industry, the shapes of the objects seem to be convex polygons, such as trapezoid, triangles, and rectangles. Furthermore, the constraint directed graph search in construction scheduling originated from the fact that PERT was not an appropriate tool, as many constraints would not be considered.

Screen shot 2011-03-27 at 8.58.57 PM.png

Figure 1.

According to Lee et al., the objective of DAS - ERECT in terms of block construction is balancing the load among every stage of assembly operations and minimizing of makespan. In this paper, there are two types of constraints that are taken into account, resource and technical constraints. Resource constraints are the capacity of human, material handling, and area, on the other hand, technical constraints are partial sequence and precedence relationship. Moreover, backtracking idea is an interesting tool for finding a feasible schedule for certain day. Backtracking and adjustment the current spatial layout, starting time of scheduled and resource commitment levels are necessary.

2.1.2. Spatial Scheduling and Block Placement

Mostly every journal said that dealing with block spatial scheduling is complex because it is a combination between scheduling and spatial allocation concurrently. Space is limited and usually become the bottleneck; as a result block assembly process is the bottleneck in shipyard because it requires large space. Earliest Starting Time (EST) and Latest Starting Time (LST), geometric shape and the list of possible area for each block are necessary for deciding the block assembly process. EST depends on the arrival of materials while LST is the latest time of the block start processing. Both EST and LST are considered as precedent constraints according to Park et al.

Spatial scheduling is also another good tool because it deals with the optimal dynamic spatial layout schedules. The goal is to pursue the due-date satisfaction, maximal utilization a spatial and non-spatial resources, and minimization of waiting time for work-in-process and final product inventories. Then, the constraints are "crane capacity, man-hour availability, assembly due date, precedence between associated assemblies, and maximum acceptable waiting time for completed and work-in-process blocks." Searching space in spatial scheduling means "to find feasible positions of an object ai within a workplate W, which do not overlap a scheduled object bj."(Lozano-Perez 1983; Zhu and Latombe 1991). Configuration space according to Lozano-Perez is a space which object's reference point can go through one place without interference with existing object. In this paper, there are two types of configuration space, obstacle avoiding and inner locatable space.

In the obstacle-avoiding space S(ai|B), the reference point of an object ai should be placed without interference with the located objects, that are considered as obstacles. On the other hand, the inner locatable space S(ai|W), the reference point of an object ai could be placed inside the work area, W. "The feasible locatable space will be S(ai|B,W) which means the intersection of previous two spaces:

S(ai|B,W) = S(ai|B) ∩ S(ai|W)" (citation needed).

The figure below describes the spaces where the object aj should be located inside W, where there are already two objects, b1 and b2.

Screen shot 2011-03-27 at 11.42.52 PM.png

Other journal by Lozano also shows that spatial planning problems in terms of placing an object among other existing object without interference with each other. In the common problem, there are two main points that needs to take into account in spatial planning problem, geometry and optimization.

Before go further into model, there are few notations that need to be described, R is a convex polyhedron that contains kB, convex polyhedral Bi as obstacles, A is the union of kA and convex polyhedral Ai. According to Lozano, there are two algorithms in regards to store objects inside the area:

Findspace - find the right position for A as polyhedral object inside the R.

∀i∀j : Ai ∩ Bj = ∅, it is called safe position.

Findpath - find the path for A as polyhedral object from position s to g without any interference, therefore, A is inside R and never overlaps any Bi. This situation is called safe path.

Screen shot 2011-03-29 at 12.35.32 AM.png

FindspaceScreen shot 2011-03-29 at 12.35.45 AM.png


Other journal also discussed different method in dealing with spatial scheduling. According to Zheng et al. paper, block spatial scheduling problem can be solved using several scheduling strategies such as greedy algorithm with the purpose of minimizing makespan. Block spatial scheduling can be divided into several stages:

Sort blocks according to geographic sizes and technology process

Assign the selected blocks to the most available work area with considering of material handling constraint

Locate the block in the right workshop with optimum position orientation

Calculate the whole production time and show output of dynamic spatial layout or the allocated blocks and orders

Screen shot 2010-07-14 at 10

Figure. X. Structure of spatial scheduling system

In order to optimize the spatial resource, the blocks' characteristics and available space should be analyzed in selecting the correct scheduling strategies,

Blocks are assembled in selected workshop based on block attributes and available work plate. Block attributes like shape, size, material and tools, and the attributes of work plate such as handling capacity, size, some blocks should be erected in a special work area.

Maximal remnant space strategy

In this plant, there are several work plates that blocks can be stored. The proper area should be the one, which is able to balance the workload.

Initial positioning strategy

At the beginning, there is no block in the work plate when it is selected for the block. After locating the block in the proper position, selecting the best point (s) to know the exact spot is needed.

Clustering Strategy

Cluster means treating two different blocks as one object. One block has similar processing time, while others have comparable shape mutually. Figure below shows that minimal orthogonal covering parallelepiped (MOCP) ob block a and b have similar processing time, therefore, both of them can be treated as one object. Moreover, both of them can be lifted and moved out the work plate at the same time so that it makes more efficient and effective for lifting environment. The other blocks, like c and d have compensatory shape, are located adjacently; thus, it is minimize the fractured space. Hence, clustering strategy improves utilization of the work plate.

Screen shot 2011-03-29 at 2.09.11 AM.png

Maximal available space strategy

To fully utilize the limited space in the work plate; therefore, the block can be allocated there.

Minimum occupied space strategy

Fixed backtracking

Fixed backtracking strategy based on this paper is useful in spatial scheduling problem mainly to minimize the makespan due to different shape and time.

2.1.3. Time Scheduling

According to Asanao and Ohta, this paper discusses about job shop scheduling problem with objective to minimize the total weighted tardiness due to specific job due dates and delay penalties. A heuristic algorithm called tree search procedure has been developed to solve the time scheduling problem. Heuristic algorithm is simple because it does not require any parameter estimation for the implementation and the sub optimum schedules takes little computation effort. Moreover, another proposed algorithm that might be worth to take a look into is called Apparent Tardiness Cost Rule and Shifting Bottleneck Procedure.

In addition, the paper by Tamer Eren, is concerned about multiple goals on production scheduling and the objective is to minimize the weighted sum of total completion time, makespan, maximum tardiness, and maximum earliness. This algorithm considers NP-hard class and uses integer programming, which seems to be complicated. Only small size problems, such as up to 20 jobs, can be solved using the integer-programming model. On the other hand, tabu search algorithm is tested in 1000 jobs and it alters a current solution in a certain manner and takes the best alteration as the new current solution. To avoid being trapped at local optima, the best neighbor is worse than current solution becomes the new current solution. Furthermore, there are certain moves called tabu to avoid cycling. There are six tabu search methods:

Random tabu

SPT tabu search

Johnson's-rule tabu search

EDD tabu search

MST tabu search

NEH tabu search

This paper is good to consider different kinds of methodology and think about the possibilities of applying this method.

2.2. Positioning Block

2.2.1. Bin Packing

Block placement is similar with bin problem as a NP-hard case, which means it is hard to find the optimal solution. The primary key of bin packing is to pack a collection of objects into well-defined areas called bins; therefore, they do not have interference. In reality, the critical issue is to make efficient use of space and time. A bin in block placement industry is a stocking area.

In Berkey and Wang paper, they discussed about two-dimensional finite bin-packing algorithms. A finite block is to be packed into finite bin and the number of bins should be minimized. The authors also developed heuristic algorithms, which includes packs denoted as P={P1, P2,…,Pn) and bins as B= (B1, B2, …, Bn) as follows:

Finite next-fit (FNF)

This algorithm is packing all the blocks into finite bins with having finite dimensions. In this algorithm, the blocks will be put in the bin when it fits, if the next block is coming and it cant have more space at this bin, the current bin will be removed from the list and a new empty bin is added to it.

Screen shot 2011-05-03 at 2.37.00 PM.png

Figure X. Finite Next Fit Systematic

Finite first-fit (FFF)

The block first fit rule is using fully maximize the first bin and checking each of its levels from the bottom to the upper level to see if the blocks can be placed there. If there are no blocks can be put in there, the next bin is searched and or the bin is created if there are no more bin in the list.

Screen shot 2011-05-03 at 2.35.16 PM.png

Figure x. Finite First-Fit layout

Finite best-strip (FBS)

"The finite best-strip algorithm first packs the list P into level in an open-ended strip, using a best-fit packing approach to select the level for packing the next piece. The finite best-strip approach, the level (bin) that is selected for the next block is the level bin whose resulting packing has the minimum remaining horizontal area." (citation ) The approach is to maximize the empty space.

Screen shot 2011-05-03 at 2.38.06 PM.png

Figure X. Finite Best Strip Layout

Finite bottom-left (FBL)

The finite bottom left approach searches the empty space in each bin for the lowest and left position and locates the block. If there is no space at the current bin, the new bin will be created.

Screen shot 2011-05-03 at 2.38.15 PM.png

Figure X. Bottom Left Rule Layout

Besides that Almeida and Figueiredo discussed about "the simplest way to look at the problem by considering storage centers that stores items in boxes that must be packed into shelves for a diverse set of customers." (citation needed) From this understanding, the items will be the blocks. Moreover, this papers apply heuristic method for the "3D bin packing problem without rotation on the boxes, which aims to minimize the total waste of space by using the evaluation of the space left between the packed boxes and unfilled space at the front of the packing in each one of the bins." (citation needed) This heuristic algorithm is called corner point (CP) by Martello et al. Furthermore, the author applies other method called branch and bound algorithm that uses only cubic bins (area) to find optimization in 3D bin packing problem. On placing the items in the area, they start the placement by the left-bottom-back corner, placing each block at the right hand side of the last placed blocks. Another possibilities are placing the block on the corner point and the back then if the block doesn't fit there, it will be put at the first left and front corner point. This algorithm is called Corner Points for the Box (CPBOX), which is using computer programming to solve it.

The other bin packing articles are really good to have more idea on how to deal with block scheduling. Bin packing problem can be used in shipbuilding industry, especially on how to place the blocks in storage area in an efficient way.

2.2.2. Spatial Planning

According to Joe et al. (Heuristic and Metaheuristic Spatial Planning of Assembly Blocks with Process Schedules in An Assembly …) , there are several algorithms for spatial planning assembly blocks, such as bottom-left fill (BLF), differential evolution (DE), automatic arrangement, and metaheuristic placement for locating the blocks into work plates with different requirements.

The heuristic algorithm for block placement procedures are divided into two things, one is block sequence and the other is how to move blocks that are put in such orders. "If the order of blocks is determined, they will be put onto the preferred work places like Queuing model." (Banks et al. 2001). BLF procedure is two-dimensional packing and it provides possible placement location point and finds the most left location for the blocks to be put. Usually, the block is sorted according to start date and areas and then blocks will be put in one area. Once blocks are placed, interference between blocks or facilities should be checked. If there is any interference, then it should be moved right or up until it has no interference.

Differential evolution firstly presented by Storn and Price (1997). "DE algorithm is a stochastic optimization method for minimizing an objectives while incorporating constraints."(citation needed) DE has proven as an effective and robust optimization that outperforms traditional genetic algorithm."(Storn and Price 1997) The advantages are:

1. Fast convergence

2. Few control parameter

3. Global minimum has been found despite the initial parameter

The purpose of this algorithm is to recognize how much area used and how many items are located. Therefore, this algorithm is to maximize storing the blocks inside the workshop. This paper is really useful for me in terms of researching the algorithm on how to put the blocks in each storage area. I will apply one of the algorithms in this paper to my project and modify it to adjust with my project criteria.

2.3. Layout

Plant layout is one of the factors that give large influences in the international competitiveness of shipbuilding as a world industry. To build a factory, there are several things that need to be considered. In the shipbuilding, the factors are area size for storage and workshops, the production flow, area functions, and etc. Shipyard will be divided into small-size, medium-sized, and large-sized vessels. Each size will have different layout, because the bigger the products, the bigger area that the shipyard needs. "The space requirement is readily admitted by shipyard managers but not so readily provided by the nature of circumstances." (Todd, 30)

Hull construction



1. Steel Preparation

The process of machinery or forge inside the shipyard or elsewhere.

The process of installing the non-structural and non-propulsion items to a ship.

2. Steel Cutting

The process of adding a propulsion items to a ship.

3. Steel Bending

4. Unit preparation - welding the steel into units

5. Unit assembly

6. Assembly erection - blocks assembled in a dock to complete hull construction

Table 1. Division of Shipyard

Nowadays the shipyard is focusing on modular construction and pre-outfitting. Modular construction means "efficient flow of material to construct large sections or assemblies of ships in panel lines, joining these form modules or blocks and then joining the modules to form the completed hull." (Todd, 34) Meanwhile, pre-outfitting refers "to the installation of components into the module, such as pipes, cables, and ventilation equipment, prior to working the assemblies into the hull. Below is the example of modern shipyard for medium-sized-vessels."(Todd,Screen shot 2011-04-04 at 8.03.08 PM.png