Behavior perception-based disruption models for berth allocation and quay crane assignment problems

Behavior perception-based disruption models for berth allocation and quay crane assignment problems

Computers & Industrial Engineering 97 (2016) 258–275 Contents lists available at ScienceDirect Computers & Industrial Engineering journal homepage: ...

4MB Sizes 0 Downloads 39 Views

Computers & Industrial Engineering 97 (2016) 258–275

Contents lists available at ScienceDirect

Computers & Industrial Engineering journal homepage: www.elsevier.com/locate/caie

Behavior perception-based disruption models for berth allocation and quay crane assignment problems Changchun Liu a, Li Zheng a, Canrong Zhang b,⇑ a b

Department of Industrial Engineering, Tsinghua University, Beijing 100084, China Logistics Engineering and Simulation Laboratory, Graduate School at Shenzhen, Tsinghua University, Shenzhen 518055, China

a r t i c l e

i n f o

Article history: Received 9 October 2015 Received in revised form 21 January 2016 Accepted 9 April 2016 Available online 19 April 2016 Keywords: Container terminals Berth allocation Quay crane assignment problem Disruption environment Prospect theory

a b s t r a c t Berth allocation and quay crane assignment problems are frequently encountered in container terminals and the scheduling problems usually exist in a disruption environment. This paper focuses on the rescheduling problem dealing with the disruption that a quay crane breakdowns unexpectedly in the middle of the execution of a planned schedule. Considering that the rescheduling action normally affect the conflicting objectives of port planner, vessel owners and crane operators, this paper aims to reschedule the system with the objective to minimize their negative deviation from the originally planned schedule. The problem is divided into two phases and the behavior perception-based disruption models are constructed for each phase based on prospect theory. Furthermore, an MIP-based relax-and-fix algorithm is proposed to obtain optimal solutions for Phase I and a dynamic programming technique is applied to solve Phase II. Finally, extensive numerical experiments are conducted to test the performance of the proposed models and solution approaches. Ó 2016 Elsevier Ltd. All rights reserved.

1. Introduction With the development of containerization, container terminals (CTs) play a more and more important role in the global transportation (Bierwirth & Meisel, 2015). Facing the fierce competition, CTs must provide a high-efficiency service to the calling vessels. Therefore, an appropriate schedule which can help terminal operators reduce operational costs and improve efficiency is needed. It is widely known that the construction cost of a berth is very high comparing to the investment costs for other facilities in the CTs (Park & Kim, 2003). Therefore, the berth is the most critical resource and numerous papers dealing with the application of operation research (OR) methods address seaside operations planning. One issue is berth allocation problem (BAP) which is to assign quay space and service time to vessels that have to be unloaded and loaded at a CT. The transshipment of containers between a vessel and the wharf is generally performed by quay cranes (QCs), which are mounted on rail tracks alongside the wharf. The assignment of these QCs to vessels and the work plans for the QCs addresses a further problem, namely the quay crane assignment problem (QCAP). QCAP and BAP are basically interrelated, because solving the QCAP can have a strong impact on the vessels’ opera⇑ Corresponding author. Tel.: +86 755 26036021. E-mail addresses: [email protected] (C. Liu), (L. Zheng), [email protected] (C. Zhang). http://dx.doi.org/10.1016/j.cie.2016.04.008 0360-8352/Ó 2016 Elsevier Ltd. All rights reserved.

[email protected]

tion times. The duration of berthing of a vessel depends on the number of QCs allocated to the vessel. When the number of QCs allocated to a vessel increases, the duration time is reduced. This is why BAP and QCAP are considered simultaneously. Numerous studies have been conducted regarding the improvement of the efficiency of BAP and QCAP. Many models and algorithms have been developed to optimize BAP and QCAP. However, during operation, the scheduling environment is full of uncertainties and CTs are therefore actually existed in the disruption environment (Zeng, Yang, & Hu, 2011). The planned schedules often have to be revised because of disruptions caused by severe weather, equipment failures, technical problems, machinery breakdowns and other unforeseen events. Once these disruptions happen, the initial plan may be infeasible, and modification of current or future schedules should be undertaken to minimize the negative impacts of the disruption, which is called disruption management (DM). Existing literatures, which we will review later in Section 2 always studied the deterministic problems. Although some papers, e.g., Han, Lu, and Xi (2010), Zhen, Lee, and Chew (2011a) and Zhen and Chang (2012), have considered the disruption such as the delay of arrival time, the deviation of operation time, to the best of our knowledge, the issue, considering the disruptions those have arisen due to the machinery breakdowns of QCs, has not been dealt with in other literature. Thus, this paper focuses on cases in which disruptions have arisen due to the

C. Liu et al. / Computers & Industrial Engineering 97 (2016) 258–275

machinery breakdowns of QCs. QCs are the major tools to unload and load containers from the vessels. Before making a schedule, it is often assumed that QCs can work regularly. However, machinery breakdowns of QCs commonly exist in actual operation. As a result of the machinery breakdowns of QCs, the original schedule cannot be executed as smoothly as anticipated which may even result in huge adjustment costs. Therefore, it is necessary to study the disruptions caused by the machinery breakdowns of QCs in seaside operations planning. A major issue in the planning and operations management of such system is to reschedule vessels so that the negative deviation from the originally planned schedule could be minimized. In practice, there are several reactive methods to reschedule vessels. For example, right-pushing (RP) strategy along the time-axis, but this method may cause chain reactions to other vessels; reschedule vessels with the same method which is adopted to generate the original schedule, but this way may lead to a schedule which is very different from the original schedule. Considering that the rescheduling action normally involves human beings’ behavioral performance, therefore, in this paper, we would like to take into account the effect of behavioral perception in the disruption model. Since a reschedule policy normally involves the profit of port planner, vessel owners and crane operators in practical world when the disruptions happen, it is important to contemplate their attitudes towards the disruptions while launching a reschedule policy. Pursuant to the prospect theory, one of the most famous behavioral economic theories, this paper intends to determine when and where the vessels should be moored and the detailed schedule for each QC while minimizing the negative deviation cost incurred by deviating from the originally planned schedule, taking into consideration of the port planner, vessel owners and crane operators’ perspectives. This paper is structured as follows: subsequent to the introduction provided herein; Section 2 reviews the related papers; Section 3 gives the the problem description; the original models and the behavior perception-based disruption models are presented in Section 4; Section 5 employs a relax-and-fix algorithm and a dynamic programming to solve the above problem in large-scale realistic environments; numerical experiments are conducted in Section 6 to validate the effectiveness and efficiency of the proposed method; and Section 7 draws the conclusions.

2. Literature review Since the early 1990s, CT operations have been intensively studied. For a comprehensive overview, please refer to the review work given by Vis and Koster (2003), Steenken, VoB, and Stahlbock (2004), Stahlbock and VoB (2008), Bierwirth and Meisel (2010) and Bierwirth and Meisel (2015). BAP and QCAP are widely studied and can be effectively modeled and efficiently solved. Imai, Nagaiwa, and Chan (1997) aimed to minimize not only waiting and operation times of the vessels but also the deviation between the arrival order and the service order. The problem can be reduced to a classical assignment problem, which is solved by the Hungarian method. Park and Kim (2003) discussed a method for scheduling berth and QCs and a two-phase solution is suggested for solving the proposed mathematical model. The first phase determines the berthing time and position as well as the number of QCs assigned to each vessel at each time segment and the second phase aims to construct a detailed schedule for QCs. It is noted that our model is similar to the model in Park and Kim (2003). Guan and Cheung (2004) considered the problem of allocating space at berth for vessels with the objective of minimizing total weighted flow time. Two mathematical formulations were considered where one is used to

259

develop a tree search procedure while the other is used to develop a lower bound that can speed up the tree search procedure. Cordeau, Gaudioso, Laporte, and Moccia (2007) formulated the service allocation problem as a generalized quadratic assignment problem. Liu, Wan, and Wang (2006) studied the problem of scheduling QCs at CTs where incoming vessels have different ready times. A heuristic decomposition approach is proposed to breakdown the problem into two smaller, linked models and two heuristic methods were developed. Imai, Chen, Nishimura, and Papadimitriou (2008) addressed efficient berth and crane allocation scheduling at a multi-user CT. A model is formulated for the simultaneous berth and crane allocation problem and a heuristic is developed by employing a genetic algorithm to find an approximate solution for the problem. Zhang, Zheng, Zhang, Shi, and Armstrong (2010) incorporated crane coverage ranges into a continuous berth allocation problem. They solved the problem by Lagrangian relaxation and sub-gradient optimization. The approach is evaluated in a case study for Tianjin Five Continents International Container Terminal, China. The other papers can refer to Lim (1998), Nishimura, Imai, and Papadimitriou (2001), Imai, Nishimura, and Papadimitriou (2001), Park and Kim (2002), Hansen and Oguz (2003), Kim and Moon (2003), Imai, Sun, Nishimura, and Papadimitriou (2005), Lee, Song, and Wang (2006), Wang and Lim (2007), Lokuge and Alahakoon (2007), Liang, Huang, and Yang (2008), Hansen, Oguz, and Mladenovic (2008), Chang, Yan, Chen, and Jiang (2008), Meisel and Bierwirth (2009), Zhen, Chew, and Lee (2011b) and Zhen and Chang (2012). Most of the researches presented above are concerned about how to obtain an initial schedule under a static and deterministic situation. However, the scheduling environment is full of uncertainties and CTs are therefore actually existed in the disruption environment. Han et al. (2010) addressed berth and QC scheduling problems in a simultaneous way, with uncertainties of vessel arrival time and container handling time. Zhen et al. (2011a) studied the BAP under uncertain arrival time or operation time of vessels. Later on, Zhen and Chang (2012) proposed a bi-objective model for the robust berth allocation scheduling, in which a heuristic based on the time buffer inserting method was proposed to solve the problem. Zhen (2014) studied the container yard template planning under uncertain maritime market and a model is proposed for yard template planning considering random numbers of containers that will be loaded onto vessels. Zeng et al. (2011) addressed the problem of recovering berth and QC schedules in CTs when disruptions occur after a subset of operations has been processed. Two strategies, namely, QC rescheduling strategy and berth reallocation strategy are proposed to tackle disruptions and recover the berth and QC schedule, and models for the two strategies are developed respectively. Contrary to the above papers, this paper will study the disruptions caused by the machinery breakdowns of QCs. Another important issue related to this paper is DM. Since DM was proposed, it has been applied in many fields, e.g., airline, supply chain, shipping, logistics and production scheduling. Clausen, Larsen, and Larsen (2010) provided a thorough review of the current state-of-the-art within airline DM of resources, including

Fig. 1. Two-phase procedure for berth and crane scheduling.

260

C. Liu et al. / Computers & Industrial Engineering 97 (2016) 258–275

Fig. 2. An illustration of the problem.

aircraft, crew, passenger and integrated recovery. Qi, Bard, and Yu (2004) investigated a one-supplier-one-retailer supply chain that experienced a disruption in demand during the planning horizon.

Wang, Ruan, and Shi (2012) developed a combinational disruption recovery model for vehicle routing problem with time windows, trying to handle a variety and a combination of delivery disruption

C. Liu et al. / Computers & Industrial Engineering 97 (2016) 258–275

events. Tang and Zhang (2009) investigated the scheduling problem of dealing with disruption caused by machine breakdown under the environment of identical parallel machines. Wang, Wang, and Liu (2011) considered parallel identical machines scheduling problems with a deteriorating maintenance activity and made a decision on when to schedule the deteriorating maintenance activities. In this paper, we will study DM in BAP and QCAP. Behavior in operations management is also an important issue relevant to this paper. Bendoly, Donohue, and Schultz (2006) provided a perspective on why behavioral research is critical to the operations management field. Boudreau, Hopp, and McClain (2003) probed the interface between operations and human resources by examining how human considerations affect classical operations management results. Gino and Pisano (2008) explored the theoretical and practical implications of incorporating behavioral and cognitive factors into models of operations management and suggested fruitful avenues for research in behavioral operations. In this paper, prospect theory is applied as a measure of human beings’ utility while launching a reschedule policy. Prospect theory is one of the most famous behavioral economic theories which is proposed in Kahneman and Tversky (1979). Now, it is often used into decision-making problems. Based on prospect theory, Wang, Dang, Pei, and Wang (2010) used a linear transformation operator to standardize the original decision-making information and get the positive and negative ideal scheme. Xu, Zhou, and Xu (2011) studied a rescheduling problem and developed a general travel decision-making rule utilizing prospect theory. It investigated the mechanism of travelers’ behavior, examines the probability of applying prospect theory as a measure of commute utility, and establishes a general utility measurement system. Jiang, Sun, Ding, and Zhang (2013) aimed to improve the theory of the decision-making in production scheduling by combining the behavioral perception with an optimization method in behavioral operations research. This paper addresses on cases in which disruptions caused the machinery breakdowns of QCs which commonly exists in actual operation. The issue to be studied in this paper is important in two aspects. Firstly, research suggests that papers found in the topic of DM for the BAP and QCAP with the multiple constraints presented in this paper are minimal, especially that there is no scholar studying the disruptions caused the machinery breakdowns of QCs. Secondly, literature for rescheduling problem for the BAP and QCAP considering the behavioral perception is limited. To our best knowledge, this issue has not been dealt with in other literature. Hence, it is noteworthy to study this issue.

3. Problem description As mentioned before, BAP and QCAP considered in this paper determine when and where the vessels should be moored and the detailed schedule for each QC. The problem can be divided into two phases as refer to Park and Kim (2003) which can be summarized as shown in Fig. 1. As shown in Fig. 1, the problem can be decomposed into two phases. Phase I, which we call it ‘‘Berth-Scheduling Phase”, determines the berth time and position and the number of QCs assigned to each vessel. Based on the results of Phase I, Phase II, which we call it ‘‘Crane-Assignment Phase”, generates a scheduling which includes the starting and ending times of the operation of each QC for each vessel to minimize the number of setups. Based on the two-phase procedure, an original scheduling can be generated. However, during the execution of the original sched-

261

ule, a QC may breakdown unexpectedly. As a result, a reschedule needs to be applied. The choice of reschedule policy may affect the feeling of port planner, vessel owners and crane operators all of whom naturally compare the rescheduled results with the original ones. It is important to contemplate their attitudes towards the disruptions while launching a reschedule policy. In order to overcome this problem, prospect theory is adopted. The following assumptions, which are reasonable in reality, are listed for the formulation of the problem. 1. Each vessel has a maximum and a minimum number of QCs to be assigned. The maximum number of QCs which can be simultaneously assigned to a vessel is limited by the length of the vessel and the minimum number is specified by the contract between the container terminals and the vessels. 2. In order to simplify the analysis, it is assumed that the duration of berthing for a vessel is inversely proportional to the number of QCs assigned to the vessel. The linearity of berthing time with the number of QCs may not be true. However, the linearity was assumed for the simplicity of the analysis and has little influence on the results. 3. Since the main focus of this paper is to study the behavioral performance of port planner, vessel owners and crane operators, therefore in order to illustrate the problem clearly, it is assumed that only one of the QCs may break down at a time and at most one disruption can take place during the whole time periods. Since the disruption has the relatively small probability of occurrence, it is virtually impossible that there are two or more disruptions at a time. If such a case happens, we just need to add a constraint which is similar to Constraint (46) to restrict it. Furthermore, if another disruption happens after rescheduling during the whole time periods, we just need to reschedule again. 4. The disruption lasts finitely long and the duration of the disruption and the recovery time is known. The time period is of discrete and we assume that the disruption period is multiple times of the unit time. To abate the error, time period should be as small as possible. The disruption duration may not be calculated accurately. However, repair workers can give an approximate recovery time according to their experience. Thus, this assumption is reasonable. An illustration of the problem is given in Fig. 2. Fig. 2(a) illustrates the output of the Phase I. Each rectangle represents the berthing scheduling of a vessel. The length of horizontal sides represents the lengths of the corresponding vessels and the position of a vertical side corresponds to the duration time from the starting to the ending time of the operation of a vessel. The numerical values on the left-hand of each rectangle denote the number of QCs assigned to each vessel at each time segment. Fig. 2(b) illustrates the output of the Phase II based on the results as the one in Fig. 2(a). In Fig. 2(b), specific QCs are assigned to each time segment for each vessel. In the example of Fig. 2(b), QCs 1–4 are assigned to vessel A for the first 5 time segments. For QC 3, it is assigned to vessel B at time segment 13, however, it stops serving vessel B to serve vessel E at time segment 14. Fig. 2(c) illustrates the case that the QC 2 breakdowns at time segment 7 and the duration of the disruption lasts 10 time segments and recoveries at time segment 17. This disruption which happens in the middle of the execution of a planned schedule will make the schedule be rescheduled. Based on the behavior perception-based disruption models presented in Section 4.2, a reschedule policy is generated which is similar to the results as shown Fig. 2(a) and (b). Contrary to the results in Fig. 2(a) and (b), QC 2 cannot work between time segment 7 and 16.

262

C. Liu et al. / Computers & Industrial Engineering 97 (2016) 258–275

4. Model formulation This section will introduce the original models which generate the original scheduling in Section 4.1 and the behavior perception-based disruption models which are formulated based on prospect theory in Section 4.2. Furthermore, BAP and QCAP are introduced, respectively. 4.1. Original models

position of a vessel to the location in the yard where containers for the corresponding vessel are stacked, the penalty cost incurred by berthing earlier or later than the expected arrival time, and the penalty cost incurred by the delay of the departure beyond the promised due time. A berthing earlier than the expected arrival time causes the vessel to speed up, which in turn causes the extra consumption of fuel and a berthing later than the expected arrival time may incur complaints from vessel owners. Besides, delayed departure of a vessel beyond the due time may lead to trouble in meeting the schedule at the next port. l X  þ c1k jBk  sk j þ c2k ðek  T k Þþ þ c3k ðT k  ek Þþ þ c4k ðC k  dk Þ

For the original model, it aims to obtain a scheduling which is executed by the port. Besides, the obtained scheduling is the reference when rescheduling the policy.

min

4.1.1. Phase I: Berth-scheduling phase This section shows a mathematical model for Phase I which is transformed based on the model proposed by Park and Kim (2003) and the following notations will be used for the formulation of the Phase I.

l X Y jk 6 c;

l m n ek ak

bk

dk sk c1k c2k c3k c4k lk mk c Bk Tk Ck Y jk

V jk hTkk0 hBkk0 M

The total number of vessels which is indexed by k The length of the wharf The planning horizon, the planning horizon is decomposed into n time segments which is indexed by j The expected arrival time of vessel k The total operation time of QCs, which is expressed as the number of crane-time segments, required to unload and load all the containers for vessel k The length of vessel k, this value includes the safety margin, which means the requested gap between adjacent vessels The due time for the departure of vessel k The desired berthing position with the lowest cost for vessel k The container handling cost per unit distance of vessel k between the yard and berth The penalty cost per unit time of arrival before ek for vessel k The penalty cost per unit time of arrival later ek for vessel k The penalty cost per unit time of delay beyond dk for vessel k The minimum number of QCs that can be assigned to vessel k The maximum number of QCs that can be assigned to vessel k The total number of available QCs (c P mk ) Decision variable. The berthing position of vessel k on the berth axis Integer decision variable. The start berthing time of vessel k on the time axis Integer decision variable. The completion time of vessel k which is equal to the maximum j such that Y jk > 0 plus one Integer decision variable. The number of QCs assigned to vessel k at time segment j. lk 6 Y jk 6 mk , if T k 6 j < C k ; 0, otherwise 1, if Y jk is positive; 0, otherwise 1, if the completion time C k of vessel k is earlier than the 0 arrival time of vessel k , which means vessel k is below ves0 sel k in the 2-dimensional time-berth plane; 0, otherwise 0 1, if vessel k is located on the left of vessel k along the 0 wharf, that is, located located on the left of vessel k in the 2-dimensional time-berth plane; 0, otherwise A large positive real number

Based on the above notations, Phase I can be formulated as follows. The objective function (1) is to minimize the total cost, which includes the transport cost depends on the distance form the berth

k¼1

ð1Þ The constraints are presented as follows.

8j

k¼1 n X

Y jk P ak ;

ð2Þ

8k

ð3Þ

j¼1

8j; k 8j; k ðj þ 1ÞV jk 6 C k ; 8j; k Y jk 6 mk V jk ;

ð4Þ

Y jk P lk V jk ;

ð5Þ ð6Þ

jV jk þ Mð1  V jk Þ P T k ; C k 6 T k0 þ Mð1 

8j; k

þ

hTk0 k

þ

hBkk0

Bk þ bk 6 m;

þ

hBk0 k

P 1;

2 f0; 1g;

ð8Þ

8k; k0 ; k – k0 0

8k; k ; k – k

8k

Bk ; T k ; C k ; Y jk P 0; V jk ; hTkk0 ; hBkk0

0

8k; k ; k – k

Bk þ bk 6 Bk0 þ Mð1  hBkk0 Þ; hTkk0

ð7Þ

0

hTkk0 Þ;

0

ð9Þ ð10Þ ð11Þ

8j; k

ð12Þ 0

8j; k; k ; k – k

0

ð13Þ

Constraint (2) restricts the maximum number of QCs utilized at a time segment which cannot beyond the total number of available QCs. Constraint (3) ensures that the total amount of handling operation for a vessel must be satisfied. Constraints (4) and (5) define variable V jk by relating it with Y jk and the number of QCs assigned to a vessel must be within lk and mk when V jk ¼ 1. Constraint (6) relates the departure time C k to V jk . Since V jk ¼ 1 if at least a QC serves vessel k at time segment j, that is between time j and j þ 1, the departure time of vessel k must be greater or equal to j þ 1. Constraint (7) relates the start berthing time T k to V jk . If V jk ¼ 1, the start berthing time of vessel k must be earlier or equal to j. Constraints (8)–(10) imply that the overlaps between vessels do not exist in the two-dimensional time-berth plane, which means the rectangle of each vessel in the two-dimensional timeberth plane has no overlaps each other. The constraint (11) implies that the berthing position of the schedule cannot exceed the range of the wharf. 4.1.2. Phase II: Crane-assignment phase Based on the results of the Phase I, this section constructs the scheduling for the individual QC. Suppose that V jk and Y jk is the output results of Phase I. Some additional notations will be presented. Z ijk 1, if QC i is assigned to vessel k at time segment j; 0, otherwise Lijk 1, if Z ijk  Z i1;jk P 1; 0, otherwise. This notation is used to indicate the left-most QC assigned to vessel k at time segment j Rijk 1, if Z ijk  Z iþ1;jk P 1; 0, otherwise. This notation is used to indicate the right-most QC assigned to vessel k at time segment j

C. Liu et al. / Computers & Industrial Engineering 97 (2016) 258–275

W ijk

1, if Z ijk  Z i;j1;k P 1; 0, otherwise. This notation is used to indicate that the QC assigned to vessel k has a new set-up at time segment j

Sij

1, if QC i has a new set-up at time segment j

c X n X Sij

ð14Þ

i¼1 j¼1

The constraints are presented one by one as follows. (1) Each QC is occupied by no more than one vessel per time segment. l X Z ijk 6 1;

8i; j

ð15Þ

k¼1

(2) Define Lijk such that

8j; k

L1jk  Z 1jk ¼ 0;

ð16Þ

Lijk ¼ 1 () Z ijk  Z i1;jk P 1;

8i ¼ 2; . . . ; c; 8j; k

ð17Þ

The ‘‘)” of logic constraint (17) is equivalent to the following inequality.

1  ðZ ijk  Z i1;jk Þ  Mð1  Lijk Þ 6 0;

8i ¼ 2; . . . ; c; 8j; k

The ‘‘(” of logic constraint (17) is equivalent to the following inequality.

Z ijk  Z i1;jk  M  Lijk 6 0;

8i ¼ 2; . . . ; c; 8j; k

Constraints (19) and (21) are similar to Constraint (17) and the linearizing transformations are similar to those as shown above. For brevity, the linearizing transformations for the those constraints will be omitted. (3) Similarly, define Rijk such that

8j; k

Rcjk  Z cjk ¼ 0;

Rijk ¼ 1 () Z ijk  Z iþ1;jk P 1;

ð18Þ

8i ¼ 1; . . . ; c  1; 8j; k

ð20Þ

8i; k; 8j ¼ 2; . . . ; n

ð21Þ

(5) Define Sij such that

Sij ¼

l X W ijk ;

8i; j

ð22Þ

k¼1

(6) All the QCs between the left-most and right-most QCs assigned to a vessel are all assigned to serve the vessel. This means that no QC between two QCs that have been assigned to the same vessel are idle. c X Lijk ¼ V jk ; i¼1 c X

Rijk ¼ V jk ;

i¼1 c X

Z ijk ¼ Y jk ;

4.2.1. Prospect theory Prospect theory is one of the most famous behavioral economic theories which is proposed by Kahneman and Tversky (1979). It describes the way that how people make their decision between probabilistic alternatives that involve risk. Most importantly, the prospect theory describes the real life choices of human being instead of the optimal decision. It states that people make their decisions based on the potential value of losses and gains rather than the final outcome by using certain heuristics. The main idea of the prospect theory can be presented in three parts. First of all, the majority of people are of loss aversion while facing gains; secondly, people appear to be risk preferred when facing loss; thirdly, human beings are more sensitive to loss rather than gain. Based on the above, prospect theory can be seen as an useful and important approach to determine the reschedule policy that involves human beings’ decision. Our following research is based on the prospect theory. Fig. 3 shows the S-shaped value function of the prospect theory. According to the figure, it indicates that when the outcome turns out to be at the gain effect, the value function appears to be concave; otherwise, it is convex. The following value function can be presented in Eq. (26) below. Note that the a and b are the risk performance parameters, while the k is the loss aversion parameter.

 VðxÞ ¼

8i; k

W ijk ¼ 1 () Z ijk  Z i;j1;k P 1;

The rescheduling action normally involves human beings behavioral performance. Therefore, this section would like to formulate the disruption models taking into account the effect of behavioral perception. Since a reschedule policy normally involves the profit of port planner, vessel owners and crane operators in practical world when the disruptions happen. It is important to contemplate their attitudes while launching a reschedule policy. In order to illustrate the human behavioral performance, we would like to introduce briefly the prospect theory first.

ð19Þ

(4) Define W ijk such that

W i1k  Z i1k ¼ 0;

Based on the above model, the detailed scheduling for individual QC is obtained. 4.2. Behavior perception-based disruption models

Based on the above notations, Phase II can be formulated as follows. The objective function (14) is to minimize the total number of set-ups for QCs to start to transfer operation of vessels.

min

263

8j; k

ð23Þ

8j; k

ð24Þ

8j; k

ð25Þ

xa ;

for x P 0

kðxÞb ; for x < 0

According to the prospect theory, we understand that people care only about the difference between the outcomes of their decision. Therefore, it is essential to have a reference point O to determine whether the outcome is a gain or a loss. Thus, the originally planned schedule is naturally our reference point in this paper. Since human perception is normally subjective and fuzzy, therefore, we have to make fuzzy processing to the value function. In the fuzzy logic, membership function represents the degree of

i¼1

Constraints (23) and (24) ensure that there is only one leftmost and one right-most QC for each vessel at time segment j if V jk ¼ 1. Constraint (25) satisfied the demand of QCs of vessel k at time segment j.

ð26Þ

Fig. 3. S-shaped value function.

264

C. Liu et al. / Computers & Industrial Engineering 97 (2016) 258–275

truth during the valuation. As a generalization of the indicator function in classical sets, the value of membership function can be obtained from the interval ½0; 1; instead of taking only figures 0 and 1. Thus, it is clearly an extension of the indicator function. In this paper, we only consider the scenario that loss arises after rescheduling. This is because people are unlikely to argue about the outcome of gaining. Therefore, assuming if the loss value is equal or larger than a maximum figure, the membership function takes 1, while the membership function takes value between 0 and 1 if the loss value is lower than the maximum value; however if the outcome turns out to be gain effect, the membership function takes 0 instead. To illustrate the situation above, the following calculation steps are listed below. Let x0 be the reference point, hence according to the loss situation of the value function (26) in prospect theory, we have

n o lðxÞ ¼ Vðx þ x0 Þ ¼  k½ðx þ x0 Þb ¼ kðx  x0 Þb When

4.2.2. Phase I: Berth-scheduling phase This section will introduce the disruption model for Phase I based on the prospect theory. For Phase I, it involves the profit of port planner and vessel owners. From the port planner’ perspective, the increment of total cost which includes the transport cost and penalty cost after rescheduling implies the loss of the port planner, and so the increment should be as small as possible. However, from the vessel owners’ perspective, the increment of time deviation, which includes deviation between the berthing time and the expected arrival time and the delay of the departure beyond the promised due time, are the most concern after rescheduling. Suppose that the original schedule can be represented by Bk ; T k ; C k and Y jk and the schedule after rescheduling can be represent by Bk ; T k ; C k and Y jk . Therefore, the total cost of the original schedule and the new schedule can be presented by Eqs. (28) and (29), respectively. l X 

þ

þ

c1k jBk  sk j þ c2k ðek  T k Þ þ c3k ðT k  ek Þ þ c4k ðC k  dk Þ

þ

ð28Þ c1k jBk  sk j þ c2k ðek  T k Þþ þ c3k ðT k  ek Þþ þ c4k ðC k  dk Þ

8 > > 1; > > <

DTC >

 b1 1 k1

1

> k1 ðDTCÞb1 ; 0 6 DTC < > > > : 0; DTC 6 0

 b1 1 k1

ð34Þ

1

8 > > 1; > > <

DTDk >

 b1 1 k2

> k2 ðDTDk Þb2 ; 0 6 DTDk < > > > : 0; DTDk 6 0

2

 b1 1 k2

ð35Þ

2

Thus, the objective (36) is to minimize the negative deviation cost caused by deviating from the originally planned schedule in consideration of the port planner and vessel owners’ perspectives, or in other words, to determine Bk ; T k ; C k and Y jk by minimizing the sum of both membership functions of port planner and vessel owners for the time period.

min c  lðTC ns Þ þ ð1  cÞ 

Pl k¼1

lðTDns k Þ

ð36Þ

l

where a coefficient c is defined to make a tradeoff between the profit of port planner and vessel owners. However, because lðTC ns Þ and lðTDns k Þ are piecewise nonlinear functions, therefore we could not solve the optimization problems involving these functions. Firstly, we divided the membership function into five grades as shown in Fig. 4. In the following, we describe the grade specification for lðTC ns Þ in detail. Grade 0

lðTC ns Þ ¼ 0, when TC ns 6 TC os Grade 1 lðTC ns Þ ¼ 0:125, TC os þ ð4k11 Þ

when

0 < lðTC ns Þ 6 0:25

with

TC os < TC ns 6

1 b1

Grade 2 1

k¼1

l X 

ð33Þ

For the owner of vessel k,

lðRÞ ¼ 1, then R ¼ x0 þ ð1kÞ . Thus membership function

Therefore, the introduction of the membership function above gives the foundation of obtaining the objective function of the behavior perception-based disruption models in this paper.

TC ns ¼

lðTC Þ ¼ ns

lðTDns k Þ ¼

ð27Þ

8k

Based the membership function (27), we can obtain the negative deviation cost caused by deviating from the originally planned schedule in consideration of the port planner and vessel owners’ perspectives. For the port planner,

1 b

8 xPR > < 1; lðxÞ ¼ kðx  x0 Þb ; x0 6 x < R > : 0; 0 6 x < x0

TC os ¼

os DTDk ¼ TDns k  TDk ;

lðTC ns Þ ¼ 0:375, when 0:25 < lðTC ns Þ 6 0:5 with TC os þ ð4k11 Þb1 < 1

TC ns 6 TC os þ ð2k11 Þb1

þ

k¼1

ð29Þ Thus, the increment of the total cost can be presented by Eq. (30).

DTC ¼ TC ns  TC os

ð30Þ

For each vessel’ time deviation of the original schedule and the new schedule can be presented by Eqs. (31) and (32), respectively. þ

8k

ð31Þ

þ

8k

ð32Þ

  TDos k ¼ jek  T k j þ ðC k  dk Þ ;

TDns k

¼ jek  T k j þ ðC k  dk Þ ;

Thus, the increment of the time deviation for vessel k can be presented by Eq. (33).

Fig. 4. Grade specification of the membership function.

265

C. Liu et al. / Computers & Industrial Engineering 97 (2016) 258–275

Grade 3 1

lðTC ns Þ ¼ 0:75, when 0:5 < lðTC ns Þ 6 1 with TC os þ ð2k11 Þb1 < TC ns 6 R ¼ TC os þ ðk11 Þ

1 b1

Grade 4

ts

Firstly, Some additional notations will be presented. The starting time of the disruption

tr

The starting time of the reschedule

Nt

Number of disruption time segments

1 b1

lðTC ns Þ ¼ 1, when TC ns > R ¼ TC os þ ðk11 Þ . Secondly, we represent these piecewise linear functions in linear functions by using 0–1 variables. We denote ~ e ¼ ½e0 ; e1 ; 1 1 1 f ¼ ½f ; e2 ; e3 ; e4  ¼ ½0; TC os ; TC os þ ð 1 Þb1 ; TC os þ ð 1 Þb1 ; TC os þ ð 1 Þb1 ; ~ 4k1

k1

2k1

0

f 1 ; f 2 ; f 3 ; f 4  ¼ ½0; 0:125; 0:375; 0:75; 1 and auxiliary variables X i , where i is the grade. Thus, we can linearize the model using the Constraints (37)–(40).

lðTC ns Þ ¼

4 X f iXi

ð37Þ

i¼0

TC ns P ei X i ;

i ¼ 0; 1; . . . ; 4

ð38Þ

4 X Xi ¼ 1

ð39Þ

i¼0

X i 2 f0; 1g;

i ¼ 0; 1; . . . ; 4

ð40Þ

For the vessel owners and crane operators, the linearizing transformations are similar to those as shown above. For brevity, the linearizing transformations for the those constraints will be omitted. 4.2.3. Phase II: Crane-assignment phase This section will introduce the disruption model for Phase II. For Phase II, it involves the profit of crane operators. From the crane operators, they are very reluctant to make too many setups. Thus, for their perspective, the increment of setups is the most concern after rescheduling. Suppose that the original schedule of crane assignment can be represented by Z ijk and Sij and the schedule after rescheduling can be represent by Z ijk and Sij . Therefore, the increment of the setups number for QC i can be presented by Eq. (41). os DASi ¼ ASns i  ASi ¼

n n X X Sij  Sij ; j¼1

8i

lðASns i Þ ¼

DASi >

 b1 1 k3

> k3 ðDASi Þb3 ; 0 6 DASi < > > > : 0; DASi 6 0

min

i¼1

l

ðASns i Þ

c

Y jk ¼

Y jk ;

Z i0 jk ¼ 0;

8T k 6 tr

ð44Þ

8j 6 t r

ð45Þ

8t r 6 j < t r þ Nt

ð46Þ

4.2.4.2. Mode 2: RALAP. However, there is another frequent method to handle the rescheduling problem of the disruption. RALAP is the case that we reschedule the whole system when the disruption finishes while the unaffected schedules are being executed as is during the disruption (tr ¼ t s þ N t ). Hence, it is obvious that scenario RALAP could cause a different outcome and reschedules policy. In this mode, it is unnecessary to know the recovery time of disruption. Therefore, we would like to compare both scenarios in this paper. As for RALAP, the schedule before tr is also executed as the original schedule which can be presented as Constraints (44) and (45). In addition, the schedule between t s and t r assigned for crane i must not be completed. Thus, we must added it on ak . Sup0 pose that crane i is the broken crane, then the total operation time P r 1 of cranes for vessel k is a0k ¼ ak þ tj¼t Z i0 jk . The objective function is s conducted as the same way as RASAP. 5. Solution approach

3

 b1 1 k3

3

ð42Þ

The objective (43) is to minimize the negative deviation cost caused by deviating from the originally planned schedule in consideration of crane operators’ perspectives, or in other words, to determine Z ijk and Sij by minimizing the membership functions of crane operators.

Pc

Bk ¼ Bk ; T k ¼ T k ;

ð41Þ

j¼1

Based the membership function (27), we can obtain the negative deviation cost caused by deviating from the originally planned schedule in consideration of the crane operators’ perspectives.

8 > > 1; > > <

4.2.4.1. Mode 1: RASAP. RASAP is the case that we reschedule the whole system as soon as the disruption takes place (t r ¼ ts ). This is very common in real world since plenty of people tend to do something to the system while the disruptions happen. Therefore, it is significant to look into the effect of RASAP. In RASAP, the schedule before tr is executed as the original schedule which can be presented as Constraints (44) and (45). The schedule after tr can be obtained by replaced the objective function (1) by the objec0 tive function (36). And suppose that QC i is the broken crane, thus, 0 QC i cannot work between tr and tr þ N t . We use Constraint (46) to restrict the capacity of QC.

ð43Þ

4.2.4. Two modes of rescheduling For the rescheduling mode of Phase I, we introduce two modes according to different time points when to start to reschedule: reschedule as soon as possible (RASAP) and reschedule as late as possible (RALAP). For Phase II, it is solved based on the results of Phase I. It has no difference between RASAP and RALAP.

The BAP has been shown to be an NP-hard problem by relating BAP to the set partitioning problem (Lim, 1998), the single machine scheduling problem with release dates (Hansen & Oguz, 2003) and the two dimensional cutting stock problem (Imai et al., 2005). The problem studied in this paper is more complex than BAP. Thus, the problem studied is NP-hard. Due to the NP-hardness, the largescale problem is hard to solve by a commercial software. This paper employs a MIP-based relax-and-fix algorithm proposed by James and Almada-Lobo (2011) to solve Phase I and a dynamic programming technique is applied to solve Phase II. 5.1. Relax-and-fix algorithm for Phase I 5.1.1. Basic idea Adopting the MIP-based fix-and-relax algorithm is motivated 2

by the fact that a great number ((2l þ nl) in total) of binary variables hTkk0 ; hBkk0 ; V jk take most of the computational effort when invoking the MIP solver. To overcome this drawback, most of the binary variables are fixed first leading to a modified problem whose remaining variables can be solved easily by an MIP solver. Then the binary variables which are fixed first are updated, leading to another modified problem which can also be solved by a MIP solver. The whole process is repeated until the termination condition is met. We can also find that the number of vessels (l) has a

266

C. Liu et al. / Computers & Industrial Engineering 97 (2016) 258–275

Fig. 5. Relax-and-fix algorithm description.

Table 1 Parameters determining for relax-and-fix algorithm. Parameters

Objective

CPU time (s)

x

q



Avg

S2

jTj

Avg

S2

3 3 3 5 5 5 8 8 8 10 10 10 10

0 1 2 0 2 4 2 4 6 1 3 5 7

0.00 0.00 0.00 0.05 0.05 0.05 0.10 0.10 0.10 0.15 0.15 0.15 0.15

289 338 244 375 256 336 321 205 258 387 349 324 301

64 106 42 100 62 114 65 43 59 81 109 77 95

25.64 34.37 13.39 44.87 15.70 33.12 35.22 – 16.63 51.55 36.81 34.46 25.92

76 87 132 276 276 548 297 496 1042 521 664 2467 731

1 1 3 11 13 37 30 46 351 77 54 967 46

The bold values mean the most appropriate combination.

2

great influence on the number of binary variables (l ), thus, we modify the problem from the dimension of the vessel number. There are three keywords for the relax-and-fix algorithm proposed by James and Almada-Lobo (2011), which are ‘relax’, ‘optimize’ and ‘fix’. First of all, the basic idea of the algorithm is that we decompose the planning horizon into a number of smaller intervals, and here we decompose the vessels instead of the planning horizon into several groups. Then, we start to optimize the variables from the beginning of those groups, while relaxing the variables for the remaining groups. After obtaining the solution for the first group, we move to the next group and optimize the variables, while fixing the variables of the previous groups and relaxing the variables for the remaining groups. This shifts forward strategy is used until variables of the problem are optimized. To be more specific, a diagram of this algorithm is presented in Fig. 5. According to Fig. 5, let x be amount of vessels for the current iteration and q be the number of overlapped vessels whose binary variables are determined from the previous iterations but are to be resolved. Note that using the overlapped vessels q aims to obtain better solutions and smoothen the solutions between the successive iterations. The solution of the previous iteration has a great effect on the solution of the current iteration. In order to reduce the influence of the previous iteration and improve the quality of the solution, q is adopted. For example in Table 1 the objective value tends to decrease with the increasing of q with a fixed x. However, with consideration of the computational time, q cannot be too large. Thus, an appropriate q must be determined. l m x The total number of iterations is TI ¼ N xq þ 1. Let nt and ne indicate the starting number and end number of the vessels, respectively. Then, the binary variables within the interval ðnt ; ne Þ are to be optimized in the current iteration, while the subset of

Fig. 6. The framework of the relax-and-fix algorithm.

the binary variables up to vessel nt  1 are fixed and the subset from vessels ne þ 1 to N are relaxed to be real numbers. 5.1.2. Procedure Observe the model of BAP, we can find once Bk ; T k and Y jk are given, the other variables are fixed. Thus, to determine the berth schedule for vessel k, it is sufficient to determine Bk ; T k and Y jk . In order to illustrate the relax-and-fix algorithm, we need to introduce an auxiliary parameter wk and several constraints to indicate whether the decision variables Bk ; T k and Y jk are fixed to Bk ; T k and Y jk or not, where Bk ; T k and Y jk are the optimal solutions obtained in previous iterations. The following constraints are given:

Bk ð1  wk Þ ¼ Bk ð1  wk Þ;

8k

ð47Þ

T k ð1  wk Þ ¼ T k ð1  wk Þ;

8k

ð48Þ

Y jk ð1  wk Þ ¼ Y jk ð1  wk Þ;

8j; k

ð49Þ

For example, if wk is equal to 0, the decision variables Bk ; T k and Y jk are fixed to Bk ; T k and Y jk , respectively. However, if wk ¼ 1, the decision variables Bk ; T k and Y jk are not fixed to Bk ; T k and Y jk and will need to be optimized in the current iteration. Accordingly, the ultimate problem called SubMIPModel is presented as bellow. The relax-and-fix algorithm for our model can be described in Fig. 6. And note that the CPLEX 12.6 optimization package has been applied as the MIP solver to compute the SubMIPModel for vessels nt to ne . For the example in Fig. 5, x ¼ 3 and q ¼ 1. The procedure is executed as follows. In the first iteration, vessels 1, 2 and 3 are inserted into the plane within their searching space and we can n o obtain an solution ðB1 ; T 1 ; Y~1 Þ; ðB2 ; T 2 ; Y~2 Þ; ðB3 ; T 3 ; Y~3 Þ , where Y~k ¼ ½Y 1k ; Y 2k ; . . . ; Y nk . Thus, we can obtain the schedule for vessels 1 and 2. In the second iteration, we solve the SubMIPModel for vessels 3, 4 and 5 to obtain the schedule for vessels 3 and 4. By repeating this operation, we can obtain a schedule for all l vessels. The SubMIPModel is solved by CPLEX which will consume a long computational time. In order to solve these problems quickly, a relaxed optimality gap is given. As an example, an instance with 10 vessels is solved by CPLEX. Since the trend for each iteration is similar, we simply illustrate the gap values and upper and lower

C. Liu et al. / Computers & Industrial Engineering 97 (2016) 258–275

267

Fig. 7. Convergence speed of CPLEX slows down ‘‘Exponentially”.

Fig. 8. An illustration of results of the berth scheduling problem (6 vessels and 6 cranes).

bounds for one iteration in Fig. 7. It shows that the algorithm converges quickly at the initial stage and is able to reach a small gap within a relatively short time, but after that it takes much longer time to reach the optimality. However, in practice, rather than spending great efforts on finding the optimal solution, it is more useful that we obtain a feasible solution in a reasonable time by knowing how far it is from optimality, i.e. -optimal solution, where  is the gap between the best integer solution and the lower bound. In this paper  is used to reduce the computational efforts spent after the -optimality is achieved. 5.2. Dynamic programming for Phase II For Phase II, it can be solved by formulating it as a dynamic programming with the objective to minimize the negative deviation cost. Note that the number of QCs assigned to a vessel at each time segment has already been determined in BAP and Fig. 8 illustrates the results of Phase I. Two types of events can be used to define the stages for dynamic programming. One is the arrival of a vessel such as Stage 1, 2, 3, 4 and 6 in Fig. 8. The other one is changing of the number of QCs assigned to a vessel such as Stage 5 and 7 in Fig. 8. Therefore, the time when either event occurs is considered as a ‘‘stage” of dynamic programming. The state of dynamic programming can be expressed by the sequence of the left-most QCs assigned to each vessel that is berthing at the stage. For example, in Fig. 8, there are

7 stages. In Fig. 9, the states of the first, second and third stages are (1), (1, 5) and (1, 5), respectively. The QCAP in Fig. 8 can be represented by the network shown in Fig. 10. From the initial node ðSÞ to the terminal ðTÞ, there are 7 stages and the nodes represent the states of the stage. The recursive equation of the dynamic programming for QCAP can be written as follows.

Sn;i ¼ min½Sn ðj; iÞ þ Sn1;j  j

ð50Þ

where Sn;i is the minimum total number of setups from stage 1 through stage n under the condition that the state of stage n is i for the original schedule. And Sn ðj; iÞ is the number of setups when the states at stage n  1 and n are j and i, respectively. For the new schedule, Sn;i is the minimum total negative deviation cost caused by the increment of setups number from stage 1 through stage n under the condition that the state of stage n is i. In order to reduce the solution space of dynamic programming, a proposition is proposed. Before describing the proposition, a definition is given as follows. Definition 1. Saturated state: defined as the situation when all the available QCs are assigned to the corresponding vessels. For example, in Fig. 10, there are 3 saturated states which are colored red, e.g., (1,5), (1,4) and (1,4) in stages 3, 4 and 6, respectively. Based Definition 1, Proposition 1 is given as follows.

268

C. Liu et al. / Computers & Industrial Engineering 97 (2016) 258–275

Fig. 9. The final solution for the example problem in Fig. 8 for original schedule.

Fig. 10. A network representation of the crane assignment problem shown in Fig. 8.

Proposition 1. The optimal solution between two adjacent saturated states must be a part of the optimal solution for the global problem. For example, in Fig. 10, between (1,4) and (1,4) in stages 4 and 6, the optimal path ð1; 4Þ ! ð3Þ ! ð1; 4Þ must be a part of the optimal path of the problem. By inspection we can easily prove Proposition 1 is true. Based on Proposition 1, we can divide the example in Fig. 10 into four sub-problems: S to stage 3, stage 3 to stage 4, stage 4 to stage 6 and stage 3 to T. Thus, the problem can be more easily calculated than before. The heavy line in Fig. 10 is the optimal path. And the optimal path ðSÞ ! ð1Þ ! ð1; 5Þ ! ð1; 5Þ ! ð1; 4Þ ! ð3Þ ! ð1; 4Þ ! ð3Þ ! ðTÞ, is shown in Fig. 9. The total number of setups is 20 (3 þ 2 þ 4 þ 3 þ 1 þ 6 þ 1). 6. Numerical experiments 6.1. Generate problem instances The instance data in this paper refers to Park and Kim (2003). In Park and Kim (2003), Pusan Eastern Container Terminal (PECT) in Pusan (Korea) is used as the physical model for the numerical experiment. The length of the wharf is 1200 m and there are 11 QCs. The unloading and loading operations for a vessel is performed by 2–5 cranes, which means lk ¼ 2; mk ¼ 5; 8k. The port planners make a schedule once per week. We set n ¼ 300 and m ¼ 120. The real size of a square in Fig. 2 corresponds to 10 m–1 h in the berth-time plane. The arrival time of vessels, the operation time of vessels, the length of vessels, and the desired berthing position for vessels are randomly generated from a uniform distribution of Uð1; 170Þ; Uð10; 48Þ; Uð15; 35Þ, and

Uð1; 120Þ, respectively. An instance with 40 vessels is as shown in Table 5. For the following experiments, k1 ; k2 ; k3 ; b1 ; b2 ; b3 and c are set to 0.05, 0.2, 0.2, 0.5, 0.8, 0.8 and 0.5, respectively. For all k, the cost coefficient c1k ; c2k ; c3k , and c4k is assumed to be 1, 1, 1, and 2, respectively. For the numerical experiment, all programs are coded in JAVA and run on a computer with a CPU of 2.0 GHz and an RAM of size equal to 1.0 GB. 6.2. Determine the parameters of the relax-and-fix algorithm It is necessary to investigate the computing speed (CPU time) of the proposed relax-and-fix algorithm. The CPU time is influenced by many factors, e.g., the number of vessels (l), the amount of vessels for the each iteration (x) and the overlapped vessels to be resolved (q). However, the first factor is the character of the problem and it is determined by the scale of the instances. Thus x and q are two important parameters in the proposed approach and it needs to find an appropriate combination of x and q for the proposed method which can consider both the quality of the solution and the CPU time. In this experiment, 10 instances with 40 vessels generated according the rule introduced in Section 6.1 are used to be tested. For the problem, we solve it with different x (3, 5, 8 and 10) and the corresponding q with different . It is noted that, one iteration will consume long computational time if x is larger than 10 and we neglect those combinations with a larger x. Each instance is solved 10 times. We calculate the average values (avg) and sample variance (S2 ) of 10 instances as to these combinations (x and q) respectively and the results are as shown in Table 1.

C. Liu et al. / Computers & Industrial Engineering 97 (2016) 258–275 Table 2 Comparisons between relax-and-fix algorithm and LRSO. No.

l

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50

20 20 20 20 20 20 20 20 20 20 25 25 25 25 25 25 25 25 25 25 30 30 30 30 30 30 30 30 30 30 35 35 35 35 35 35 35 35 35 35 40 40 40 40 40 40 40 40 40 40

Average:

Relax-and-fix

LRSO

Gap

Time (s)

Obj

Time (s)

UB

LB

Obj=UB

Obj=LB

134 116 139 161 317 147 119 287 62 124 122 158 331 265 562 365 234 114 236 185 228 516 536 351 704 312 174 419 203 409 665 631 453 451 381 365 571 506 338 441 795 652 516 632 769 537 486 560 302 618

109 65 145 145 59 71 124 116 38 95 86 142 92 79 139 128 91 76 174 116 101 201 177 209 275 271 79 195 125 397 178 352 140 262 225 187 297 257 266 184 298 262 234 170 138 184 205 235 204 334

297 262 190 265 271 287 332 327 198 278 375 356 371 298 482 341 279 320 389 277 489 845 784 489 578 456 378 512 376 489 893 912 671 712 581 729 1023 962 629 715 1578 1035 1278 992 1342 783 591 1049 1317 892

107 64 129 139 61 69 120 111 39 92 85 133 92 80 133 125 90 77 166 112 99 197 174 201 270 265 78 189 120 378 169 330 135 247 220 182 290 239 252 174 279 245 211 161 130 172 191 223 192 317

94 56 117 121 54 61 107 99 35 84 77 119 84 72 121 111 82 70 152 103 90 178 161 183 257 250 70 175 109 340 154 304 122 231 209 171 278 215 239 162 261 221 199 144 123 157 174 209 173 302

1.019 1.016 1.124 1.043 0.967 1.029 1.033 1.045 0.974 1.033 1.012 1.068 1.000 0.988 1.045 1.024 1.011 0.987 1.048 1.036 1.020 1.020 1.017 1.040 1.019 1.023 1.013 1.032 1.042 1.050 1.053 1.067 1.037 1.061 1.023 1.027 1.024 1.075 1.056 1.057 1.068 1.069 1.109 1.056 1.062 1.070 1.073 1.054 1.063 1.054

1.160 1.161 1.239 1.198 1.093 1.164 1.159 1.172 1.086 1.131 1.117 1.193 1.095 1.097 1.149 1.153 1.110 1.086 1.145 1.126 1.122 1.129 1.099 1.142 1.070 1.084 1.129 1.114 1.147 1.168 1.156 1.158 1.148 1.134 1.077 1.094 1.068 1.195 1.113 1.136 1.142 1.186 1.176 1.181 1.122 1.172 1.178 1.124 1.179 1.106

374

175

605

167

154

1.039

1.138

269

It can be observed that the objective has the smallest value when x ¼ 8; q ¼ 4 and  ¼ 0:10 and the CPU time is also acceptable. And we do a Student’s t test to verify that the result of combination ½8; 4; 0:10 is strict smaller than other ones.

jav g ½x;q;  av g ½x;q; j jTj ¼ qffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffi S2½x;q; =10 þ S2½x;q; =10 In Table 1, we can find that jTj > t 0:001 ð9Þ ¼ 4:781. Therefore,

x ¼ 8; q ¼ 4 and  ¼ 0:10 are an appropriate combination and will be used in the following experiments. 6.3. Performance analysis on the proposed algorithm This section will evaluate the performance in terms of objective value and CPU runtime by comparing the proposed algorithm with the algorithm proposed by Park and Kim (2003) for both Phase I and Phase II. 6.3.1. Performance analysis on relax-and-fix algorithm In order to solve Phase I, Park and Kim (2003) proposed a Lagrangean relaxation and subgradient optimization (LRSO) procedure. In our experiments, the parameter settings for LRSO are same as in Park and Kim (2003). The value of k is reduced to 12 k if no improvement is found during N consecutive iterations. The value of N is set to be 30. In this experiment, the real-world-like instances are generated according to the rules introduced in Section 6.1. Each instance is solved by both LRSO and relax-and-fix algorithm with x ¼ 8; q ¼ 4 and  ¼ 0:10. In Table 2, we show a comparison of CPU time, objective value and the gap between the proposed relax-and-fix algorithm and LRSO, respectively. The first two columns display the instance numbers (1–50) and the values of l (20, 25, 30, 35 and 40). The rest of Table 2 are divided into three categories: the computational results of two algorithms, and the comparison between two methods. For LRSO, the upper bound (UB) and lower bound (LB) are displayed. From Table 2, it can be found that relax-and-fix algorithm yields acceptable results which have a small gap with the UB obtained by LRSO in a smaller amount of computational time. The average gaps between the obtained solutions and UB and LB are 3:9% and 13:8%. Note that the final UBs are the final feasible objective values that can be obtained by LRSO. On the average, the final solutions obtained by relax-and-fix algorithm are a little bigger than those obtained by LRSO. However, the biggest gap is no more than 7:5%. Therefore, it can be concluded that the proposed relax-andfix algorithm is applicable to solve the Phase I of the proposed model.

Fig. 11. The performance analysis on the proposed algorithm.

270

C. Liu et al. / Computers & Industrial Engineering 97 (2016) 258–275

Fig. 12. The comparison of CPU time between T 1 and T 2 for Mode RASAP and RALAP.

Table 3 Comparisons between RASAP and RALAP. No.

l

RASAP

RALAP

Phase I

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50

20 20 20 20 20 20 20 20 20 20 25 25 25 25 25 25 25 25 25 25 30 30 30 30 30 30 30 30 30 30 35 35 35 35 35 35 35 35 35 35 40 40 40 40 40 40 40 40 40 40

Average:

Phase II

Phase I

Phase II

Time (s)

Uc

Uv

Ut

U cr

T 1 (s)

T 2 (s)

Time (s)

Uc

Uv

Ut

U cr

T 1 (s)

T 2 (s)

141 127 157 170 309 149 127 183 54 139 127 174 310 278 601 398 255 122 254 203 251 534 532 387 756 390 199 422 227 419 669 678 488 465 405 398 588 567 356 442 823 685 532 665 801 578 501 579 334 671

0.125 0.125 0.125 0.000 0.125 0.125 0.125 0.125 0.000 0.125 0.125 0.125 0.125 0.125 0.125 0.125 0.125 0.125 0.125 0.125 0.125 0.125 0.125 0.125 0.125 0.125 0.125 0.125 0.125 0.125 0.125 0.125 0.125 0.125 0.125 0.250 0.125 0.125 0.125 0.125 0.125 0.125 0.250 0.125 0.125 0.125 0.125 0.125 0.250 0.125

0.006 0.000 0.013 0.000 0.013 0.019 0.031 0.013 0.000 0.013 0.010 0.015 0.030 0.025 0.040 0.025 0.015 0.010 0.040 0.030 0.033 0.033 0.038 0.058 0.067 0.063 0.042 0.038 0.050 0.054 0.057 0.086 0.089 0.082 0.057 0.143 0.029 0.064 0.071 0.086 0.100 0.113 0.175 0.097 0.128 0.088 0.094 0.088 0.147 0.088

0.066 0.063 0.069 0.000 0.069 0.072 0.078 0.069 0.000 0.069 0.068 0.070 0.078 0.075 0.083 0.075 0.070 0.068 0.083 0.078 0.079 0.079 0.081 0.092 0.096 0.094 0.083 0.081 0.088 0.090 0.091 0.105 0.107 0.104 0.091 0.196 0.077 0.095 0.098 0.105 0.113 0.119 0.213 0.111 0.127 0.106 0.109 0.106 0.198 0.106

0.011 0.024 0.011 0.011 0.011 0.024 0.024 0.011 0.000 0.011 0.034 0.034 0.057 0.045 0.102 0.045 0.045 0.034 0.080 0.057 0.068 0.090 0.090 0.079 0.104 0.172 0.158 0.090 0.068 0.090 0.274 0.251 0.261 0.181 0.274 0.544 0.115 0.194 0.181 0.172 0.364 0.342 0.593 0.273 0.375 0.353 0.385 0.455 0.556 0.273

6.44 6.40 5.09 6.49 3.02 5.84 4.47 4.62 3.17 6.54 4.89 4.98 3.49 5.03 5.58 4.26 3.41 6.60 6.31 6.22 4.22 6.14 5.43 3.27 4.72 5.04 5.85 6.27 5.85 3.62 4.12 6.27 5.62 6.19 4.01 4.08 5.20 5.98 3.33 4.85 6.21 5.47 3.38 4.12 4.96 4.55 5.33 4.97 3.18 6.67

5.36 6.19 4.84 5.46 2.42 5.83 3.55 3.78 2.69 5.85 3.89 4.55 2.29 4.33 5.22 3.85 1.94 5.30 5.75 5.19 2.92 6.07 4.42 2.23 3.51 4.45 4.73 5.63 4.58 2.46 3.78 6.07 4.17 6.18 3.06 2.84 3.77 4.57 2.18 4.05 5.92 4.63 2.32 3.15 3.89 3.69 3.88 4.52 2.50 5.90

120 91 113 135 239 117 98 219 35 99 110 155 238 201 505 301 201 97 198 129 190 487 501 330 623 299 147 390 189 390 576 567 399 423 391 234 523 478 334 401 670 601 501 598 709 490 445 498 255 517

0.125 0.125 0.125 0.000 0.125 0.125 0.125 0.125 0.000 0.125 0.125 0.125 0.125 0.125 0.125 0.125 0.125 0.125 0.125 0.125 0.125 0.125 0.125 0.125 0.125 0.125 0.125 0.125 0.125 0.125 0.125 0.125 0.125 0.125 0.125 0.250 0.125 0.125 0.125 0.125 0.125 0.125 0.250 0.125 0.125 0.125 0.125 0.125 0.250 0.125

0.019 0.006 0.019 0.006 0.025 0.025 0.031 0.013 0.000 0.013 0.015 0.020 0.035 0.025 0.045 0.025 0.020 0.010 0.045 0.030 0.033 0.033 0.042 0.063 0.067 0.067 0.050 0.042 0.054 0.054 0.061 0.100 0.093 0.082 0.071 0.157 0.029 0.064 0.079 0.086 0.113 0.113 0.188 0.097 0.131 0.094 0.094 0.100 0.147 0.100

0.072 0.066 0.072 0.003 0.075 0.075 0.078 0.069 0.000 0.069 0.070 0.073 0.080 0.075 0.085 0.075 0.073 0.068 0.085 0.078 0.079 0.079 0.083 0.094 0.096 0.096 0.088 0.083 0.090 0.090 0.093 0.113 0.109 0.104 0.098 0.204 0.077 0.095 0.102 0.105 0.119 0.119 0.219 0.111 0.128 0.109 0.109 0.113 0.198 0.113

0.011 0.035 0.024 0.024 0.024 0.024 0.035 0.011 0.000 0.024 0.045 0.034 0.057 0.568 0.114 0.057 0.057 0.034 0.091 0.068 0.079 0.090 0.104 0.090 0.104 0.183 0.158 0.104 0.090 0.090 0.318 0.251 0.274 0.194 0.274 0.592 0.115 0.204 0.226 0.181 0.342 0.342 0.615 0.320 0.375 0.364 0.385 0.502 0.593 0.273

5.53 6.12 5.67 5.02 6.06 4.93 3.46 5.54 3.23 5.61 3.19 6.21 3.29 4.30 5.08 5.69 3.70 4.84 5.62 4.85 6.64 4.36 5.07 4.78 6.12 4.20 4.46 5.65 3.98 3.81 3.61 4.78 6.84 4.14 5.54 5.78 4.26 3.68 6.04 6.24 6.59 6.15 3.06 3.14 6.71 4.50 5.33 5.90 4.24 6.25

4.89 5.02 4.82 4.49 5.57 4.73 3.45 4.74 1.79 4.11 2.14 5.19 2.86 3.51 4.03 5.52 3.55 4.57 4.73 4.59 5.94 3.34 4.99 3.75 4.84 4.10 4.27 4.68 3.61 2.68 3.41 4.50 5.92 4.13 4.74 4.91 3.73 2.78 5.62 4.93 6.14 5.79 1.61 1.67 6.17 3.70 5.31 5.30 3.37 5.53

392

0.128

0.054

0.091

0.162

5.04

4.21

331

0.128

0.059

0.093

0.183

5.00

4.32

271

C. Liu et al. / Computers & Industrial Engineering 97 (2016) 258–275

Fig. 13. The comparison between Mode RASAP and RALAP.

Table 4 The comparison between different reschedule policies with 50 instances. Para.

Original

RASAP

RALAP

RP

No.

l

In1

In2

In3

In1

In2

In3

In1

In2

In3

In1

In2

In3

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50

20 20 20 20 20 20 20 20 20 20 25 25 25 25 25 25 25 25 25 25 30 30 30 30 30 30 30 30 30 30 35 35 35 35 35 35 35 35 35 35 40 40 40 40 40 40 40 40 40 40

109 65 145 145 59 71 124 116 38 95 86 142 92 79 139 128 91 76 174 116 101 201 177 209 275 271 79 195 125 397 178 352 140 262 225 187 297 257 266 184 298 262 234 170 138 184 205 235 204 334

32 18 46 41 17 22 39 37 10 31 25 37 26 23 39 42 26 24 56 31 26 60 54 54 78 78 22 51 33 109 58 116 38 66 62 60 88 75 73 56 83 81 71 43 44 61 53 78 52 85

120 101 116 114 111 100 114 115 105 108 134 130 143 140 132 133 133 129 143 132 178 176 173 162 159 169 178 176 173 167 188 181 200 191 192 208 183 201 181 186 207 214 228 225 239 208 210 229 226 238

120 76 158 155 72 84 137 123 56 102 96 150 107 86 145 139 98 88 194 134 107 219 194 220 292 284 90 205 136 414 192 372 158 272 244 223 313 269 275 194 315 277 278 178 153 201 220 255 242 349

33 18 48 41 19 25 44 39 10 33 27 40 32 28 48 47 29 26 66 37 35 70 65 68 93 93 34 61 45 122 74 135 60 84 77 99 98 93 92 78 111 112 130 70 86 88 79 104 99 109

121 103 117 115 112 102 116 116 105 109 137 133 148 144 141 137 137 132 149 137 183 184 181 169 168 182 192 183 178 174 207 196 215 203 212 249 194 220 193 200 238 236 279 246 271 235 239 266 268 257

122 74 160 154 74 86 139 121 54 103 97 149 108 87 143 142 100 88 194 132 106 218 196 219 293 283 91 206 138 416 190 371 158 274 246 224 315 271 277 195 314 274 276 180 151 202 218 253 243 351

35 19 49 42 21 26 44 39 10 33 28 41 32 28 49 47 30 26 67 38 36 70 65 71 94 94 34 62 47 122 76 140 62 85 79 106 99 93 94 70 115 114 137 72 93 92 82 105 104 114

121 104 118 116 113 102 117 116 105 110 138 133 148 145 142 138 138 132 151 139 185 185 182 170 168 186 193 187 181 176 212 200 222 208 213 259 195 222 195 202 245 242 294 249 275 237 242 271 279 263

144 90 186 172 76 107 169 129 54 140 129 178 112 97 154 171 111 91 208 146 133 251 229 230 297 301 121 216 145 453 196 381 165 298 274 240 336 297 293 202 346 270 305 185 175 208 240 264 277 372

44 27 65 52 37 35 57 49 23 43 37 57 41 38 60 63 40 38 85 50 53 86 79 83 114 108 49 71 56 140 86 156 82 104 96 119 115 111 111 80 125 129 151 84 109 107 105 115 126 125

136 120 132 129 131 118 130 137 117 123 163 155 160 164 162 157 158 146 175 162 203 197 207 196 183 206 219 213 197 191 232 229 234 223 225 275 213 235 214 222 276 272 324 275 294 262 262 285 298 287

165.98

189.22

178.58

189.52

181.28

207.28

174.64

50.60

65.08

In order to analyze the results in Table 2 better, Fig. 11 summarizes the results of Table 2 with different number of vessels. From Fig. 11, we can sum up some conclusions. From Fig. 11(a), we can observe that the computation time of two algorithms all have an

66.62

80.32

200.48

increasing tendency with the growth in the number of vessels as expected. However, the CPU time for relax-and-fix algorithm is much smaller than that of LRSO. Furthermore, the difference of CPU time by using relax-and-fix algorithm and LRSO also has an

272

C. Liu et al. / Computers & Industrial Engineering 97 (2016) 258–275

increasing tendency. Therefore, the relax-and-fix algorithm has a more obvious advantages than LRSO for solving larger scale instances. Fig. 11(b) shows the radio of the objective to UB and LB for the generated problems and we can find the smallest values are obtained at l ¼ 30 and l ¼ 25, respectively. The reason for such a phenomenon is as follows. When the number of vessels is small, the setting of  leads to a poor quality of solution for relax-and-fix algorithm while LRSO can solve small scale instance well. Meanwhile, when the number of vessels is large, LRSO solve the problem with a much longer CPU time as shown in Fig. 11(a), which will lead to a better solution.

6.3.2. Performance analysis on dynamic programming Park and Kim (2003) proposed a dynamic programming to solve Phase II. In order to reduce the solution space of dynamic programming, this paper proposes Proposition 1. This section will verify that we can save some CPU time by adopting Proposition 1. In this experiment, 50 instances with 20, 25, 30, 35 and 40 vessels generated according the rule introduced in Section 6.1 are used to be tested. Each instance is solved 10 times. Assume that T 1 represents the average CPU time of the method proposed by Park and Kim (2003) and T 2 represents the average CPU time of method by adopting Proposition 1. Fig. 12 shows the comparison of CPU time between T 1 and T 2 for both Mode RASAP and RALAP.

From Fig. 12, we can find that the computation time by adopting Proposition 1 is smaller than that of before on the average, which can prove that Proposition 1 can help us obtain the solution of the Phase II quickly. We can also find that the CPU time varies slightly as the number of vessels increases. It is easy to understand that the number of stage tends to increase while the state space of each stage tends to decrease when the number of vessels grows. These two factors cancel out each other and lead to such a result. 6.4. Performance analysis between Mode RASAP and RALAP In this section, in order to compare the results of Mode RASAP and RALAP, extensive numerical experiments are conducted. In Table 3, we show a comparison of CPU time and objective value for Mode RASAP and RALAP, respectively. The first two columns display the instance numbers (1–50) and the values of l (20, 25, 30, 35 and 40). The rest of Table 3 is divided into two categories: the computational results of Mode RASAP and RALAP. For each mode, the results of Phase I and Phase II are displayed. It is note that

U c ¼ lðTC ns Þ; U v ¼ Pc lðASns i Þ U cr ¼ i¼1 c

Pl k¼1



l TDns k l

;

U t ¼ cU c þ ð1  cÞU v ;

Fig. 14. The increment of evaluation indicators for different rescheduling policies compared with original schedule.

C. Liu et al. / Computers & Industrial Engineering 97 (2016) 258–275

273

Fig. 15. Gantt chart of the original schedule.

In addition, the starting time of the disruption (t s ) and the number of disruption time segments (Nt ) are randomly generated from a uniform distribution of Uð0; 36Þ and Uð12; 36Þ, respectively. As shown in Table 3, the results for the port planner are almost same for two modes. Most of the objective value of port planner is 0.125, which means the actual cost after rescheduling is no more

However, from Fig. 13(b) and (c), Mode RASAP has a smaller objective value than that of Mode RALAP for vessel owners and crane operators with the same number of vessels. This can illustrate that Mode RALAP has a larger negative influence than that of Mode RASAP when a disruption happens.

1

than TC os þ ð4k11 Þb1 . However, for vessel owners and crane operators, the objective value of Mode RASAP is a little smaller than that of Mode RALAP. All in all, the numerical experiments can show that Mode RASAP is better than Mode RALAP, because of the smaller influence on vessels and QCs under the condition of the almost same influence on port planner. Fig. 13 shows the comparison between Mode RASAP and RALAP with different number of vessels. For port planner, vessel owners and crane operators, the perspective all tends to grow as the number of vessels rises. In addition, this tendency is more evident for vessel owners and crane operators. From Fig. 13(a), we can find that there is almost no difference in perspective for port planner with the same number of vessel for Mode RASAP and RALAP.

6.5. Performance analysis of the behavior perception-based disruption models In this section, we would like to evaluate the performance of the behavior perception-based disruption models compared with other scheduling policies. To this end, we compare both Mode RASAP and RALAP with RP scheduling. RP scheduling is one of the most common method to apply to the system while disruptions happen. It basically follows the original schedule but once the disruptions take place, delays the following scheduling plan to the end of the disruptions. In order to measure the performance of the policy, three evaluation indicators are proposed. (a) Total

274

C. Liu et al. / Computers & Industrial Engineering 97 (2016) 258–275

Table 5 An illustrative input data set. No.

ek

ak

bk

dk

sk

No.

ek

ak

bk

dk

sk

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

0 1 7 12 13 16 17 21 24 24 32 32 35 39 44 46 48 70 72 85

20 47 12 30 38 11 30 18 22 37 17 42 46 15 41 29 42 17 30 24

30 32 34 22 31 23 20 17 23 29 19 27 29 27 30 32 32 22 25 20

5 12 10 22 22 19 24 30 35 36 37 53 46 42 64 53 69 75 79 93

76 34 18 106 46 18 117 93 0 118 47 7 115 107 2 8 74 105 68 61

21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40

96 98 101 102 117 119 121 121 127 127 128 131 135 140 141 147 148 160 164 167

32 36 21 44 41 21 24 30 44 13 37 39 21 29 43 37 19 34 36 37

34 20 25 31 34 23 25 19 27 15 22 21 30 25 21 34 20 17 29 20

104 116 108 116 137 124 135 134 141 133 140 140 140 147 162 159 157 171 176 179

67 12 108 32 51 39 34 116 31 103 101 26 74 62 78 82 54 71 45 94

Table 6 The comparison between different reschedule policies. Policy

In1

In2

In3

Original scedule RASAP RALAP RP

240 259 263 299

60 84 91 117

183 199 205 219

P cost: In1 ¼ TC; (b) Total time deviations: In2 ¼ lk¼1 TDk ; and (c) Pl Total number of set-ups: In3 ¼ c¼1 ASi . Table 4 shows the comparison between different reschedule policies. From Table 4, we can find that, compared with the original schedule, the values of three evaluation indicators all have a certain extent of growth for three different policies. However, the proposed behavior perception-based disruption models have a better performance on the three indicators than that of RP scheduling. Compared with Mode RASAP and RALAP, we find that the average values of three indicators for Mode RASAP are a little smaller than that of Mode RALAP. This is consistent with the conclusion in Section 6.4. Fig. 14 shows the increment of evaluation indicators for different rescheduling policies compared with original schedule. The horizontal axis stands for the number of instance. From the figures, we can observe that for all three evaluation indicators, the results of proposed behavior perception-based disruption models (Mode RASAP and RALAP) are below the results of RP scheduling. This can also illustrate that our proposed behavior perception-based disruption models can deal with the disruption better than RP scheduling, which is the most common method in reality. 6.6. A case study This section displays a case study and the data is generated according to the rule introduced in Section 6.1. As shown in Table 5, there are 40 vessels and arrival time of vessels (ek ), operation time of vessels (ak ), the length of vessels (lk ), the desired berthing position for vessels (sk ) and the due time (dk ) are generated. Assume that QC 11 is broken down at time 120 and last for 24 time segments. The results of original schedule, the re-schedule according to Mode RASAP, Mode RALAP and the RP scheduling are shown in Table 6 and the Gantt chart for the original schedule is shown

in Fig. 15. Fig. 15 can help us understand the detail schedule for BAP and QCAP. As shown in Table 6, we can find that the schedules after rescheduling by three methods are very different. Besides, by comparing RP scheduling, we can see that our models have better solutions. Mode RASAP has the lowest total cost, total time deviations and total set-ups, which also shows that Mode RASAP is more suitable for solving the problem. 7. Conclusions BAP and QCAP are frequently encountered problems in CTs and the disruption environment frequently arises in the practical situation. Hence, it is important to have more concerns and discussions on this topic. As refer to Park and Kim (2003), the problem can be divided into two phases: Berth-Scheduling Phase and CraneAssignment Phase. Based on prospect theory, the disruption models are formulated. In order to obtain a feasible solution of the problem, an MIP-based relax-and-fix algorithm is proposed for Phase I and a dynamic programming technique, which is based on Proposition 1, is applied for Phase II. Extensive computational tests which are conducted to test the performance of the models and the proposed methods. First, we design an experiment to determine the parameters of the relax-and-fix algorithm. Second, we evaluate the performance in terms of objective value and CPU runtime by comparing the proposed algorithm with the algorithm proposed by Park and Kim (2003). The results indicate that the proposed algorithms are applicable for solving the problem. Third, through extensive numerical experiments, it is proved that Mode RASAP can conduct the disruption better than Mode RALAP. Furthermore, we evaluate the performance of the behavior perception-based disruption models compared with other scheduling policies and verify that the proposed models can deal with the disruption well. At last, a case study, in which the disruption is conducted by the Mode RASAP, Mode RALAP and the RP scheduling, also indicates that Mode RASAP can conduct the disruption better. In addition, we formulate the model with the assumption that only one of the QCs may break down at a time and incur disruption and at most one disruption can take place during the whole time periods. However, our models can deal with the cases, two or more disruptions at a time or another disruption happens after rescheduling during the whole times period, by changing the constraint of QC’ capacity. Finally, this paper is limited to the discussions on the disruption caused by the machines breakdown. Thus, future research may involve studies on other disruptions, in which the problem will be more complicated and more constraints are needed to be presented and contemplated. Acknowledgements This work is supported by National Natural Science Foundation of China under Grant No. 71472108 and Project of Innovation Method (No. 2014IM010100). References Bendoly, E., Donohue, K., & Schultz, K. L. (2006). Behavior in operations management: Assessing recent findings and revisiting old assumptions. Journal of Operations Management, 24(6), 737–752. Bierwirth, C., & Meisel, F. (2010). A survey of berth allocation and quay crane scheduling problems in container terminals. European Journal of Operational Research, 202(3), 615–627. Bierwirth, C., & Meisel, F. (2015). A follow-up survey of berth allocation and quay crane scheduling problems in container terminals. European Journal of Operational Research, 244(3), 675–689.

C. Liu et al. / Computers & Industrial Engineering 97 (2016) 258–275 Boudreau, J., Hopp, W., McClain, J., et al. (2003). On the interface between operations and human resources management. Manufacturing & Service Operations Management, 5(3), 179–202. Chang, D., Yan, W., Chen, C.-H., & Jiang, Z. (2008). A berth allocation strategy using heuristics algorithm and simulation optimisation. International Journal of Computer Applications in Technology, 32(4), 272–281. Clausen, J., Larsen, A., Larsen, J., et al. (2010). Disruption management in the airline industry-concepts, models and methods. Computers & Operations Research, 37 (5), 809–821. Cordeau, J.-F., Gaudioso, M., Laporte, G., & Moccia, L. (2007). The service allocation problem at the Gioia Tauro maritime terminal. European Journal of Operational Research, 176, 1167–1184. Gino, F., & Pisano, G. (2008). Toward a theory of behavioral operations. Manufacturing & Service Operations Management, 10(4), 676–691. Guan, Y., & Cheung, R. K. (2004). The berth allocation problem: Models and solution methods. OR Spectrum, 26, 75–92. Han, X., Lu, Z., & Xi (2010). A proactive approach for simultaneous berth and quay crane scheduling problem with stochastic arrival and handling time. European Journal of Operational Research, 207, 1327–1340. Hansen, P., & Oguz, C. (2003). A note on formulations of static and dynamic berth allocation problems. Les Cahiers du GERAD, 30, 1–17. Hansen, P., Oguz, C., & Mladenovic, N. (2008). Variable neighborhood search for minimum cost berth allocation. European Journal of Operational Research, 191, 636–649. Imai, A., Nagaiwa, K., & Chan, W. (1997). Efficient planning of berthing allocation for container terminals in Asia. Journal of Advanced Transportation, 31, 75–94. Imai, A., Nishimura, E., & Papadimitriou, S. (2001). The dynamic berth allocation problem for a container port. Transportation Research Part B, 35, 401–417. Imai, A., Sun, X., Nishimura, E., & Papadimitriou, S. (2005). Berth allocation in a container port: Using a continuous location space approach. Transportation Research Part B, 39, 199–221. Imai, A., Chen, H. C., Nishimura, E., & Papadimitriou, S. (2008). The simultaneous berth and quay crane allocation problem. Transportation Research Part E, 44(5), 900–920. James, R. J., & Almada-Lobo, B. (2011). Single and parallel machine capacitated lotsizing and scheduling: New iterative MIP-based neighborhood search heuristics. Computers & Operations Research, 38(12), 1816–1825. Jiang, Y., Sun, W., Ding, Q., & Zhang, X. (2013). Model of disruption management with actors in single machine scheduling. Mechanical Engineering, 14, 191–198. Kahneman, D., & Tversky, A. (1979). Prospect theory: An analysis of decision under risk. Econometrica: Journal of the Econometric Society, 1979, 263–291. Kim, K., & Moon, K. (2003). Berth scheduling by simulated annealing. Transportation Research Part B, 37, 541–560. Liang, C., Huang, Y., & Yang, Y. (2008). A quay crane dynamic scheduling problem by hybrid evolutionary algorithm for berth allocation planning. Computers and Industrial Engineering, 56(3), 1021–1028. Lee, D.-H., Song, L., Wang, H. (2006). Bilevel programming model and solutions of berth allocation and quay crane scheduling. In Proceedings of 85th annual meeting of transportation research board (CD-ROM). Annual Meeting of Transportation Research Board, Washington, DC. Lim, A. (1998). The berth planning problem. Operations Research Letters, 22(2), 105–110. Liu, J., Wan, Y.-W., & Wang, L. (2006). Quay crane scheduling at container terminals to minimize the maximum relative tardiness of vessel departures. Naval Research Logistics, 53(1), 60–74.

275

Lokuge, P., & Alahakoon, D. (2007). Improving the adaptability in automated vessel scheduling in container ports using intelligent software agents. European Journal of Operational Research, 177(3), 1985–2015. Meisel, F., & Bierwirth, C. (2009). Heuristics for the integration of crane productivity in the berth allocation problem. Transportation Research Part E, 45(1), 196–209. Nishimura, E., Imai, A., & Papadimitriou, S. (2001). Berth allocation planning in the public berth system by genetic algorithms. European Journal of Operational Research, 131, 282–292. Park, K., & Kim, K. (2002). Berth scheduling for container terminals by using a subgradient optimization technique. Journal of the Operational Research Society, 53, 1054–1062. Park, Y. M., & Kim, K. H. (2003). A scheduling method for berth and quay cranes. OR Spectrum, 25(1), 1–23. Qi, X., Bard, J. F., & Yu, G. (2004). Supply chain coordination with demand disruptions. Omega, 32(4), 301–312. Steenken, D., VoB, S., & Stahlbock, R. (2004). Container terminal operation and operations research: A classification and literature review. OR Spectrum, 26(1), 3–49. Stahlbock, R., & VoB, S. (2008). Operations research at container terminals: A literature update. OR Spectrum, 30(1), 1–52. Tang, L., & Zhang, Y. (2009). Parallel machine scheduling under the disruption of machine breakdown. Industrial & Engineering Chemistry Research, 48(14), 6660–6667. Vis, I. F. A., & Koster, R. (2003). Transshipment of containers at a container terminal: An overview. European Journal of Operational Research, 147(1), 1–16. Wang, F., & Lim, A. (2007). A stochastic beam search for the berth allocation problem. Decision Support Systems, 42, 2186–2196. Wang, X., Ruan, J., & Shi, Y. (2012). A recovery model for combinational disruptions in logistics delivery: Considering the real-world participators. International Journal of Production Economics, 140(1), 508–520. Wang, J., Wang, J., & Liu, F. (2011). Parallel machines scheduling with a deteriorating maintenance activity. Journal of the Operational Research Society, 62(10), 1898–1902. Wang, Z. X., Dang, Y. G., Pei, L. L., & Wang, Y. Y. (2010). Multi-index grey relational decision-making based on cumulative prospect theory. Control and Decision, 25 (2), 232–236. Xu, H., Zhou, J., & Xu, W. (2011). A decision-making rule for modeling travelers’ route choice behavior based on cumulative prospect theory. Transportation Research Part C: Emerging Technologies, 19(2), 218–228. Zeng, Q., Yang, Z., & Hu, X. (2011). Disruption recovery model for berth and quay crane scheduling in container terminals. Engineering Optimization, 43(9), 967–983. Zhang, C., Zheng, L., Zhang, Zh., Shi, L., & Armstrong, Aaron (2010). The allocation of berths and quay cranes by using a sub-gradient optimization technique. Computers & Industrial Engineering, 58(1), 40–50. Zhen, L., & Chang, D. (2012). A bi-objective model for robust berth allocation scheduling. Computers & Industrial Engineering, 63, 262–273. Zhen, L., Lee, L. H., & Chew, E. P. (2011a). A decision model for berth allocation under uncertainty. European Journal of Operational Research, 212, 54–68. Zhen, L., Chew, E. P., & Lee, L. H. (2011b). An integrated model for berth template and yard template planning in transshipment hubs. Transportation Science, 45, 483–504. Zhen, L. (2014). Container yard template planning under uncertain maritime market. Transportation Research Part E, 69, 199–217.