Some Studies on the Principles and Mechanisms for Loading and Unloading

Earliest start time: ascending order of sj.

Earliest finish time: ascending order of fj.

Shortest interval: ascending order of (fj ¨C sj).

Fewest conflicts: For each job j, count the number of conflicting jobs cj. Schedule in ascending order of cj.

Solution using GA

Greedy algorithm has been used for solving problems in container terminal by several researchers (for example Goodchild et al. 2005; Ng, 2005; Günther, 2005; Froyland et al. 2008; Jinxin et al. 2008).The truck loading and unloading problem with a single crane can be formally described as follows: it is required to minimize the time required to execute a given set of unloading jobs in a predetermined sequence, followed by a given set of loading jobs in a predetermined sequence. The execution time of every job is deterministically known and consists of two components: (i) the time required for the rail side crane to pick/drop a container from/onto a truck (during this time both the crane and the truck are occupied); and (ii) the time required to transport the container between the crane and the appropriate yard location. Upon completing the last unloading job assigned to a truck, the truck transfers directly to the first loading job assigned to it (if any) without passing through the crane. Since the loading and unloading sequences of the jobs are given, our decision problem is to assign the loading and unloading jobs to trucks so as to minimize the makespan of the schedule. The following notation is required for formulating the model.

Let m = number of trucks;

n1 = number of unloading jobs;

n2 = number of loading jobs;

U = {JU1, J U2¡K¡K.J U n1} = set of unloading jobs, ordered in the required processing sequence;

L = {JL 1, JL 2. . . JL n2} = set of loading jobs, ordered in the required processing sequence;

S (J) = processing requirement of the crane for job.

d(J) = one-way travel time required by any truck to transport a job J between the crane and the appropriate yard location.

H (µ §) = duration (i.e., makespan) of a feasible unloading/loading schedule µ §.

Throughout the analysis of this work considered the following assumptions

Assumptions

Throughout the analysis each container is referred to as a job.

All trucks are assumed to be located next to the rail-side crane at the end of all operations.

All trucks are same in their function and transfer one container at a time.

Each truck travels at unit speed 15 mile per hour.

Congestion among trucks is not considered.

The total travel time of any container (i) is the sum of the travel time from rail yard to the stack position and back. Irrespective of the position of the container where it has to be stacked, the total time is equal to 2di.

There is always an available yard crane ready to respond to a service request of any truck. Thus the time it takes a yard crane to load and unload a container is assumed to be incorporated into the container travel time between the rail side area and the yard area. Therefore the term crane will always refer to a rail-side crane (RMGC).

RMGC and TMGC are required to move a bit to adjust to the position of the container to be transferred to the truck. Hence crane unloading time also includes its movement time to position itself for the next container.

The containers in storage yard area can be stacked on top of one another, therefore the time required to get container from the lower levels needs to be incorporated in the loading time.

Every truck makes exactly one switch from “unloading” job to a “loading” job.

All problem parameters (including S (J), d (J)) are non negative.

Scheduling of unloading and loading of containers in a container terminal can be carried out using the two principles described below.

Principle 1: First Available Truck (FAT): Assign the first unscheduled job in U to the available truck which first completes the jobs previously assigned to it.

Principle 2: Last Busy Truck (LBT): Select any value [µ §]. Schedule jobs to trucks so that the last job completes at time [µ §], and proceed backwards. Assign the last unscheduled job in L to the last available truck that became busy with jobs previously assigned to it.

The FAT principle is used to unloading containers from train(s) to fleet of trucks using RMGC. These trucks transport the containers to their locations in the storage yard (see Figure ý4.). The GA is applied to unloading operations using the FAT principle.

GA for unloading container operation

Out of the first m jobs (containers) assign one job to each truck. When a truck returns to the rail side area, the next job is assigned to the truck. The next job is assigned to the first truck available at the rail side area. The greedy algorithm is the same as the list scheduling rule in the machine scheduling literature (see, for example Lawler et al. (1993)). Similarly, when assigning loading job, the first available truck that can reach the job's location at the earliest time will be dispatched to this job. Consider a JU job (container) sequence. Once a truck takes a “U” Job, it transports the job to its location in the storage yard where the yard crane unloads the job. Then this truck has to make empty trip back to the rail-side area to take the next job. The greedy algorithm based on FAT principle is applied to schedule containers to trucks.

Notation

Consider that the job sequence consists of jobs {J1, J2 ...Jn}. For any scheduling policy applied to JU or JL job sequences, the concept of truck arrival time, and truck departure time have been introduced. For dispatching policy, we refer to the time a truck in assigned to job (container) Ji, i=1, 2,¡K,n, as the arrival time of Ji and denote it as µ § and it is known as the completion time of all the jobs. Similarly, we refer to µ § as the departure time for each unloading jobµ §, i =1, 2,...,n, by truck to its location in the storage yard area. For example, initially in an unloading job sequence all trucks are ready next to the RMGC to transport containers to their locations. When the crane starts unloading jobs to trucks, the completion time of job (U) is the time at which the truck returns empty to the rail-side area after dropping off its job at its location in the yard area.

For the sake of simplicity, we will omit the scheduling policy parameter and use µ § andµ §. As mentioned above, job precedence constraints for J_ :{ J1, J2,..., Jn} job sequence are applied in two stages

for i=1,2,¡K,m

µ §Eq ý5.µ § i=1,2,...,mEq ý5.for i= n-m, ¡K, n

µ § i= n-m,...,nEq ý5.The waiting time can be calculated by using the arrival time and the departure time for m jobs. The waiting time is calculated by taking the difference between the minimum arrival time and maximum departure time within a set of m jobs.

µ § Eq ý5.To calculate µ § and µ § we use the following equations

µ §+µ § +wEq ý5.µ § Eq ý5.

The cost C of each job from its starting time to completion time is given in the following equation

µ § Eq ý5.Costs involved in the handling systems are: cost of land, cost of terminal development, cost of equipment, and cost of labour, administration cost and related office operation cost etc. The cost of land is equal to the annual rental cost if the terminal operator does not own the land, or the opportunity cost of the land if the terminal operator owns the land. The terminal development cost, including the annual maintenance and amortization cost of the yard is crucial to terminal operator. The total annual cost of equipment is equal to the capital cost, annual depreciation charge, operation and maintenance cost tied up with the equipment. The cost of labour is equal to the annual salaries and benefits for the equipment drivers and dock foremen.

For any dispatching policy µ § ,we refer to the time the last truck returns to the rail-side area after completing all jobs(containers) in the job sequence as the makespan under the dispatching policy, which is donated by H(µ §).

Theorem For any unloading job sequence, the greedy algorithm is optimal. that is, the greedy algorithm minimizes the makespan.

Proof

Suppose to the contrary, the schedule obtained by greedy algorithm is not optimal for JU:{J1,J2,.....,Jn} job sequence. Consider another optimal schedule say µ §, as this schedule is not obtained by greedy algorithm then, there must be a job say job µ § i µ § in the schedule µ §, that has not been assigned to the first available truck ,that is , job i has been assigned to truck Mi that is available at time T2 instead of truck Mj that is available at time T1, with T1µ §T2, due to the job precedence constraints, the successors of job i can be taken by trucks only after time µ §+s. Thus, in scheduleµ §, truck µ § is idle from time µ §toµ §. Now consider schedule µ §obtained from schedule µ § by assigning job i to the first available truck, that is, to truck µ § at timeµ §. In schedule µ §the successors of job i can be taken by trucks after time µ §where µ §+sµ § by principle 1 .Clearly the makespan of the scheduleµ § is either same or less than the makespan of the schedule µ § , which is contradiction. Hence the greedy algorithm generates the optimal schedule for unloading container sequence.

Remark The greedy algorithm is still optimal even if crane processing times are job-specific, that is, the crane time associated with job Ji is si, and not a constant s. Similarly, it is optimal even when the vehicle travel time and quay crane processing times for each job are random variables.

Corollary1 the greedy algorithm minimizes the completion time of each job in an unloading job sequence (from greedy algorithm definition).

To explain how greedy algorithm works for unloading job, we consider the following example of five unloading jobs µ §

With half travel time µ §2 minutes,µ §, µ §, with fixed crane processing time s=2 we need to schedule these jobs on 2 trucks. In this case greedy algorithm has applied where the first m jobs are assigned, each to a single truck. The greedy algorithm is optimal for any J- job sequence. Note that the round-trip travel time for each unloading job J is 2d (J). The greedy algorithm works as follows. First assign T1 to J1 and T2 to J2 after s1 (J1) =2 units, T1 leaves the crane with J1, and starts discharging J2 . After s(J 2 ) =2 minutes , T2 leaves with J2 , waiting time = w

µ § µ § 2+ 2 µ §

µ § µ §

By comparing µ § and µ § we find truck 1 return back earlier to the rail-side area so next container will assign to it, where is

µ § µ §= 13

Now by comparing µ § and µ § we find µ § and µ § =14, then truck 2 reach to the rail-side earlier, so next container will assign to truck 1, w=0

µ § µ §= 23

By the same way we find T1 reached to the rail side before T2 so the next container will assign to it

µ § µ §=21

The dispatching solution can be represented as T1:{J1, J3, J4}, and T2: {J2, J5}. The completion time for this unloading job sequence is 23= (6+9+8) minutes. The schedule generated by the greedy algorithm is depicted in Gantt chart (used as a visual aid for unloading and scheduling). In Figure ý5. and in all other figures to follow, the shaded region represent the crane processing time and the boxes represent the travel time of the jobs.

 Crane processing time (minutes) 

Truck Travel Time (minutes)

0 2 6 8 1315 23Truck1    J1J3J5 Waiting time

2 4 14

1517 21Truck2    J2J4Figure ý5. The greedy algorithm for an unloading job sequence using FAT principle

The performance of GA has been compared with that of MIP in terms of execution time and the quality of solution achieved. Both the techniques were able to obtain the same optimal solution having a makespan of 23 minutes. However, the execution time taken by GA was only 30 seconds compared to 16 minutes taken by the MIP model. The results are shown in Table ý5..

Table ý5. Performance Comparison of GA and MIP

MIPGAMakespan (minutes)23 23 Computational time(minutes)16 0.5 Greedy algorithm for loading container operation

The problem of loading the containers on to the trains has been solved first by greedy algorithm and then by using the reverse greedy algorithm. Now, consider a JL job (container) sequence. For each job sequence, once a truck is assigned to a “L“ job, it makes an empty trip to the job’s location starting from the train area, takes the job, and returns back to the train area with the job. The completion time of loading job is the time at which the RMGC finishes loading the job onto train(s). For loading sequence JL: {{J1, J2,..,Jn}

µ §Eq ý5.the departure time, arrival time, waiting time, and the cost can be computed using the equations (5-4),(5-5),(5-6),(5-7) Consider again the same five jobs used in the previous example, but now assume that these are loading jobs and not the unloading jobs as was the case previously. That is, we have a job sequence JL: {J1, J2, J3, J4, J5}. In this case, the greedy algorithm suggests the following schedules for each truck: T1 :{ J1, J3, J5} and T2: {J2, J4 }, which results in 24 units of completion time. This schedule is given in Figure ý5.. Note that, in this schedule, truck T1 has to wait for 5 minutes after bringing J3 and J5 to the train(s), since the predecessors (J1, J2, J4) in this case are uploaded. In order to determine whether the solution obtained by GA is optimal, the same problem has also been solved by using the reverse greedy algorithm.

Crane processing time (minutes) 

Truck Travel Time (minutes)

waiting time 0 4 6 111214 18 2224Truck1      J1J3J5 0 10 12 2022Truck2    J2J4Figure ý5. GA for an loading job sequence using FAT principle

Reverse greedy algorithm for loading container operation

Giving a job sequence JL: {J1, J2... Jn}, consider the following polynomial time algorithm called the reverse greedy algorithm the algorithm works by applying principle 2 (LBT) for loading jobs as follows:

Replace each loading job by an unloading job with same location, that is, if location P is the pickup point for a specific loading job, the associated unloading job has location P as its drop-off point.

Reverse the order to get the reversed job sequence JRU: { Jn2, Jn2 -1¡K J2 , J1 }.

Apply the greedy algorithm for this reversed list of unloading jobs.

Reverse again the sequence of the job assigned to each truck

Following the steps outlined above, the reverse greedy algorithm can be applied for scheduling loading jobs.

Theorem The reverse greedy algorithm is optimal for any loading job instance

Proof

To prove Theorem the following lemma is needed.

Lemma Consider the dispatching policy µ § applied to loading job sequence µ § with a makespan of H (µ §). There exists policy µ § applied to the reverse job sequence µ § associated with µ § that achieve the same makespan, i.e., H (µ §) =H(µ §)

Proof Consider loading job sequence µ §=µ §, and the dispatching policy µ §

Letµ §: µ §denote the job sequence assigned to vehicle l, l=1, 2,..., m, under this dispatching policy. The precedence constraints for this µ § job sequence imply that job µ §, can not be completed until all its successors in µ § i.e., µ § are completed. Hence the following equation is given

µ § Eq ý5.Clearly the makespan for this dispatching policy is H (µ §)=.µ §.Now considers the corresponding reverse unloading jobs sequence, JRU: {Jn2, Jn2 -1¡K, J2, J1}.the objective is to find a dispatching policy µ § for the reverse job sequence with a makespan H (µ §) such that H (µ §) = H (µ §).

For this purpose consider the dispatching policy µ § obtained as follows.

Reverse the job sequence µ § , define as above, and denote the resulting sequence as µ §. Under this policy, truck l starts with job µ §continues with job µ §, and so on. Start job µ §, an unloading job now , at time H (µ §)-µ §=0, job µ § at H (µ §)-µ §,..., and job µ § at H (µ §)-µ §.

The question here it can be able to show the schedule obtained by dispatching policy µ § satisfies (a) the precedence constraints for the µ § job sequence, and (b) truck capacity constraints, when we have dispatching for which

H (µ §) = H (µ §)-µ §+ µ §+s= H (µ §)

Consider jobs µ § and µ § under dispatching policy µ § then it has

µ § H (µ §) +µ §=µ § s from Eq ý5.

And hence the precedence constraints job µ §job sequences are satisfied.next it has to show that the schedule obtained by dispatching policy µ § is also satisfy the truck capacity constraints. Truck l, µ §, can serve jobs µ §.under dispatching policy µ §, since for jobs µ § and µ §, µ § .

µ § H (µ §) +µ §=µ § +s

Hence, dispatching policy µ §generates a feasible schedule for the µ § job sequence with a makespan of µ § .This complete the proof of lemma which lead to the following corollary:

Corollary2: Consider the dispatching policy µ § applied to unloading job sequence, with a makespan of H (µ §). There exists a dispatching policy µ § for the reverse loading job sequence wth unloading job such that it achieves exactly the makespan, i.e., H (µ §) = H (µ §).

Now it is ready to prove Theorem

Proof of Theorem Let µ § be the optimal dispatching policy for an unloading job sequence, with a makespan of H (µ §). By Lemma 2 it can be found a dispatching policy µ § for the corresponding reverse unloading job sequence µ § such that H (µ §).= H (µ §).

Now considering the optimal dispatching policyµ §.for this µ § job sequence with a makespan of H (µ §) by corollary2 the dispatching policy µ § for the corresponding reverse loading job sequence µ § which is the original µ § job sequence such that H (µ §).= H (µ §), by optimality of H (µ §) for the µ § job sequence , it has :

H (µ §). = H (µ §)µ § H (µ §). = H (µ §),Eq ý5.On the other hand, the optimality of H (µ §). For loading jobs sequence implies that

H (µ §).µ § H (µ §) and hence Eq ý5. hold as equality. That is H (µ §).µ § H (µ §)

H (µ §).µ § H (µ §)Eq ý5.Finally Theorem tell us that greedy algorithm is an optimal dispatching policy for µ § job sequence .thus, given a loading job sequence, it can obtain the reverse job sequence µ § associated with loading job and find the optimal schedule for this µ § job sequence , it can be constructed a schedule for the original loading job as done in proof of lemma 2, that is it can be done by reversing the sequence of jobs assigned to each truck. Furthermore, this must be one of the optimal schedule(s)for the loading job sequence ,since H (µ §).µ § H (µ §) by Eq ý5.. Observing that this is the reverse greedy algorithm complete the proof.

The same problem as discussed above was solved using the reverse greedy algorithm.

loading job J JL: { JL1, JL2 , JL3, JL4, JL5},which become JU (JU1,JU2,JU3,JU4,JU5}

reverse the order µ § :{J5,J4,J3,J2,J1)={2, 4, 2.5, 5, 2}

Apply greedy algorithm on this sequence we get

µ § µ § 2+ 2 µ §

µ § µ §

By comparing µ § and µ § we find truck 1 return back earlier to the rail-side area so next container will assign to it, where is

µ § µ §= 13

Now by comparing µ § and µ § we find µ § and µ § =12, then truck 2 reach to the rail-side earlier, so next container will be assigned to truck 2, w=0

µ § µ §= 24

By the same way we find T1 reached to the rail side before T2 so the next container will assign to it and has to wait 1 minute.

µ § µ §=20

Reversing the order again yields an optimal makespan of 22 minutes.

Figure ý5. illustrates the mechanism of reverse greedy algorithm as applied to a J+ job sequence for the problem described above. It can be seen from Figure ý5. that application of reverse greedy algorithm resulted in an optimal makespan of 22 minutes for the loading problem described above. The schedule in Figure ý5. (a) is obtained by applying the greedy algorithm to the reserved job sequence in the first step of algorithm. The schedule in Figure ý5. (b) is obtained by reversing the jobs assigned to each truck in the first step. Hence, the reverse greedy algorithm obtains a schedule with a makespan of 22 minutes, which is the optimal makespan for this loading job sequence. The complexity for both greedy algorithm and reverse greedy algorithm has running time of µ § (see Appendix D).

 Crane processing time (minutes) 

Truck Travel Time (minutes)

(a)waiting time

0 2 6 8 13 14 16 20Truck1      J5J3J1 2 4 1214 24Truck2    J4J2(b) 0 46 11 12 14 18 20Truck1      J1J3J5 0 10 12 20 22Truck2    J2J4Figure ý5.. Reverse greedy algorithm for loading containers using LBT principle

Solution using shortest job time first scheduling algorithm

STF is one priority sequencing rule which starts scheduling with the shortest job completion time (Rose, 2001) It is typically considered a multiclass and non-preemptive scheduling policy. The STF algorithm starts with shortest job completion time and then schedule the remaining jobs according to the increasing order of job completion time. For application of this mechanism to loading and unloading operations, the exact completion time of different jobs must be known in advance. However, in a real life situation it is not possible to determine the exact time of completion of a job in advance.

STF does not exhibit the fairness shown in FAT scheduling policy as processes are given priorities based on job sequence, and handling a job with longer time may starve or may have to wait too long to get serviced As mentioned above, job precedence constraints for J :{ J1, J2..., Jn} job sequences are considered in two stages: In the first stage, the processing time and travel time (which referred as handling time for simplicity) for each job is summed up. In the second stage, the scheduling sequence can be obtained by starting from smallest values to the largest value obtained in the first stage.

µ §Eq ý5.The working principle of a STF algorithm is as follows: The job with the shortest completion time are handled and completed first. The driving data for the algorithm includes the number of jobs, the job names, and the handling time of each job. The second step involves sorting out the smallest values of the summation of processing and travel time among the jobs. The order of the jobs to be sequenced is determined on the basis of summation of processing and travel time. The jobs with smallest sum are executed first and the job with the largest sum is executed in the end. The makespan is then determined by using equations (5-4), (5-5), and (5-6). The schedule obtained using the STF algorithm for the 2 trucks, 5 jobs problem is presented in Table ý5..

Table ý5. Schedule obtained using STF algorithm

Job NumberHandling time

(minutes)Handling time in increasing order

(minutes)Job number according to the new scheduling12+4=66122+10=126532+5=77342+8=1010452+4=6122Table ý5. gives the following job sequence: {J1, J5, J3, J4, J2}. For this job sequence, the makespan is calculated and the Gantt chart is prepared and shown in Figure ý5..

 Crane processing time (minutes) 

Truck Travel Time (minutes)

0 2 6 8 13 15 25Truck1      J1J3J2 2 4 8 10 18Truck2    J5J4Figure ý5. STF scheduling algorithm for unloading containers

STF algorithm suggests the following schedules for each truck: T1 :{ J1, J3,J2} and T2: {J5, J4 }, which results in 25 minutes of completion time . This schedule is given in Figure ý5..

Solution using largest job time first scheduling algorithm

LTF is multiclass scheduling policy that can be pre-emptive or non-pre-emptive. It works in the same way as STF, but tasks are initially sorted based on expected execution time. It is possible for a user to have an accurate estimation of the distribution of times between the tasks of the application, but in practice small variations will affect the overall efficiency because the order of assignment is fixed by the user at the beginning. LTF does not exhibit the fairness shown in FAT scheduling algorithm as processes are given different priorities. Also, shorter job handling time may have to wait too long to get serviced.