Table B3 - Examples of CT operating systems and land used per annum
Operating Systems m2 per 1000 TEU p.a.Examples of operating systemWheeled operation50000Norfolk, Baltimore, New York/New JerseySC20000Norfolk, Antwerp, Zeebrugge,GothenburgTMGC12000Antwerp, RotterdamRMGC8000KaoshiungAGV/ASC2500ECT in the Netherlands (withautomated stacking cranes, ASC)
Table B4 - Comparison of yard equipment OHBC, RMGC, and TMGC.
ItemTMGCRMGCOHBCPossibility of application at conventional terminalVery easyEasyVery difficultPrecision of jobLowHighVery highInitial InvestmentLowHighVery highTechnical problemEngineering facilities are necessary to prevent settlement of groundEngineering facilities are necessary to prevent settlement of ground-Engineering facilities are necessary to prevent settlement of ground ¨Cmanufacturing steel boom with high intensityTerminal retaining the equipmentCONCOR-TKD
New DelhiECT/DSL,
Thames port
HHLASingapore (PPT)
Appendix C
Code for Mathematical Model using AMPL software
param m;
param n;
param k;
set I={1..n};
set J={1..m};
set M={1..k};
param K=10000;
param d{1..n};
param s{1..n};
var ta{I}>=0;
var td{I}>=0;
var y{I,M} binary;
var x{I,J,M} binary;
minimize T: max{i in I}ta[i];
subject to
onetruck {i in I}: sum {j in M} y[i,j]=1;
jobafteri {i in I,p in M}: sum {j in J:j<>i} x[i,j,p]<=y[i,p];
jobbeforei {j in J,p in M }: sum {i in I:i<>j} x[i,j,p]<=y[j,p];
precedence {i in I, j in J,p in M:j<>i}: x[i,j,p]+x[j,i,p]>=y[i,p]+y[j,p]-1;
#precedence1 {i in I, j in J,p in M:j<>i}: x[i,j,p]+x[j,i,p]<=1;
mix {i in I, j in J,p in M:j<>i}: ta[i]<=K*(1-x[i,j,p])+ta[j];
comp {i in I}: td[i]+2*d[i]=ta[i];
depart {i in M}:td[i]=if i=1 then s[1] else sum{a in 1..i} s[a];
depart2{i in k+1..n}:td[i]=min{a in i-k..i-1}ta[a]+abs (min{a in i-k..i-1}ta[a]- max {a in i-k..i-1}td[a])+s[i];
Appendix D
Code for Greedy Algorithm Based Model
/***************************************************************/
/* Final Code for Greedy Algorithm as on May 2007*/
#include
#include
#include
#include
#include
include
#include "rvector.cpp"
void moment(float data[], int n, float *ave, float *adev, float *sdev, float *var,
float *skew, float *curt) ;
void piksr2(int n, float arr[], int brr[]);
void sortdescending(int n, float arr[]);
int RandomInteger(int, int );
float findavg(float [], int );
float findstddev(float [], int);
float findmax(float vals[],int num_els) ;
float findmin(float vals[],int num_els) ;
void get_f(char name[]) ;
/* routine to find average of values */
float findavg(float *vals,int num_els)
{
float average, summation=0.0F;
for (int i=1;i<=num_els; i++) {
summation=summation+vals[i];
}
average = summation/num_els;
return average;
}
/**********************************************/
/******This function returns standard deviation of n flaot values ****/
float findstddev(float *vals,int num_els) /* no semi colon here */
{
float avg,stddev,square_sum;
float sum = 0.0F;
float sum_square = 0.0F;
for (int i = 1; i <= num_els; i++) {
sum += vals[i];
sum_square += vals[i] * vals[i];
}
avg = sum/num_els;
square_sum = avg * avg * num_els;
stddev = sqrt((sum_square - square_sum)/(num_els - 1));
if(stddev==0) stddev=1;
return stddev;
}
/**************************************************************************/
/**************************************************************************/
/* routine to find the maximum value for a given array starts here */
float findmax(float vals[],int num_els) /* no semi colon here */
{
float max=vals[1];
int i;
for (i=1;i<= num_els; i++)
if (vals[i]>=max) max=vals[i];
return max;
}
/**************************************************************************/
/* routine to find the mimimum value for a given array starts here */
float findmin(float vals[],int num_els) /* no semi colon here */
{
int i;
float min=vals[1];
for (i=1;i<=num_els; i++)
if (vals[i]<=min) min=vals[i];
return min;
}
/**************************************************************************/
/*************************************************************************/
void sortascending(int n, float arr[]) {
int i,j;
float a;
for (j=2; j<=n; j++) {
a=arr[j];
i=j-1;
while(i>0 && arr[i]>a) {
arr[i+1]=arr[i];
i--;
}
arr[i+1]=a;
}
}
/********ROUTINE TO SORT num_els number of values ************************/
/*************************************************************************/
void piksr2(int n, float arr[], int brr[]) {
/* arranges arr values and ascending but keeps the link
between index and values intact */
int i,j;
float a;
int b;
for (j=2; j<=n; j++) {
a=arr[j];
b=brr[j];
i=j-1;
while(i>0 && arr[i]>a) {
arr[i+1]=arr[i];
brr[i+1]=brr[i];
i--;
}
arr[i+1]=a;
brr[i+1]=b;
}
}
/***********************************************************/
void moment(float data[], int n, float *ave, float *adev, float *sdev, float *var,
float *skew, float *curt)
{
int j;
float ep=0.0, s,p;
if (n<=1) nrerror (" n should be atleast 2");
s=0.0;
for(j = 1; j <= n; j++) s+=data[j];
*ave = s/n;
*adev=(*var)=(*skew)=(*curt)=0.0;
for(j = 1; j <= n; j++) {
*adev+=fabs(s=data[j]-(*ave));
ep+=s;
*var+= (p=s*s);
*skew+= (p *=s);
*curt+= (p*=s);
}
*adev /=n;
*var=(*var-ep*ep/n)/(n-1);
if (*var==0.0) *var=0.01F;
*sdev=sqrt(*var);
if (*var) {
*skew/=(n*(*var)*(*sdev));
*curt=(*curt)/(n*(*var)*(*var))-3.0;
}
else nrerror ("No skew/kurtosis when variance is zero ");
}
/*****************************************************************/
/*************************************************************************/
void sortdescending(int n, float arr[]) {
int i,j;
float a;
for (j=2; j<=n; j++) {
a=arr[j];
i=j-1;
while(i>0 && arr[i]
arr[i+1]=arr[i];
i--;
}
arr[i+1]=a;
}
}
/*****************************************************************/
main()
{
char title[80];
//char stationfile[ARRAY_SIZE][STR_SIZE] ;
int ii, jj, tt, Njobs, Ntrucks;
int *y, *truckAvail;
float W, CurMin, PreMin, makespan;
float *s, *d, *x;
float **Tarr, **Tdep;
float waiting=0.0;
FILE *f1,*f2;
/* Open the main List file */
if(!(f1 = fopen("results.txt", "w"))) {
printf(" Can't open GreedyAlgorithm.lst on f1/n") ;
exit(1) ;
}
if(!(f2 = fopen("input1.dat", "r"))) {
printf(" Can't open GreedyAlgorithm.lst on f2/n") ;
exit(1) ;
}
fscanf(f2,"%d ",&Njobs);
fscanf(f2,"%d ",&Ntrucks);
fprintf(f1,"Number of jobs=%d\n",Njobs);
fprintf(f1,"Number of trucks=%d\n",Ntrucks);
// fgets(title, 80, f1);
// puts(title);
printf("Njobs = %4d & ", Njobs);
printf("Ntrucks = %4d\n", Ntrucks);
printf("press a key to continue\n");
s = vector (1, Njobs);
d= vector (1, Njobs);
x= vector (1, Ntrucks);
y= ivector (1, Ntrucks);
truckAvail= ivector (1, Njobs);
fprintf(f1,"Job_Number Processing_Time Travel_Time \n");
fprintf(f1,"==========================================\n");
for(ii = 1; ii <= Njobs; ii++) {
fscanf(f2,"%f %f" ,&s[ii],&d[ii] );
fprintf(f1,"%2d\t %2.2f\t %2.2f \n",ii,s[ii],2.0*d[ii]);
}
printf("data read successfully; press a key to continue\n");
(void)fclose(f2) ;
Tarr = matrix(1, Njobs,1,Ntrucks);
Tdep = matrix(1, Njobs,1,Ntrucks);
W = 0.0;
PreMin = -100.0;
ii =1;
jj=1;
for(tt = 1; tt <= Ntrucks; tt++) {
truckAvail[tt] = tt;
Tdep[jj][tt] = jj*s[jj];
Tarr[jj][tt] = Tdep[jj][tt] + 2.0*d[jj];
x[ii] = Tarr[jj][tt];
// printf("x[%d]=%3.2f\t",ii,x[ii]);
ii = ii +1;
jj=jj+1;
}
for(ii = 1; ii <= Ntrucks; ii++) {
y[ii]=ii;
}
piksr2(Ntrucks, x, y);
fprintf(f1,"\n");
float z=0.0;
float c=0.0;
float total=0.0;
float ww=0;
fprintf(f1,"Job_Number Depart_Time Arrival_Time Waiting_Time Travel_Time Truck_No Cost(Rs)\n");
fprintf(f1,"===============================================================================================\n");
for(ii = 1; ii <= Ntrucks; ii++) {
printf("x[%d]=%3.2f , ",ii, x[ii]);
printf("y[%d]=%d\n",ii, y[ii]);
z=z+s[ii];
fprintf(f1,"%3d\t %5.2f\t %5.2f\t %3.2f\t %5.2f\t %d\t %6.2f \n",ii,z,z+2.0*d[ii],ww,2.0*d[ii],ii,c=(2.0*d[ii]*4.0)+(z*2.0));
total+=c;
ww=z;
waiting+=ww;
}
// stage loop starts here
for(jj = (Ntrucks + 1); jj <= Njobs; jj++) {
CurMin=x[1];//previous minimum arrival time
CurMin = x[1];
truckAvail[jj] = y[1];
PreMin=0;//previous maximum departure time
for(int kk=1 ;kk
if (PreMin
W = PreMin-CurMin;
if (W<0) W=W*(-1.0);
printf("jj=%4d\t",jj);
printf("PreMin=%3.2f\t", PreMin);
printf("CurMin=%3.2f\t", CurMin);
printf("truckAvai[%d] =%d\t",jj, truckAvail[jj]);
printf("W =%3.2f\n", W);
//if (W>=s[jj]) W = 0.0;
//printf("W after correction =%3.2f\n", W);
//PreMin = CurMin;
Tdep[jj][truckAvail[jj]] = CurMin+s[jj] + W;
Tarr[jj][truckAvail[jj]] = Tdep[jj][truckAvail[jj]] + 2.0*d[jj];
printf("Tarr[%d][%d]=%3.2f\n",jj,truckAvail[jj], Tarr[jj][truckAvail[jj]]);
c=4.0*(Tarr[jj][truckAvail[jj]]-Tdep[jj][truckAvail[jj]])+0.5*W+s[jj];
fprintf(f1,"%3d\t %5.2f\t %5.2f\t %2.2f\t %5.2f\t %d\t %6.2f \n",jj,Tdep[jj][truckAvail[jj]],Tarr[jj][truckAvail[jj]],W,Tarr[jj][truckAvail[jj]]-Tdep[jj][truckAvail[jj]],truckAvail[jj],c);
total+= c ;
waiting+=W;
x[1] = Tarr[jj][truckAvail[jj]];
y[1] = truckAvail[jj];
piksr2(Ntrucks, x, y);
}
makespan = Tarr[Njobs][truckAvail[Njobs]];
printf("makespan=%3.2f\n", makespan);
fprintf(f1,"\n\nMakespan=%3.2f\n",makespan);
fprintf(f1,"Total Cost=%3.2f\n",total);
fprintf(f1,"Total waiting=%3.2f",waiting);
//print the results
printf("Job No. Truck Assigned\n");
for(jj = 1; jj <= Njobs; jj++) {
printf( " %4d % 4d\n", jj, truckAvail[jj]);
}
fclose(f1);
return 0;
} /* end of main */
Code for Reverse Greedy Algorithm Based Model
/***************************************************************/
/* Final Code for Greedy Algorithm as on 15 June 2007*/
#include
#include
#include
#include
#include
#include "rvector.cpp"
const unsigned STR_SIZE = 25; //no. of characters in filenames
const unsigned ARRAY_SIZE = 10; //depends upon number of files
void moment(float data[], int n, float *ave, float *adev, float *sdev, float *var,
float *skew, float *curt) ;
void piksr2(int n, float arr[], int brr[]);
void sortdescending(int n, float arr[]);
int RandomInteger(int, int );
float findavg(float [], int );
float findstddev(float [], int);
float findmax(float vals[],int num_els) ;
float findmin(float vals[],int num_els) ;
void get_f(char name[]) ;
/* routine to find average of values */
float findavg(float *vals,int num_els)
{
float average, summation=0.0F;
for (int i=1;i<=num_els; i++) {
summation=summation+vals[i];
}
average = summation/num_els;
return average;
}
/**********************************************/
/******This function returns standard deviation of n flaot values ****/
float findstddev(float *vals,int num_els) /* no semi colon here */
{
float avg,stddev,square_sum;
float sum = 0.0F;
float sum_square = 0.0F;
for (int i = 1; i <= num_els; i++) {
sum += vals[i];
sum_square += vals[i] * vals[i];
}
avg = sum/num_els;
square_sum = avg * avg * num_els;
stddev = sqrt((sum_square - square_sum)/(num_els - 1));
if(stddev==0) stddev=1;
return stddev;
}
/**************************************************************************/
/**************************************************************************/
/* routine to find the maximum value for a given array starts here */
float findmax(float vals[],int num_els) /* no semi colon here */
{
float max=vals[1];
int i;
for (i=1;i<= num_els; i++)
if (vals[i]>=max) max=vals[i];
return max;
}
/**************************************************************************/
/* routine to find the mimimum value for a given array starts here */
float findmin(float vals[],int num_els) /* no semi colon here */
{
int i;
float min=vals[1];
for (i=1;i<=num_els; i++)
if (vals[i]<=min) min=vals[i];
return min;
}
/**************************************************************************/
/*************************************************************************/
void sortascending(int n, float arr[]) {
int i,j;
float a;
for (j=2; j<=n; j++) {
a=arr[j];
i=j-1;
while(i>0 && arr[i]>a) {
arr[i+1]=arr[i];
i--;
}
arr[i+1]=a;
}
}
/********ROUTINE TO SORT num_els number of values ************************/
/*************************************************************************/
void piksr2(int n, float arr[], int brr[]) {
/* arranges arr values and ascending but keeps the link
between index and values intact */
int i,j;
float a;
int b;
for (j=2; j<=n; j++) {
a=arr[j];
b=brr[j];
i=j-1;
while(i>0 && arr[i]>a) {
arr[i+1]=arr[i];
brr[i+1]=brr[i];
i--;
}
arr[i+1]=a;
brr[i+1]=b;
}
}
/***********************************************************/
void moment(float data[], int n, float *ave, float *adev, float *sdev, float *var,
float *skew, float *curt)
{
int j;
float ep=0.0, s,p;
if (n<=1) nrerror (" n should be atleast 2");
s=0.0;
for(j = 1; j <= n; j++) s+=data[j];
*ave = s/n;
*adev=(*var)=(*skew)=(*curt)=0.0;
for(j = 1; j <= n; j++) {
*adev+=fabs(s=data[j]-(*ave));
ep+=s;
*var+= (p=s*s);
*skew+= (p *=s);
*curt+= (p*=s);
}
*adev /=n;
*var=(*var-ep*ep/n)/(n-1);
if (*var==0.0) *var=0.01F;
*sdev=sqrt(*var);
if (*var) {
*skew/=(n*(*var)*(*sdev));
*curt=(*curt)/(n*(*var)*(*var))-3.0;
}
else nrerror ("No skew/kurtosis when variance is zero ");
}
/*****************************************************************/
/*************************************************************************/
void sortdescending(int n, float arr[]) {
int i,j;
float a;
for (j=2; j<=n; j++) {
a=arr[j];
i=j-1;
while(i>0 && arr[i]
arr[i+1]=arr[i];
i--;
}
arr[i+1]=a;
}
}
/***************************************************************/
main()
{
char title[80],temptitle[80];
char datafile[ARRAY_SIZE][STR_SIZE] ;
int ii, mm, jj, tt, kk, Njobs, Ntrucks, Nfiles;
int *y, *z, *jobseq, *truckAvail, *Ntrips, *revindex, *x;
int **jobByTruck;
float W, CurMin, PreMin, makespan, netCost;
float *s, *d, *rd, *xarr, *xdep, *diff, *TD, *TA,*cost;
float **Tarr, **Tdep;
float shipCost = 10;
float truckCost1 = 5; //per minute cost
float truckCost2 = 4; //per truck cost
float waitSum=0.0;
FILE *f1, *f2;
/*Nfiles = 1;
if(!(f1 = fopen("ReverseGreedyAlgorithm.lst", "r"))) {
printf(" Can't open GreedyAlgorithm.lst on f1/n") ;
exit(1) ;
}
fgets(temptitle, 80, f1);
puts(temptitle);
printf("Names of files as read from Main File\n");
for (mm=1; mm<=Nfiles; mm++) {
fgets(datafile[mm],STR_SIZE, f1);
printf("%3d %s\n", mm, datafile[mm]);
}
for (mm=1; mm<=Nfiles; mm++) {
for (ii=1; ii<=STR_SIZE; ii++) {
if (datafile[mm][ii] =='\n') datafile[mm][ii]='\0';
}
}
(void)fclose(f1);
/*****************************************/
/* open the actual data file */
/* for(mm = 1; mm <= Nfiles; mm++) {
if(!(f2 = fopen(datafile[mm], "r"))) {
printf(" Can't open datafile on f2\n") ;
exit(1) ;
}
fgets(title, 80, f2) ;
}
*/
// puts(title);
if(!(f1=fopen("Results2.txt","w"))) printf("Can not create file ");
if(!(f2=fopen("input2.dat","r"))) printf("Can not open file ");
fscanf(f2,"%d ",&Njobs);
fscanf(f2,"%d ",&Ntrucks);
printf("Njobs = %4d\t", Njobs);
printf("Ntrucks = %4d\n", Ntrucks);
fprintf(f1,"Number of Jobs=%d\n",Njobs);
fprintf(f1,"Number of Trucks=%d\n",Ntrucks);
printf("press a key to continue\n");
s = vector (1, Njobs);
d= vector (1, Njobs);
rd= vector (1, Njobs);
xarr= vector (1, Ntrucks);
xdep= vector (1, Ntrucks);
diff= vector (1, Ntrucks);
TD = vector (1, Njobs);
TA = vector (1, Njobs);
y= ivector (1, Ntrucks);
z= ivector (1, Ntrucks);
revindex = ivector (1, Njobs);
Ntrips = ivector (1, Ntrucks);
truckAvail= ivector (1, Njobs);
jobseq= ivector (1, Njobs);
fprintf(f1,"Job_Number Processing_Time Half_Travel_Time\n ");
fprintf(f1,"==============================================\n");
for(ii = 1; ii <= Njobs; ii++) {
fscanf(f2,"%f %f" ,&s[ii],&d[ii] );
fprintf(f1,"%2d\t %3.2f\t %3.2f\t\n" ,ii,s[ii],d[ii] );
}
printf("data read successfully\n");
(void)fclose(f2) ;
//reverse the job order
jj=0;
float ww=0.0;
float waiting=0.0;
fprintf(f1,"Job_Number Depart_Time Arrival_Time Waiting_Time Travel_Time Truck_Number Cost\n ");
fprintf(f1,"=======================================================================================\n");
for(ii = Njobs; ii >= 1; ii--) {
jj=jj+1;
rd[ii]= d[jj];
}
printf("order reversed\n");
Tarr = matrix(1, Njobs,1,Ntrucks);
Tdep = matrix(1, Njobs,1,Ntrucks);
cost= vector(1,Njobs);
W = 0.0;
PreMin = -100.0;
float a=0;
float total=0.0;
ii =1;
jj=1;
makespan=0.0F;
for(tt = 1; tt <= Ntrucks; tt++) {
a+=s[jj];
truckAvail[tt] = tt;
Tdep[jj][tt] = a;
Tarr[jj][tt] = Tdep[jj][tt] + 2.0*rd[jj];
if (Tarr[jj][tt]>makespan) makespan = Tarr[jj][tt];
xarr[ii] = Tarr[jj][tt];
xdep[ii] = Tdep[jj][tt];
cost[tt]=4.0*(Tarr[jj][truckAvail[jj]]-Tdep[jj][truckAvail[jj]])+2.0*a;
printf("xarr[ii]=%3.2f\n", xarr[ii]);
printf("xdep[ii]=%3.2f\n", xdep[ii]);
fprintf(f1,"%2d\t %5.2f\t \t%5.2f\t \t %3.2f\t \t %5.2f\t %5d\t \t %5.2f\t\n",jj,Tdep[jj][tt],Tarr[jj][tt],ww,Tarr[jj][tt]-Tdep[jj][tt],tt,cost[tt] );
total+=cost[tt];
ww=a;
waiting+=ww;
ii = ii +1;
jj=jj+1;
}
for(ii = 1; ii <= Ntrucks; ii++) {
y[ii]=ii;
z[ii]=ii;
}
piksr2(Ntrucks, xarr, y);
piksr2(Ntrucks, xdep, z);
printf("Arrival times in ascending order\n");
for(ii = 1; ii <= Ntrucks; ii++) {
printf("xarr[ii]=%3.2f\n", xarr[ii]);
}
for(ii = 1; ii <= Ntrucks; ii++) {
printf("y[ii]=%d\n", y[ii]);
}
printf("Departure times in ascending order\n");
for(ii = 1; ii <= Ntrucks; ii++) {
printf("xdep[ii]=%3.2f\n", xdep[ii]);
}
for(ii = 1; ii <= Ntrucks; ii++) {
printf("z[ii]=%d\n", z[ii]);
}
// stage loop starts here
for(jj = (Ntrucks + 1); jj <= Njobs; jj++) {
W = xdep[Ntrucks] - xarr[1];
if (W <0.0) W =0.0F;
waitSum=waitSum+W;
printf("W=%3.2f WaitSum = %3.2f\n",W, waitSum);
CurMin = xarr[1];
truckAvail[jj] = y[1];
printf("jj=%4d\n",jj);
printf("PreMin=%3.2f\n", PreMin);
printf("CurMin=%3.2f\n", CurMin);
printf("truckAvai[jj] =%d\n", truckAvail[jj]);
printf("W =%3.2f\n", W);
PreMin = CurMin;
Tdep[jj][truckAvail[jj]] = CurMin+s[jj] + W;
Tarr[jj][truckAvail[jj]] = Tdep[jj][truckAvail[jj]] + (float)2.0*rd[jj];
if (Tarr[jj][truckAvail[jj]]>makespan) makespan = Tarr[jj][truckAvail[jj]];
printf("Tdep[jj][truck[jj]]=%3.2f\n", Tdep[jj][truckAvail[jj]]);
printf("Tarr[jj][truck[jj]]=%3.2f\n", Tarr[jj][truckAvail[jj]]);
xarr[1] = Tarr[jj][truckAvail[jj]];
xdep[Ntrucks] = Tdep[jj][truckAvail[jj]];
y[1] = truckAvail[jj];
piksr2(Ntrucks, xarr, y);
cost[jj]= 2.5*(Tarr[jj][truckAvail[jj]]-Tdep[jj][truckAvail[jj]])+0.5*W+s[jj];
fprintf(f1,"%2d\t %5.2f\t\t%5.2f\t \t %5.2f\t \t %5.2f\t %5d\t \t %5.2f\t\n",jj,Tdep[jj][truckAvail[jj]],Tarr[jj][truckAvail[jj]],W,Tarr[jj][truckAvail[jj]]-Tdep[jj][truckAvail[jj]],truckAvail[jj] ,cost[jj]);
total+=cost[jj];
waiting+=W;
}
printf("makespan=%3.2f\n", makespan);
netCost = makespan*(shipCost - truckCost1)-Ntrucks*truckCost2;
printf("netCost=%3.2f\n", netCost);
printf("waitSum=%3.2f\n", waitSum);
// REVERSE THE index
ii=Njobs+1;
for(jj = 1; jj <= Njobs; jj++) {
ii=ii-1;
revindex[ii]=jj;
}
printf("After reversing \n");
printf("jobs truck available Arrival time Departure time\n");
for(ii = 1; ii <= Njobs; ii++) {
kk = revindex[ii];
}
// calculate number of trips for each truck
jobByTruck = imatrix(1, Ntrucks, 1, Njobs);
for(jj = 1; jj <= Ntrucks; jj++) {
for(ii = 1; ii <= Njobs; ii++) {
jobByTruck[jj][ii]=0;
}
}
for(jj = 1; jj <= Ntrucks; jj++) {
Ntrips[jj] =0; kk =0;
for(ii = 1; ii <= Njobs; ii++) {
if (truckAvail[revindex[ii]] == jj) {
kk=kk+1;
Ntrips[jj] = Ntrips[jj]+1;
jobByTruck[jj][kk] = ii;
}
}
}
for(jj = 1; jj <= Ntrucks; jj++) {
printf( " %4d % 4d\n", jj, Ntrips[jj]);
}
printf( " Jobs by each truck\n");
for(jj = 1; jj <= Ntrucks; jj++) {
printf(" Truck No = %4d\n", jj);
for(ii = 1; ii <= Ntrips[jj]; ii++) {
printf("%4d\n", jobByTruck[jj][ii]);
}
}
printf("truck job Arrival time\n");
for(jj = 1; jj <= Ntrucks; jj++) {
ii = jobByTruck[jj][1];
kk = revindex[ii];
y[jj]=ii;
xarr[jj] = Tarr[kk][truckAvail[kk]];
// printf( " %4d % 4d\n", jj,jobByTruck[jj][1]);
printf( " %4d %4d %3.2f\n", jj,ii,Tarr[kk][truckAvail[kk]]);
}
//sortthe last Ntrucks arrival times
piksr2(Ntrucks, xarr, y);
printf("Arrival times in ascending order\n");
for(jj = 1; jj <= Ntrucks; jj++) {
printf("xarr[jj]=%3.2f y[jj]=%d\n", xarr[jj], y[jj]);
}
for(jj = 1; jj <= Ntrucks; jj++) {
ii = jobByTruck[jj][1];
kk = revindex[ii];
diff[jj]= xarr[Ntrucks] - Tarr[kk][truckAvail[kk]];
printf("diff[jj]=%3.2f \n", diff[jj]);
}
// re run the algorithm
tt=0; ii=0;
while (tt< Njobs) {
ii=ii+1;
for(kk =1; kk <= Ntrucks; kk++) {
tt = tt+1;
jobseq[tt] = jobByTruck[kk][ii];
if (tt==Njobs) break;
}
}
printf("makespan=%3.2f\n", makespan);
for(ii = 1; ii <= Njobs; ii++) {
printf("jobseq[ii]=%4d\n", jobseq[ii]);
}
printf("Job ArrTime DepTime\n");
for(ii = 1; ii <= Njobs; ii++) {
kk = revindex[ii];
// printf( " %4d % 4d %3.2f %3.2f\n", ii, truckAvail[kk], Tarr[kk][truckAvail[kk]], Tdep[kk][truckAvail[kk]]);
TA[kk]= makespan-Tdep[kk][truckAvail[kk]] ;
TD[kk] = TA[kk] +s[kk];
printf("%4d %4.2f %4.2f\n", ii, TA[kk], TD[kk]);
}
fprintf(f1,"\n\nMakespan=%6.2f\n",makespan);
fprintf(f1,"Total Cost=%6.2f\n",total);
fprintf(f1,"Total waiting=%6.2f\n",waiting);
fclose(f1);
return 0;
} /* end of main */
Complexity of greedy algorithm
Greedy Algorithm: first loop (i=1 to Ntrucks) „³ complexity=Ntrucks
Second loop (i= Ntrucks+1 to Njobs) inside loop (k=1 to i)
„³ Complexity= (Njobs-Ntrucks-1)*Njobs
Total complexity =O ((Njobs)2)where O(n) is big O function
Complexity is the same for reverse greedy
Start
Input Njobs, Ntrucks, si ,di
Assign job i to available truck i
i<=Ntrucks
i=1
Ouput results
Calculate Tdi,Tai, Wi
i=Ntrucks+1
i<=Njobs
k<=i
Assign job i to available truckavial
Calculate Tdi,Tai, Wi
End
Calculate truckavial
k=1
Appendix E
List of publications
1. Dayoub M, Suhaib S and Khan R. A, Shipport’s handling Equipment-A Review, Proceedings of National Conference on emerging Trends in Manufacturing Systems (ETMS-2005), Seth Jai Parkash Mukand Lal Insititute of Engineering & Technology (JMIT) Radaur (Yamuna Nagar) ISO 9001: 2000 Certified , March 15-16, 2005
2. Dayoub M, Suhaib S and Khan R. A, Material handling Equipment-A Review, Proceedings of National Conference on Recent Trends in Design and Manufacturing Technologies (RTDMT-2005), Kumaraguru College of Technology, Coimbatore (Tamil Naidu), March 17-18, 2005.
3. Dayoub M, Suhaib S and Khan R. A, Technologies for containers movement in container terminal ¨C a survey, Proceedings of International Conference on Advances in Materials, Product Design and Manufacturing Systems (ICMPM 2005), Bannari Amman Institute of Technology, Sathyamangalalam (Tamil Nadu), December’ 2005.
4. Dayoub M. Suhaib M. and Khan R.A., Loading and Unloading Containers Operations at Container terminal and application of greedy algorithm, Proceedings of Advances in Mechanical Engineering (AIME 2006), Faculty of Engineering and Technology Jamila Millia Islamia, New Delhi, January 20-21, 2006.
5. Dayoub M. Sharif M, .Rakesh N, and Khan R.A.,Selection of Material Handling Equipments Using Expert System , Proceedings of International Conference on Advances in Manufacturing Engineering,(ICAME-2007), Department of Mechanical and manufacturing Engineering ,MIT, Manipal.October 24-26 -2007.