# A Hybrid Heuristic Algorithm for Ship Block Construction Space Scheduling Problem

Authors: Shicheng Hu; Tengjiao Liu; Song Wang; Yonggui Kao; Xuedong Sun
Journal: Discrete Dynamics in Nature and Society
 (2015)

---

## Abstract

Ship block construction space is an important bottleneck resource in the process of shipbuilding, so the production scheduling optimization is a key technology to improve the efficiency of shipbuilding. With respect to ship block construction space scheduling problem, a hybrid heuristic algorithm is proposed in this paper. Firstly, Bottom-Left-Fill (BLF) process is introduced. Next, an initial solution is obtained by guiding the sorting process with corners. Then on the basis of the initial solution, the simulated annealing arithmetic (SA) is used to improve the solution by offering a possibility to accept worse neighbor solutions in order to escape from local optimum. Finally, the simulation experiments are conducted to verify the effectiveness of the algorithm.


---

## Body

## 1. Introduction

Space is the key resource in ship block construction process. How to minimize the makespan of the project under space resource and precedence constraints is a complicated scheduling problem. As for this problem, two related problems are involved: resource constrained project scheduling problem (RCPSP) and bin packing problem.RCPSP can be described as a problem which should be scheduled under the limits of technology and other constraints to meet the objective of a project [1]. Generally, the goal is to get the shortest project makespan under the available resources and precedence constraints. The methods can be classified into two categories: exact methods and heuristic methods. Hartmann [2] puts forward that RCPSP belongs to NP-hard problem because it is always used to extend machine scheduling problem [3, 4]. So with the augment of problem scale, the computational complexity will increase rapidly. Many researchers have used exact algorithm to solve RCPSP [5, 6]; however, most of them proposed that exact algorithm is not feasible in reality. Priority rules proposed by Kelley [7] indicated that RCPSP can be solved by heuristic algorithms. Liu and Wang [8] tried to reduce the project makespan by heuristic algorithms and achieved good results. Bhaskar et al. [9] utilized parallel methods and priority rules to solve RCPSP with fuzzy activity times. Lee et al. [10] proposed a ship block construction space scheduling problem and described this problem theoretically. Koh et al. [11] solved the scheduling problem in shipbuilding company by heuristic algorithm.The bin packing problem is putting more boxes into a limited bin in order to minimum the height. This problem can be classified into two categories, two-dimensional and three-dimensional problems. For the former one, researchers tend to solve bin packing problems by heuristic methods. They are Bottom-Left (BL) algorithm [12], Bottom-Left-Fill (BLF) algorithm [13]. In addition, Belov et al. [14] considered adapting one-dimensional problem for solving two-dimensional problems. Chan et al. [15] tried to solve two-dimensional problems by heuristics with stochastic neighborhood structures. For three-dimensional problems, the most popular 3BF [16], proposed by Silvano Martello in 2000, figure out the problem of how to choose the most suitable cubes. Alvarez-Valdes et al. [17] used a GRASP/Path relinking algorithm to solve multiple bin-size bin packing problems. Liao and Hsu [18] found new lower bounds to improve the efficiency of three-dimensional problems.This paper is organized as follows. After introduction, Section2 presents a mathematical model. Section 3 gives the hybrid heuristic algorithm for this problem. In Section 4, we conduct simulation experiments to verify the effectiveness of the algorithm. Section 5 proposes general conclusions.


## 2. Ship Block Construction Space Scheduling Problem

Ship block construction space scheduling problem can be described as a project which includesn activities N={1,2,…,n}; place is required to process activities. A activity can be defined as aik=eik×cik, where eik and cik represent the length and width of place k which activity i needs. The duration of activity i is ti. Ii and Hi are the start and finish time of activity i. During the project, there are m places M={1,2,…,m} which can be defined as Bk=Ek×Ck.During the project, every activity is under precedence constraints, and we propose thatPj is the predecessors of activity j. So j can not be started if any one of its predecessors in Pj has not been finished. We assume that the start time of the whole project is 0. For the convenience of modeling, we also introduce two dummy nodes: activity 0 and n+1. They do not need time and space. 0 is the predecessor of all the activities in the project; meanwhile, n+1 is the successor of all the activities. So In+1 is the makespan of the project. In addition, we regard an activity as a cube which is represented as zik=eik×cik×ti. All the activities can be rotated in horizontal with 90 degree, and ri=1 and 0, indicating that activity i is rotated and not, respectively. The model of this problem is shown in what follows:(1)Minimize:In+1,(2)Ii+ti≤Ij,∀i∈Pj,(3)zik∩zjk=φ,∀i,j∈N,i<j,∀k∈M,(4)1-riwik+rieik≤1-ricik+rieik+xi,(5)1-ricik+rieik+xi≤Ek,(6)1-rieik+ricik≤1-rieik+ricik+yi,(7)1-rieik+ricik+yi≤Ck,(8)ri∈0,1.In the model, formula (1) is the objective of the problem, (2) proposes the precedence constraints, and (3) means that two cubes cannot overlap. Formulae (4)–(7) denote that each cube should be completed within available place. The cube can be rotated horizontally and 0 and 1 represent if the cube is rotated, as formula (8) has shown.


## 3. A Hybrid Heuristic Algorithm

### 3.1. Initial Solution Method

In this paper, we apply BLF to get the initial solution. BLF, presented by Chazelle [13] in 1983, belongs to heuristic algorithm. In this algorithm, the method of placing cubes is determined by corners [19].


#### 3.1.1. Corner

In BLF, it is important to find corners to place the activity. Firstly, we will try the lowest and leftmost point (lowest point first); if this placement can match the activity, then place it in the position and update corners; otherwise, try next point until a corner is found. The corners can be represented as{(x,y,t),(e,c,h)}, where (x,y,t) indicates the location of the corners and (e,c,h) represents the available space of the point in x-y-z dimensions. See Figure 1; E and C denote the length and width of the place and t represents the duration of the project.Figure 1
Corners.


#### 3.1.2. Bottom-Left-Fill Algorithm

In this paper, we represent the activities as cubes whose length, width, and height are limited. For these cubes, the length and width denote the length and width of the place they need, and the height represents the time they need. Meanwhile, we regard the unrestricted height as timelinet. When all activities have been placed, the total height equals the duration of the project. In the process, we find activities that can be placed at each time point first and then consider the sequence of these activities. We place the activity with larger bottom area first; if equal, choose the higher height; if still equal, select the one with the longer length. We describe the algorithm as follows.(1)
We embed the place (the platform in ship block construction space) in a three-dimensional coordinate system, put the bottom-left-rear point on the origin (0, 0, 0), and put length, width, and height onx, y, and t axis, respectively. E and C represent length and width of the place.(2)
Set 5 sets:An, Cn, Dn, I, and B. An is a set of activities which have been scheduled but not yet completed. Cn is a set of activities which have been scheduled and already completed. Dn is a set of activities which can be scheduled but have not been scheduled yet. I is a set of corners, while B is a set of all activities in input order.(3)
Move the activities which can be scheduled fromB to Dn and then sort these activities: firstly, interchange the length and width of the activities so that ei≥ci can be met for any activity bi; then sort the activities in Dn by placement policy mentioned above, and the first activity should be scheduled in Dn after being sorted. Detect the corners in I until the first eligible corner is found by t-y-x rule, which means that the smaller t among the corners is better. Then, consider the smaller y. Finally, select the smaller x. Put the bottom-left-rear point of the activity on the selected corner, and the new eligible corners will be new elements of I; meanwhile delete the corner which is used this time from I. Record the activities and their corners sequentially.(4)
If an activity inAn has been completed, move it from An to Cn and then move its nearest successor from B to Dn. Sort activities in Dn by rules mentioned in (3). Repeat (3) and (4) until all activities are completed.(5)
Select the highert of all corners as the duration of the project.


### 3.2. Optimization Solution Method

Proposed by Steinbrunn et al. [20], simulated annealing (SA) is a metaheuristic algorithm which offers a possibility to accept worse neighbor solutions to escape from local optimum. Until 1983, Kirkpatrick et al. [21] transformed this idea to SA arithmetic and applied it to traveling salesman problem successfully.Chan et al. [22] develop a hybrid algorithm which gleans the ideas both from tabu search and sample sort simulated annealing to solve distributed scheduling problem. Bouleimen and Lecocq [23] implemented SA to RCPSP and MRCPSP. Yannibelli and Amandi [24] combined SA and other algorithms to solve a multiobjective project scheduling problem. In SA arithmetic, we describe the neighborhood as the modification of the order of two activities which can be scheduled at the same time. dt represents temperature decreasing rate, L denotes the initial value of neighborhood, dL represents the neighbors that are generated once the temperature drops, f denotes current duration, fbest denotes the shortest duration till now. For our ship block construction space scheduling problem, the SA can be described as follows.(1)
Initialization: the initial and final temperature isSt and Et, respectively. The algorithm iterates from initial solution B. The value of initial evaluation function is f=3D-PS(B), while the evaluation function value of initial optimal solution Bbest=B is fbest=f.(2)
t denotes the current temperature and Lt denotes the length of current neighborhood. Initially t=St, Lt=L.(3)
j=1.(4)
Select a new solutionB′ from the neighborhood N(B) of B.(5)
Calculate the incrementaldf=f-f′.(6)
Ifdf>0, accept B′ as a new solution, f=f′, B=B′; if f′<fbest, then fbest=f′, Bbest=B′. Else accept B′ as a new solution with a probability P=exp⁡(10∗df/T).(7)
j=j+1, if j≤Lt, go to step (4); else go to step (8).(8)
Lt=dL, t∗=dt, and compare t and Et. If t≥Et, go to step (3); else the termination condition is met and output current fbest and Bbest; end the program.


## 3.1. Initial Solution Method

In this paper, we apply BLF to get the initial solution. BLF, presented by Chazelle [13] in 1983, belongs to heuristic algorithm. In this algorithm, the method of placing cubes is determined by corners [19].


### 3.1.1. Corner

In BLF, it is important to find corners to place the activity. Firstly, we will try the lowest and leftmost point (lowest point first); if this placement can match the activity, then place it in the position and update corners; otherwise, try next point until a corner is found. The corners can be represented as{(x,y,t),(e,c,h)}, where (x,y,t) indicates the location of the corners and (e,c,h) represents the available space of the point in x-y-z dimensions. See Figure 1; E and C denote the length and width of the place and t represents the duration of the project.Figure 1
Corners.


### 3.1.2. Bottom-Left-Fill Algorithm

In this paper, we represent the activities as cubes whose length, width, and height are limited. For these cubes, the length and width denote the length and width of the place they need, and the height represents the time they need. Meanwhile, we regard the unrestricted height as timelinet. When all activities have been placed, the total height equals the duration of the project. In the process, we find activities that can be placed at each time point first and then consider the sequence of these activities. We place the activity with larger bottom area first; if equal, choose the higher height; if still equal, select the one with the longer length. We describe the algorithm as follows.(1)
We embed the place (the platform in ship block construction space) in a three-dimensional coordinate system, put the bottom-left-rear point on the origin (0, 0, 0), and put length, width, and height onx, y, and t axis, respectively. E and C represent length and width of the place.(2)
Set 5 sets:An, Cn, Dn, I, and B. An is a set of activities which have been scheduled but not yet completed. Cn is a set of activities which have been scheduled and already completed. Dn is a set of activities which can be scheduled but have not been scheduled yet. I is a set of corners, while B is a set of all activities in input order.(3)
Move the activities which can be scheduled fromB to Dn and then sort these activities: firstly, interchange the length and width of the activities so that ei≥ci can be met for any activity bi; then sort the activities in Dn by placement policy mentioned above, and the first activity should be scheduled in Dn after being sorted. Detect the corners in I until the first eligible corner is found by t-y-x rule, which means that the smaller t among the corners is better. Then, consider the smaller y. Finally, select the smaller x. Put the bottom-left-rear point of the activity on the selected corner, and the new eligible corners will be new elements of I; meanwhile delete the corner which is used this time from I. Record the activities and their corners sequentially.(4)
If an activity inAn has been completed, move it from An to Cn and then move its nearest successor from B to Dn. Sort activities in Dn by rules mentioned in (3). Repeat (3) and (4) until all activities are completed.(5)
Select the highert of all corners as the duration of the project.


## 3.1.1. Corner

In BLF, it is important to find corners to place the activity. Firstly, we will try the lowest and leftmost point (lowest point first); if this placement can match the activity, then place it in the position and update corners; otherwise, try next point until a corner is found. The corners can be represented as{(x,y,t),(e,c,h)}, where (x,y,t) indicates the location of the corners and (e,c,h) represents the available space of the point in x-y-z dimensions. See Figure 1; E and C denote the length and width of the place and t represents the duration of the project.Figure 1
Corners.


## 3.1.2. Bottom-Left-Fill Algorithm

In this paper, we represent the activities as cubes whose length, width, and height are limited. For these cubes, the length and width denote the length and width of the place they need, and the height represents the time they need. Meanwhile, we regard the unrestricted height as timelinet. When all activities have been placed, the total height equals the duration of the project. In the process, we find activities that can be placed at each time point first and then consider the sequence of these activities. We place the activity with larger bottom area first; if equal, choose the higher height; if still equal, select the one with the longer length. We describe the algorithm as follows.(1)
We embed the place (the platform in ship block construction space) in a three-dimensional coordinate system, put the bottom-left-rear point on the origin (0, 0, 0), and put length, width, and height onx, y, and t axis, respectively. E and C represent length and width of the place.(2)
Set 5 sets:An, Cn, Dn, I, and B. An is a set of activities which have been scheduled but not yet completed. Cn is a set of activities which have been scheduled and already completed. Dn is a set of activities which can be scheduled but have not been scheduled yet. I is a set of corners, while B is a set of all activities in input order.(3)
Move the activities which can be scheduled fromB to Dn and then sort these activities: firstly, interchange the length and width of the activities so that ei≥ci can be met for any activity bi; then sort the activities in Dn by placement policy mentioned above, and the first activity should be scheduled in Dn after being sorted. Detect the corners in I until the first eligible corner is found by t-y-x rule, which means that the smaller t among the corners is better. Then, consider the smaller y. Finally, select the smaller x. Put the bottom-left-rear point of the activity on the selected corner, and the new eligible corners will be new elements of I; meanwhile delete the corner which is used this time from I. Record the activities and their corners sequentially.(4)
If an activity inAn has been completed, move it from An to Cn and then move its nearest successor from B to Dn. Sort activities in Dn by rules mentioned in (3). Repeat (3) and (4) until all activities are completed.(5)
Select the highert of all corners as the duration of the project.


## 3.2. Optimization Solution Method

Proposed by Steinbrunn et al. [20], simulated annealing (SA) is a metaheuristic algorithm which offers a possibility to accept worse neighbor solutions to escape from local optimum. Until 1983, Kirkpatrick et al. [21] transformed this idea to SA arithmetic and applied it to traveling salesman problem successfully.Chan et al. [22] develop a hybrid algorithm which gleans the ideas both from tabu search and sample sort simulated annealing to solve distributed scheduling problem. Bouleimen and Lecocq [23] implemented SA to RCPSP and MRCPSP. Yannibelli and Amandi [24] combined SA and other algorithms to solve a multiobjective project scheduling problem. In SA arithmetic, we describe the neighborhood as the modification of the order of two activities which can be scheduled at the same time. dt represents temperature decreasing rate, L denotes the initial value of neighborhood, dL represents the neighbors that are generated once the temperature drops, f denotes current duration, fbest denotes the shortest duration till now. For our ship block construction space scheduling problem, the SA can be described as follows.(1)
Initialization: the initial and final temperature isSt and Et, respectively. The algorithm iterates from initial solution B. The value of initial evaluation function is f=3D-PS(B), while the evaluation function value of initial optimal solution Bbest=B is fbest=f.(2)
t denotes the current temperature and Lt denotes the length of current neighborhood. Initially t=St, Lt=L.(3)
j=1.(4)
Select a new solutionB′ from the neighborhood N(B) of B.(5)
Calculate the incrementaldf=f-f′.(6)
Ifdf>0, accept B′ as a new solution, f=f′, B=B′; if f′<fbest, then fbest=f′, Bbest=B′. Else accept B′ as a new solution with a probability P=exp⁡(10∗df/T).(7)
j=j+1, if j≤Lt, go to step (4); else go to step (8).(8)
Lt=dL, t∗=dt, and compare t and Et. If t≥Et, go to step (3); else the termination condition is met and output current fbest and Bbest; end the program.


## 4. Simulation Experiment

We use a set of activities to verify our algorithm. The parameters of these activities are shown in Table1, and the network diagram of activities is presented in Figure 2. There are 2 places in the experiment, x, y, and t represent length, width, and time, respectively. The length and width of place 1 are 3 and 3, while 3 and 2 are for place 2.Table 1
The parameters of activities.
Activity
Duration
Length, width
Place
1
0
0, 0
1
2
8
2, 1
1
3
4
2, 2
1
4
6
2, 1
2
5
3
2, 2
2
6
8
2, 1
2
7
5
2, 1
2
8
9
3, 1
1
9
2
3, 2
1
10
3
1, 1
1
11
7
2, 2
1
12
2
2, 2
2
13
7
3, 1
1
14
9
2, 1
2
15
4
3, 2
1
16
6
2, 1
2
17
3
2, 1
1
18
0
0, 0
2Figure 2
The network diagram of activities.


### 4.1. Generation of Initial Solution

We get the initial solution as follows.(1)
At first,t=0. {2,3,4,5} can be arranged at this time. According to the rule above, we adjust the order to {3,5,2,4}. Activity 3 will be completed in place 1, so we put the bottom-left-rear point of it at the origin of place 1. So three new corners {(0,0,4),(3,3,∞)}, {(0,2,0),(3,1,∞)}, {(2,0,0),(1,3,∞)} are produced. Update An, Dn, I, Cn={1}, An={3}, Dn={5,2,4}, I1={{(2,0,0),(1,3,∞)},{(0,2,0),(3,1,∞)}, {(0,0,4),(3,3,∞)}}, I2={{(0,0,0),(3,2,∞)}}. See Figure 3.(2)
Next, activity 5 will be scheduled on place 2. We put the bottom-left-rear point of activity 5 at the origin of place 2. Then new corners{(0,0,3),(3,2,∞)}, {(0,2,0),(3,0,∞)}, {(2,0,0),(1,2,∞)} are produced. According to the rule, we delete {(0,2,0),(3,0,∞)}. Update An, Dn, I. Cn={1}, An={3,5}, Dn={2,4}, I1={{(2,0,0),(1,3,∞)},{(0,2,0),(3,1,∞)}, {(0,0,4),(3,3,∞)}}, I2={{(2,0,0),(1,2,∞)}, {(0,0,3),(3,2,∞)}}. See Figure 4.(3)
Detect the corners ofI1 and {(2,0,0),(1,3,∞)} is selected for activity 2. After activity 2 is scheduled, three new corners are produced and only {(2,0,8),(1,3,∞)} is eligible to be a corner. Considering that part of the space has been occupied by activity 2, we should retest the available space of previous corners when we update I1. {(0,0,4),(3,3,∞)} should be modified into {(0,0,4),(2,3,∞)}. Then Cn={1}, An={3,5,2}, Dn={4}, I1={{(0,2,0),(3,1,∞)},{(0,0,4),(2,3,∞)}, {(2,0,8),(1,3,∞)}}, I2={{(2,0,0),(1,2,∞)}, {(0,0,3),(3,2,∞)}}. See Figure 5.(4)
At time 0, activity 4 will be put in order. DetectI2 and put it on {(2,0,0),(1,2,∞)}. After testing, only {(2,0,6),(1,2,∞)} can be a new corner. Similarly, the available space of previous corners in I2 should also be retested and {(0,0,3),(3,2,∞)} should be changed into {(0,0,3),(2,2,∞)}. Cn={1}, An={3,5,2,4}, D=Ø,   I1={{(0,2,0),(3,1,∞)},{(0,0,4),(2,3,∞)}, {(2,0,8),(1,3,∞)}}, I2={{(0,0,3),(2,2,∞)}, {(2,0,6),(1,2,∞)}}. See Figure 6.(5)
At time 0, space is still available, but it is not enough for any remaining activity. So next time point ist=3, and activity 5 is completed at this time. Cn={1,5}, An={3,2,4}, Dn={14,15}. After ordering, Dn is changed into {15,14}. In order to arrange activity 15, we detect I1. If there is any corner whose value of t is less than 3, we should change it into 3 and modify available space of this corner. For example, {(0,2,0),(3,1,∞)} should be changed into {(0,2,3),(3,1,∞)} before activity 15 is put. Meanwhile, the space of this corner should be changed into {(0,2,3),(3,1,1)} after activity 15 is put. We lay activity 15 on {(0,0,4),(2,3,∞)}. Cn={1,5}, An={3,2,4,15}, Dn={14}, I1={{(0,2,3),(3,1,1)},{(0,0,8),(3,3,∞)}}, I2={{(0,0,3),(2,2,∞)},{(2,0,6),(1,2,∞)}}. See Figure 7.(6)
According to this train of thought, we get an initial solution{3(0,0,0)}, {5(0,0,0)}, {2(2,0,0)}, {4(2,0,0)}, {15(0,0,4)}, {14(0,0,3)}, {6(0,1,4)}, {7(2,0,6)}, {9(0,0,8)}, {8(0,2,8)}, {10(0,0,10)}, {11(1,0,11)}, {12(0,0,12)}, {16(2,0,12)}, {17(0,0,13)}, {13(0,0,18)}, in which {B(x,y,t)} means activity B should be started at time t, and the space it needs can be represented as (x,y). According to the initial solution, the whole duration of the project is 25. The status of place 1 and place 2 is shown in Figure 8.Figure 3
The status of place 1 while activity 3 is put.Figure 4
The status of place 2 while activity 5 is put.Figure 5
The status of place 1 while activity 2 is put.Figure 6
The status of place 2 while activity 4 is put.Figure 7
The status of place 1 while activity 15 is put.Figure 8
The status while all activities are put.
(a)
Place 1
(b)
Place 2


### 4.2. Optimization of Initial Solution

In SA, the order of activities has great influence on the duration of the project. So by searching the neighborhood and increasing the size of neighborhood dynamically, we manage to use SA and improve the initial solution.We show a step of improvement as follows.(1)
f=fbest=25, B=Bbest={3,5,2,4,15,14,6,7,9,8,10,11,12,16,17,13}.(2)
t=St, Lt=L.(3)
Ift≥Et, go to step (4); else output current fbest and Bbest; finish the program.(4)
j=1.(5)
Ifj>Lt, Lt+=dL, and go to step (4); else go to next step.(6)
SelectB′ from the neighborhood N(B) of B. In our example, we swap the order of activity 6 and activity 7. Then, we get another solution {3(0,0,0)}, {5(0,0,0)}, {2(2,0,0)}, {4(2,0,0)}, {15(0,0,4)}, {14(0,0,3)}, {7(0,1,4)}, {6(2,0,6)}, {9(0,0,8)}, {8(0,2,8)}, {10(0,0,10)}, {11(1,0,10)}, {16(0,0,12)}, {17(0,0,13)}, {12(0,0,18)}, {13(0,2,17)}. f′=24, B′={3,5,2,4,15,14,7,6,9,8,10,11,16,17,12,13}. df=f-f′=25-24=1. If df>0, go to step (7); else, go to step (8). The current df is 1, so go to step (7).(7)
Comparef′ and fbest, if f′<fbest, fbest=f′, Bbest=B′; else j=j+1 and go to step (5). In this example, f′<fbest, so fbest=24, Bbest={3,5,2,4,15,14,7,6,9,8,10,11,16,17,12,13}.(8)
Generate a numberx randomly, if x<exp⁡(10∗df/t), f=f′, B=B′, j=j+1, and go to step (5).After this improvement, the optimal solution reduces from 25 to 24. So it is proved that the method is effective.


## 4.1. Generation of Initial Solution

We get the initial solution as follows.(1)
At first,t=0. {2,3,4,5} can be arranged at this time. According to the rule above, we adjust the order to {3,5,2,4}. Activity 3 will be completed in place 1, so we put the bottom-left-rear point of it at the origin of place 1. So three new corners {(0,0,4),(3,3,∞)}, {(0,2,0),(3,1,∞)}, {(2,0,0),(1,3,∞)} are produced. Update An, Dn, I, Cn={1}, An={3}, Dn={5,2,4}, I1={{(2,0,0),(1,3,∞)},{(0,2,0),(3,1,∞)}, {(0,0,4),(3,3,∞)}}, I2={{(0,0,0),(3,2,∞)}}. See Figure 3.(2)
Next, activity 5 will be scheduled on place 2. We put the bottom-left-rear point of activity 5 at the origin of place 2. Then new corners{(0,0,3),(3,2,∞)}, {(0,2,0),(3,0,∞)}, {(2,0,0),(1,2,∞)} are produced. According to the rule, we delete {(0,2,0),(3,0,∞)}. Update An, Dn, I. Cn={1}, An={3,5}, Dn={2,4}, I1={{(2,0,0),(1,3,∞)},{(0,2,0),(3,1,∞)}, {(0,0,4),(3,3,∞)}}, I2={{(2,0,0),(1,2,∞)}, {(0,0,3),(3,2,∞)}}. See Figure 4.(3)
Detect the corners ofI1 and {(2,0,0),(1,3,∞)} is selected for activity 2. After activity 2 is scheduled, three new corners are produced and only {(2,0,8),(1,3,∞)} is eligible to be a corner. Considering that part of the space has been occupied by activity 2, we should retest the available space of previous corners when we update I1. {(0,0,4),(3,3,∞)} should be modified into {(0,0,4),(2,3,∞)}. Then Cn={1}, An={3,5,2}, Dn={4}, I1={{(0,2,0),(3,1,∞)},{(0,0,4),(2,3,∞)}, {(2,0,8),(1,3,∞)}}, I2={{(2,0,0),(1,2,∞)}, {(0,0,3),(3,2,∞)}}. See Figure 5.(4)
At time 0, activity 4 will be put in order. DetectI2 and put it on {(2,0,0),(1,2,∞)}. After testing, only {(2,0,6),(1,2,∞)} can be a new corner. Similarly, the available space of previous corners in I2 should also be retested and {(0,0,3),(3,2,∞)} should be changed into {(0,0,3),(2,2,∞)}. Cn={1}, An={3,5,2,4}, D=Ø,   I1={{(0,2,0),(3,1,∞)},{(0,0,4),(2,3,∞)}, {(2,0,8),(1,3,∞)}}, I2={{(0,0,3),(2,2,∞)}, {(2,0,6),(1,2,∞)}}. See Figure 6.(5)
At time 0, space is still available, but it is not enough for any remaining activity. So next time point ist=3, and activity 5 is completed at this time. Cn={1,5}, An={3,2,4}, Dn={14,15}. After ordering, Dn is changed into {15,14}. In order to arrange activity 15, we detect I1. If there is any corner whose value of t is less than 3, we should change it into 3 and modify available space of this corner. For example, {(0,2,0),(3,1,∞)} should be changed into {(0,2,3),(3,1,∞)} before activity 15 is put. Meanwhile, the space of this corner should be changed into {(0,2,3),(3,1,1)} after activity 15 is put. We lay activity 15 on {(0,0,4),(2,3,∞)}. Cn={1,5}, An={3,2,4,15}, Dn={14}, I1={{(0,2,3),(3,1,1)},{(0,0,8),(3,3,∞)}}, I2={{(0,0,3),(2,2,∞)},{(2,0,6),(1,2,∞)}}. See Figure 7.(6)
According to this train of thought, we get an initial solution{3(0,0,0)}, {5(0,0,0)}, {2(2,0,0)}, {4(2,0,0)}, {15(0,0,4)}, {14(0,0,3)}, {6(0,1,4)}, {7(2,0,6)}, {9(0,0,8)}, {8(0,2,8)}, {10(0,0,10)}, {11(1,0,11)}, {12(0,0,12)}, {16(2,0,12)}, {17(0,0,13)}, {13(0,0,18)}, in which {B(x,y,t)} means activity B should be started at time t, and the space it needs can be represented as (x,y). According to the initial solution, the whole duration of the project is 25. The status of place 1 and place 2 is shown in Figure 8.Figure 3
The status of place 1 while activity 3 is put.Figure 4
The status of place 2 while activity 5 is put.Figure 5
The status of place 1 while activity 2 is put.Figure 6
The status of place 2 while activity 4 is put.Figure 7
The status of place 1 while activity 15 is put.Figure 8
The status while all activities are put.
(a)
Place 1
(b)
Place 2


## 4.2. Optimization of Initial Solution

In SA, the order of activities has great influence on the duration of the project. So by searching the neighborhood and increasing the size of neighborhood dynamically, we manage to use SA and improve the initial solution.We show a step of improvement as follows.(1)
f=fbest=25, B=Bbest={3,5,2,4,15,14,6,7,9,8,10,11,12,16,17,13}.(2)
t=St, Lt=L.(3)
Ift≥Et, go to step (4); else output current fbest and Bbest; finish the program.(4)
j=1.(5)
Ifj>Lt, Lt+=dL, and go to step (4); else go to next step.(6)
SelectB′ from the neighborhood N(B) of B. In our example, we swap the order of activity 6 and activity 7. Then, we get another solution {3(0,0,0)}, {5(0,0,0)}, {2(2,0,0)}, {4(2,0,0)}, {15(0,0,4)}, {14(0,0,3)}, {7(0,1,4)}, {6(2,0,6)}, {9(0,0,8)}, {8(0,2,8)}, {10(0,0,10)}, {11(1,0,10)}, {16(0,0,12)}, {17(0,0,13)}, {12(0,0,18)}, {13(0,2,17)}. f′=24, B′={3,5,2,4,15,14,7,6,9,8,10,11,16,17,12,13}. df=f-f′=25-24=1. If df>0, go to step (7); else, go to step (8). The current df is 1, so go to step (7).(7)
Comparef′ and fbest, if f′<fbest, fbest=f′, Bbest=B′; else j=j+1 and go to step (5). In this example, f′<fbest, so fbest=24, Bbest={3,5,2,4,15,14,7,6,9,8,10,11,16,17,12,13}.(8)
Generate a numberx randomly, if x<exp⁡(10∗df/t), f=f′, B=B′, j=j+1, and go to step (5).After this improvement, the optimal solution reduces from 25 to 24. So it is proved that the method is effective.


## 5. Conclusion

In this paper, we combine BLF and SA to solve ship block construction space scheduling problem. During the procedure of scheduling activities, we guide the sorting process with corners. Then, the sorting of initial solution can be changed by SA. However, how to improve the searching efficiency will be the future research, especially when the number of blocks is very large.



---

*Source: 841637-2015-04-12.xml*