Chapter 1



Some Studies on the Principles and Mechanisms for Loading and UnloadingA thesisSubmitted in Fulfilment of the Requirements for the Award of the Degree of Doctor of Philosophy(In Mechanical Engineering)ByMudar DayoubUnder the Supervision ofProf. Rasheed Ahmad KhanDr. Mohammed Sharif&2028355360293Dr. Mohammed SuhaibDepartment of Mechanical EngineeringFaculty of Engineering and TechnologyJamia Millia IslamiaNew Delhi2009AbstractContainerization of general cargo has been increasing steadily over the last three decades. The world container turnover increased from 76 million TEU in year 1988 to 544 million TEU in year 2008. As a result of substantial increase in world container turnover, container terminals have become an important component of the global transportation network. Container terminals serve the function of delivering containers to consignees and receiving containers from shippers, loading containers onto and unloading containers from vessels, trains, trucks, and then temporarily storing the containers in the storage yard. The productivity of container terminals is often measured in terms of the time necessary to load and unload containers by cranes and trucks, which are the most important and expensive equipment used in ports. Most container terminals have either initiated or in the process of initiating measures to increase their throughput and capacity by introducing new technologies, reducing equipment dwell times, and increasing storage density.Transportation of containers between the quayside and the storage yard can be divided into a number of sub-processes according to the type of equipment involved. In most container terminals, trucks are commonly used for transporting containers between the quayside and the storage-yard. Determining the sequence of containers to be handled by trucks is one of the major issues in terminal operations. The operation efficiency of container terminals is directly impacted by the container sequencing decisions. Therefore, the major objective of this research is to develop generic models that can be used to solve truck scheduling problem that is the problem of scheduling a fleet of trucks to handle a set of non-preemptive jobs with sequence-dependent processing times and different arrival times. This objective is achieved through optimizing the makespan for loading and unloading containers in the container terminal using mixed integer programming and greedy search algorithms. The intent behind optimizing the makespan is (1) to reduce the waiting time of the trucks, (2) to cut down the operation costs, (3) to find the optimal number of trucks to be used for loading and unloading containers to and from trains and (4) to contribute towards improvement in the national economy.In this research, development and implementation of several studies has been carried out for optimal scheduling of loading and unloading operations in container terminals. A generic model based on mixed integer programming (MIP) has been developed and its effectiveness in scheduling container loading and unloading operations has been studied. In addition to MIP model, four generic models based on different scheduling algorithms have been developed in this research. The performance of these models has been evaluated in terms of the quality of solution achieved by them. Comparison of the performance of MIP model with that of other models has revealed that although MIP model is able to produce optimal solutions but its execution time is quite high. Due to the high execution time requirements, it was concluded that MIP model has limited practical applicability to real world problems.Major achievements of the research carried out in this thesis may be summarized as follows:A comprehensive review of literature related to application of optimization techniques for improving container terminal operations has been carried out with a view to provide ready reference for any future work.A comprehensive review of processes being followed, and equipment being used in container terminals has been carried out in order to put the work carried out in this research in context.Real-world data pertaining to processing time and travel time for each container has been procured from CONCOR, and has been used to test the developed modelsA generic MIP model that is transportable to any other container terminal with minimal changes has been developed for the truck scheduling problemAnalysis of several computational experiments carried out using the MIP model has revealed that the execution time requirements are quite high for solving even moderate size problems, thereby ruling out the application of MIP model to large real-world problemsFour generic models based on STF, LTF, FAT, and LBT scheduling mechanisms have been developed and their practicality in solving complex problems has been demonstrated through application to four real-world problems.It has been demonstrated that the application of recommended models for unloading different number of train could lead to substantial savings in the cost of operationsA distinct practical advantage of the model developed in this work are that they are transportable to any other container terminal without any difficultyModels developed in this work can be used by terminal operations managers for optimizing container terminal processesModels recommended in this work provide a wider choice to the terminal managers as well as to customersFinally, implementation of models developed in this work is straightforward due to the ease of interfacingDeclaration of OriginalityThis work reported in this thesis entitled “Some Studies on the Principles and Mechanisms for Loading and Unloading” was conducted entirely by me in the Department of Mechanical Engineering at the Faculty of Engineering and Technology, Jamia Millia Islamia, New Delhi, India. The matter embodied in this thesis has not been submitted in part or full to any other University/institution for the award of any degree or diploma.Mudar Dayoub01 July 2009CertificateThis is to certify that the thesis entitled “Some Studies on the Principles and Mechanisms for Loading and Unloading” submitted in fulfilment for the requirement of award of degree of Doctor of Philosophy is a record of bonafide work carried out by Mudar Dayoub under our supervision and guidance.To the best of our knowledge the matter embodied in this dissertation has not been submitted in part or full to any other University/institution for the award of any degree. (Rasheed Ahmad Khan, Ph.D)ProfessorDepartment of Mechanical EngineeringFaculty of Engineering and TechnologyJamia Millia IslamiaNew Delhi-110025(Mohammed Sharif, Ph.D)Associate ProfessorDepartment of Civil EngineeringFaculty of Engineering and TechnologyJamia Millia IslamiaNew Delhi-110025(Mohammed Suhaib, Ph.D)Associate ProfessorDepartment of Mechanical EngineeringFaculty of Engineering and TechnologyJamia Millia IslamiaNew Delhi-110025AcknowledgementsI am extremely grateful to my thesis supervisor Prof. R A Khan who has provided valuable guidance for accomplishing this project work. He has been benevolent enough to take time out from his busy schedule for this project and supported me in every respect. I am deeply indebted to my thesis co-supervisor Dr. Mohammed Sharif for his continuous support, stimulating suggestions and patience. It would not have been possible to complete this thesis without his encouragement and trust. I have learned a lot from his broad and profound knowledge during the long hours that we have spent together.I am also grateful to my co-supervisor Dr Mohammed Suhaib for his whole hearted support , who has guided me at the start of this thesis work and introduced me to the ICD, Tughlakabad, authorities, where ideas for this Thesis work all got started.In researching container terminals, loading and loading operations, I have met many colourful and interesting people from academia and industry that have helped tremendously. Mr. A. K. Mishra, operation Manager , Mr. Tomar, Supervisor of the Container Corporation of India Ltd., Inland Container Depot, Tughlakabad, New Delhi for their valuable suggestion and support. And Mr. Leela Dhar Kala, IIT Delhi, In the course of the working on this thesis, I had the fortune of meeting many fine friends who assisted me in various forms. I would like to thank all of them. Lastly, I would like to thank my family for their unceasing love and support of my endeavour, in particular, my mother my brothers and my sister. There is no way I have could have done this without their tremendous sacrifice.Mudar DayoubDate: 01, July 2009Place: New DelhiContents TOC \o "1-3" \h \z \t "Content Heading,4" Abstract PAGEREF _Toc234153696 \h iiDeclaration of Originality PAGEREF _Toc234153697 \h vCertificate PAGEREF _Toc234153698 \h viAcknowledgements PAGEREF _Toc234153699 \h viiContents PAGEREF _Toc234153700 \h viiiList of Figures PAGEREF _Toc234153701 \h xiiList of Tables PAGEREF _Toc234153702 \h xvList of Abbreviations PAGEREF _Toc234153703 \h xviii1.INTRODUCTION PAGEREF _Toc234153704 \h 11.1General PAGEREF _Toc234153705 \h 11.2World containerized trade PAGEREF _Toc234153706 \h 11.3Port scenario in India PAGEREF _Toc234153707 \h 41.3.1Performance of Indian ports PAGEREF _Toc234153708 \h 51.4Containers PAGEREF _Toc234153709 \h 71.4.1Types of containers PAGEREF _Toc234153710 \h 91.4.2Advantages and disadvantages PAGEREF _Toc234153711 \h 121.4.3Identification system PAGEREF _Toc234153712 \h 131.5Container terminal structure and handling equipment PAGEREF _Toc234153713 \h 141.5.1Processes at container terminal PAGEREF _Toc234153714 \h 151.5.2Technologies for movement of containers PAGEREF _Toc234153715 \h 171.5.3Container handling equipment PAGEREF _Toc234153716 \h 191.6Recent technologies for container loading -unloading PAGEREF _Toc234153717 \h 241.6.1Automated guided vehicles PAGEREF _Toc234153718 \h 241.6.2Automated lifting vehicle PAGEREF _Toc234153719 \h 251.6.3Linear motor conveyance system PAGEREF _Toc234153720 \h 261.6.4Overhead grid rail technology PAGEREF _Toc234153721 \h 271.6.5Automated storage/retrieval system PAGEREF _Toc234153722 \h 271.6.6Assisting systems PAGEREF _Toc234153723 \h 281.7Participants at container terminals PAGEREF _Toc234153724 \h 291.8Problem statement PAGEREF _Toc234153725 \h 292.LITERATURE REVIEW PAGEREF _Toc234153726 \h 322.1General PAGEREF _Toc234153727 \h 322.2Optimization techniques PAGEREF _Toc234153728 \h 322.2.1Mathematical model PAGEREF _Toc234153729 \h 332.2.2Linear programming PAGEREF _Toc234153730 \h 352.2.3Non-linear programming PAGEREF _Toc234153731 \h 362.2.4Mixed integer programming PAGEREF _Toc234153732 \h 372.2.5Simulation PAGEREF _Toc234153733 \h 382.2.6Branch and bound algorithms PAGEREF _Toc234153734 \h 392.2.7Heuristic models PAGEREF _Toc234153735 \h 412.3Literature review of container terminal processes: PAGEREF _Toc234153736 \h 412.3.1Arrival of containers PAGEREF _Toc234153737 \h 422.3.2Loading and unloading of containers PAGEREF _Toc234153738 \h 442.3.3Transport of containers from quayside to stack and vice versa PAGEREF _Toc234153739 \h 472.3.4Stacking of containers PAGEREF _Toc234153740 \h 492.3.5Inter-terminal container transport PAGEREF _Toc234153741 \h 532.3.6Complete container terminals PAGEREF _Toc234153742 \h 543.Container Terminal Operations PAGEREF _Toc234153743 \h 563.1Operations at Singapore port PAGEREF _Toc234153744 \h 563.2Operations at container terminals in India PAGEREF _Toc234153745 \h 583.2.1Container corporation of India PAGEREF _Toc234153746 \h 593.2.2Financials PAGEREF _Toc234153747 \h 603.2.3Physical performance PAGEREF _Toc234153748 \h 613.3Case study at ICD, Tughlakabad, New Delhi PAGEREF _Toc234153749 \h 623.3.1Facilities and Equipment PAGEREF _Toc234153750 \h 633.3.2Loading-unloading operations at ICD, Tughlakabad PAGEREF _Toc234153751 \h 653.3.3Rail Side operations PAGEREF _Toc234153752 \h 653.3.4Storage yard operation PAGEREF _Toc234153753 \h 673.3.5Gate operation PAGEREF _Toc234153754 \h 683.3.6Summary of operations at ICD, Tughlakabad PAGEREF _Toc234153755 \h 684.Mathematical Model Formulation PAGEREF _Toc234153756 \h 704.1Introduction PAGEREF _Toc234153757 \h 704.2Problem description PAGEREF _Toc234153758 \h 704.3Truck dispatching model formulation PAGEREF _Toc234153759 \h 724.4Solution of truck dispatching problem PAGEREF _Toc234153760 \h 755.Solution Mechanisms PAGEREF _Toc234153761 \h 785.1Introduction PAGEREF _Toc234153762 \h 785.2Greedy algorithm PAGEREF _Toc234153763 \h 795.2.1Elements of a GA PAGEREF _Toc234153764 \h 795.3Types of GA PAGEREF _Toc234153765 \h 825.3.1Greedy algorithm and scheduling problems PAGEREF _Toc234153766 \h 835.4Solution using GA PAGEREF _Toc234153767 \h 835.4.1Assumptions PAGEREF _Toc234153768 \h 845.4.2GA for unloading container operation PAGEREF _Toc234153769 \h 865.4.3Greedy algorithm for loading container operation PAGEREF _Toc234153770 \h 915.4.4Reverse greedy algorithm for loading container operation PAGEREF _Toc234153771 \h 925.4.5Solution using shortest job time first scheduling algorithm PAGEREF _Toc234153772 \h 965.4.6Solution using largest job time first scheduling algorithm PAGEREF _Toc234153773 \h 986.Model Application to Real World Case Studies PAGEREF _Toc234153774 \h 1016.1Case study 1 PAGEREF _Toc234153775 \h 1026.1.1Makespan for unloading operations PAGEREF _Toc234153776 \h 1036.1.2Computation of makespan for loading operations PAGEREF _Toc234153777 \h 1046.1.3Cost of unloading operations PAGEREF _Toc234153778 \h 1056.1.4Cost of loading operation PAGEREF _Toc234153779 \h 1066.1.5Waiting time of unloading operation PAGEREF _Toc234153780 \h 1076.1.6Waiting time of loading operation PAGEREF _Toc234153781 \h 1086.2Case study 2 PAGEREF _Toc234153782 \h 1096.2.1Makespan for unloading operations PAGEREF _Toc234153783 \h 1116.2.2Makespan for loading operations PAGEREF _Toc234153784 \h 1126.2.3Cost of unloading operations PAGEREF _Toc234153785 \h 1136.2.4Cost of loading operations PAGEREF _Toc234153786 \h 1146.2.5Waiting time for unloading operations PAGEREF _Toc234153787 \h 1156.2.6Waiting time for loading operations PAGEREF _Toc234153788 \h 1166.3Case study 3 PAGEREF _Toc234153789 \h 1176.3.1Makespan for unloading operations PAGEREF _Toc234153790 \h 1206.3.2Makespan for loading operations PAGEREF _Toc234153791 \h 1216.3.3Cost for unloading operations PAGEREF _Toc234153792 \h 1226.3.4Cost for loading operations PAGEREF _Toc234153793 \h 1236.3.5Waiting time for unloading operations PAGEREF _Toc234153794 \h 1246.3.6Waiting time for loading operations PAGEREF _Toc234153795 \h 1256.4Case study 4 PAGEREF _Toc234153796 \h 1266.4.1Makespan for unloading operations PAGEREF _Toc234153797 \h 1296.4.2Makespan for loading operations PAGEREF _Toc234153798 \h 1306.4.3Cost for unloading operation PAGEREF _Toc234153799 \h 1316.4.4Cost for loading operation PAGEREF _Toc234153800 \h 1326.4.5Waiting time for unloading operation PAGEREF _Toc234153801 \h 1336.4.6Waiting time of loading operation PAGEREF _Toc234153802 \h 1346.5Summary of loading and unloading results PAGEREF _Toc234153803 \h 1356.6Analysis of models results PAGEREF _Toc234153804 \h 1396.6.1Optimal number of trucks PAGEREF _Toc234153805 \h 1396.6.2Optimal makespan PAGEREF _Toc234153806 \h 1416.6.3Optimal cost PAGEREF _Toc234153807 \h 1436.6.4Optimal waiting time PAGEREF _Toc234153808 \h 1456.7Recommended Models PAGEREF _Toc234153809 \h 1477.Conclusions and future work PAGEREF _Toc234153810 \h 1537.1Achievement of the thesis PAGEREF _Toc234153811 \h 1547.2Limitations of the research PAGEREF _Toc234153812 \h 1577.3Recommendations for further research PAGEREF _Toc234153813 \h 157References PAGEREF _Toc234153814 \h 159Appendix A PAGEREF _Toc234153815 \h 176Appendix B PAGEREF _Toc234153816 \h 180Appendix C PAGEREF _Toc234153817 \h 183Appendix D PAGEREF _Toc234153818 \h 184Appendix E PAGEREF _Toc234153819 \h 204List of Figures TOC \h \z \c "Figure" Figure 1.1 Growth of world container turnover from 1988 to 2008 PAGEREF _Toc234141350 \h 2Figure 1.2 Continent-wise turnover of containers PAGEREF _Toc234141351 \h 2Figure 1.3 Growth rate of real GDP in India PAGEREF _Toc234141352 \h 5Figure 1.4 Traffic handled at major and minor ports of India PAGEREF _Toc234141353 \h 6Figure 1.5 Share of principle commodities handled at major ports: 2005-2006 PAGEREF _Toc234141354 \h 6Figure 1.6 Growth of world maritime trade versus containers 1987 to 2004 PAGEREF _Toc234141355 \h 8Figure 1.7 Forty feet normal, forty feet high cube, and twenty feet containers PAGEREF _Toc234141356 \h 10Figure 1.8 Example of container ID PAGEREF _Toc234141357 \h 14Figure 1.9 view of containership PAGEREF _Toc234141358 \h 15Figure 1.10 Process of loading –unloading containers PAGEREF _Toc234141359 \h 16Figure 1.11 Different types of handling equipment and their stacking capacity PAGEREF _Toc234141360 \h 18Figure 1.12 Straddle carrier at Singapore port PAGEREF _Toc234141361 \h 19Figure 1.13 Reach Stacker at ICD, Tughlakabad PAGEREF _Toc234141362 \h 20Figure 1.14 Multi-trailers at the port of Rotterdam PAGEREF _Toc234141363 \h 21Figure 1.15 Rail mounted gantry crane at CONCOR, Tughlakabad, New Delhi. PAGEREF _Toc234141364 \h 22Figure 1.16. Quay crane at port of Paranaque, Brazil. PAGEREF _Toc234141365 \h 23Figure 1.17 Automated guided vehicle used at Rotterdam port. PAGEREF _Toc234141366 \h 25Figure 1.18 Linear motor conveyance system PAGEREF _Toc234141367 \h 26Figure 2.1 View of container terminal. PAGEREF _Toc234141368 \h 41Figure 2.2 (a) Single cycling unloading (b) Double cycling unloading and loading. PAGEREF _Toc234141369 \h 46Figure 2.3 Yard crane and a container block PAGEREF _Toc234141370 \h 50Figure 3.1 Container throughput at Singapore PAGEREF _Toc234141371 \h 56Figure 3.2 Total traffic handled at CONCOR terminals PAGEREF _Toc234141372 \h 61Figure 3.3 ICD, Tughlakabad, New Delhi PAGEREF _Toc234141373 \h 62Figure 3.4 Schematic of ICD, Tughlakabad. PAGEREF _Toc234141374 \h 64Figure 3.5 Rail mounted gantry crane PAGEREF _Toc234141375 \h 66Figure 3.6 Truck used for transhipment of containers PAGEREF _Toc234141376 \h 66Figure 3.7 Part of storage yard in CONCOR served with TMGC. PAGEREF _Toc234141377 \h 67Figure 4.1Layout of ICD, Tughlakabad PAGEREF _Toc234141378 \h 76Figure 5.1 Flow chart of scheduling mechanism PAGEREF _Toc234141379 \h 78Figure 5.2 The greedy algorithm for an unloading job sequence using FAT principle PAGEREF _Toc234141380 \h 90Figure 5.3 GA for an loading job sequence using FAT principle PAGEREF _Toc234141381 \h 91Figure 5.4. Reverse greedy algorithm for loading containers using LBT principle PAGEREF _Toc234141382 \h 96Figure 5.5 STF scheduling algorithm for unloading containers PAGEREF _Toc234141383 \h 98Figure 5.6 The LTF scheduling algorithm for unloading containers PAGEREF _Toc234141384 \h 100Figure 6.1 Comparison of makespan for unloading one train PAGEREF _Toc234141385 \h 103Figure 6.2 Comparison of makespan for loading one train PAGEREF _Toc234141386 \h 104Figure 6.3 Comparison of cost of unloading one train PAGEREF _Toc234141387 \h 106Figure 6.4 Comparison of cost of loading one train PAGEREF _Toc234141388 \h 107Figure 6.5 Comparison of waiting time for unloading one train PAGEREF _Toc234141389 \h 108Figure 6.6 Comparison of waiting time for loading one train PAGEREF _Toc234141390 \h 109Figure 6.7 Comparison of makespan for unloading two trains PAGEREF _Toc234141391 \h 112Figure 6.8 Comparison of makespan of unloading two trains PAGEREF _Toc234141392 \h 113Figure 6.9 Comparison of cost for unloading two trains PAGEREF _Toc234141393 \h 114Figure 6.10 Comparison of cost for loading two trains PAGEREF _Toc234141394 \h 115Figure 6.11 Comparison of waiting time for unloading two trains PAGEREF _Toc234141395 \h 116Figure 6.12 Comparison of waiting time for loading two trains PAGEREF _Toc234141396 \h 117Figure 6.13 Comparison of makespan for unloading three trains PAGEREF _Toc234141397 \h 120Figure 6.14 Comparison of makespan for loading three trains PAGEREF _Toc234141398 \h 121Figure 6.15 Comparison of cost for unloading three trains PAGEREF _Toc234141399 \h 122Figure 6.16 Comparison of cost for loading three trains PAGEREF _Toc234141400 \h 123Figure 6.17 Comparison of waiting time for unloading three trains PAGEREF _Toc234141401 \h 124Figure 6.18 Comparison of waiting time for loading of three trains PAGEREF _Toc234141402 \h 125Figure 6.19 Comparison of makespan for unloading four trains PAGEREF _Toc234141403 \h 130Figure 6.20 Comparison of makespan for loading three trains PAGEREF _Toc234141404 \h 131Figure 6.21 Comparison of cost of unloading four trains PAGEREF _Toc234141405 \h 132Figure 6.22 Comparison of cost for loading four trains PAGEREF _Toc234141406 \h 133Figure 6.23Comparison of waiting time for unloading four trains PAGEREF _Toc234141407 \h 134Figure 6.24 Comparison of waiting time for loading four trains PAGEREF _Toc234141408 \h 135Figure 6.25 Number of trucks versus number of trains in unloading process PAGEREF _Toc234141409 \h 140Figure 6.26 Number of trucks versus number of trains in loading process PAGEREF _Toc234141410 \h 140Figure 6.27 Number of trucks versus number of trains in loading-unloading process PAGEREF _Toc234141411 \h 141Figure 6.28 Makespan versus number of trains in an unloading process PAGEREF _Toc234141412 \h 142Figure 6.29 Makespan versus number of trains in a loading process PAGEREF _Toc234141413 \h 142Figure 6.30 Makespan versus number of trains in loading and unloading process PAGEREF _Toc234141414 \h 143Figure 6.31 Cost versus number of trains in unloading process PAGEREF _Toc234141415 \h 144Figure 6.32 Cost versus number of trains in loading process PAGEREF _Toc234141416 \h 144Figure 6.33 Cost versus number of trains in combined loading-unloading process PAGEREF _Toc234141417 \h 145Figure 6.34 Waiting time versus number of trains in an unloading process PAGEREF _Toc234141418 \h 146Figure 6.35 Waiting time versus number of trains in loading Process PAGEREF _Toc234141419 \h 146Figure 6.36 Waiting time versus number of trains in combined loading-unloading process PAGEREF _Toc234141420 \h 147List of Tables TOC \h \z \c "Table" Table 1.1 Busiest ports in the World in 2004 versus 2007 PAGEREF _Toc234141421 \h 3Table 1.2 Average allocation of funds in the Indian public transport sector PAGEREF _Toc234141422 \h 7Table 1.3 Dimensions f ISO and non- ISO containers PAGEREF _Toc234141423 \h 10Table 1.4 Types of containers PAGEREF _Toc234141424 \h 11Table 2.1 Categorization of optimization techniques PAGEREF _Toc234141425 \h 33Table 3.1Characteristics of Singapore Container Port (2007) PAGEREF _Toc234141426 \h 57Table 3.2 Summary of loading/unloading operations at ICD, Tughlakabad PAGEREF _Toc234141427 \h 68Table 4.1 Input data for truck dispatching problem PAGEREF _Toc234141428 \h 75Table 4.2 Output from MIP model PAGEREF _Toc234141429 \h 75Table 4.3 Computational time requirements for combinations of number of trucks and containers PAGEREF _Toc234141430 \h 77Table 5.1 Performance Comparison of GA and MIP PAGEREF _Toc234141431 \h 90Table 5.2 Schedule obtained using STF algorithm PAGEREF _Toc234141432 \h 98Table 5.3 Schedule obtained using LTF algorithm PAGEREF _Toc234141433 \h 99Table 6.1 Four different real world case studies PAGEREF _Toc234141434 \h 101Table 6.2 Input data for case study 1 PAGEREF _Toc234141435 \h 102Table 6.3 Minimum makespan and the corresponding number of trucks of unloading operation PAGEREF _Toc234141436 \h 104Table 6.4 Minimum makespan and the corresponding number of trucks for loading operation PAGEREF _Toc234141437 \h 105Table 6.5 Comparison of costs for unloading operations PAGEREF _Toc234141438 \h 106Table 6.6 Comparison of costs for loading operations PAGEREF _Toc234141439 \h 107Table 6.7 Comparison of waiting time for unloading operations PAGEREF _Toc234141440 \h 108Table 6.8 Comparison of waiting time for loading operations PAGEREF _Toc234141441 \h 109Table 6.9 Input data for case study 2 PAGEREF _Toc234141442 \h 110Table 6.10 Minimum makespan and the corresponding number of trucks for unloading operations PAGEREF _Toc234141443 \h 112Table 6.11 Minimum makespan for loading two trains PAGEREF _Toc234141444 \h 113Table 6.12 Operation cost for unloading two trains PAGEREF _Toc234141445 \h 114Table 6.13 Operation cost for loading two trains PAGEREF _Toc234141446 \h 115Table 6.14 Waiting time for unloading two trains PAGEREF _Toc234141447 \h 116Table 6.15 Waiting time for loading two trains PAGEREF _Toc234141448 \h 117Table 6.16 Input data for case study 3 PAGEREF _Toc234141449 \h 118Table 6.17 Minimum Makespan for unloading three trains PAGEREF _Toc234141450 \h 121Table 6.18 Minimum makespan for loading three trains PAGEREF _Toc234141451 \h 122Table 6.19 Operation cost for unloading three trains PAGEREF _Toc234141452 \h 123Table 6.20 Operation Cost for loading three trains PAGEREF _Toc234141453 \h 124Table 6.21 Waiting time for unloading three trains PAGEREF _Toc234141454 \h 125Table 6.22 Waiting Time for loading three trains PAGEREF _Toc234141455 \h 126Table 6.23 Input data of case study 4 PAGEREF _Toc234141456 \h 126Table 6.24 Minimum makespan for unloading four trains PAGEREF _Toc234141457 \h 130Table 6.25 Minimum makespan for loading four trains PAGEREF _Toc234141458 \h 131Table 6.26 Comparison of operation cost for unloading four trains PAGEREF _Toc234141459 \h 132Table 6.27 Operation cost of for loading four trains PAGEREF _Toc234141460 \h 133Table 6.28 Waiting time for unloading four trains PAGEREF _Toc234141461 \h 134Table 6.29 Waiting time for loading four trains PAGEREF _Toc234141462 \h 135Table 6.30 Summary of minimum makespan for loading-unloading operations PAGEREF _Toc234141463 \h 136Table 6.31 Summary of cost corresponding to the minimum makespan for loading and unloading operations PAGEREF _Toc234141464 \h 137Table 6.32 Summary of waiting time corresponding to the minimum makespan for loading and unloading operations PAGEREF _Toc234141465 \h 138Table 6.33 Recommended models for loading and unloading one train PAGEREF _Toc234141466 \h 148Table 6.34 Recommended models for loading and unloading two trains PAGEREF _Toc234141467 \h 149Table 6.35 Recommended models for loading and unloading three trains PAGEREF _Toc234141468 \h 150Table 6.36 Recommended models for loading and unloading four trains PAGEREF _Toc234141469 \h 150Table 6.37 Computations for savings in cost for one train PAGEREF _Toc234141470 \h 152Table 6.38 Computations for time savings for unloading one train PAGEREF _Toc234141471 \h 152Table 6.39Computations for resource savings for one train PAGEREF _Toc234141472 \h 152List of AbbreviationsAGVsAutomated Guided VehiclesAISC All India shippers CouncilALVAutomated lifting VehicleAS/RS Automated Storage and Retrieval StructureASCs Automated Stacking CranesBAP Berth Allocating Problem BARSYLBalaji Railroad Systems LimitedCFSs Container Freight StationsCONCOR Container Corporation of India, Ltd CTContainer Terminal DGSDirectorate General of ShippingECT European Container TerminalEDIFACTElectronic Data Interchange For Administration, Commerce and TransportESCAPEconomic and Social Commission for Asia and the PacificEXIM Export – ImportFATFirst Available TruckFEUForty-feet Equivalent UnitGAGreedy AlgorithmGDPGross Domestic Product HCHigh CubicINFORMSInstitute for Operations Research and the Management SciencesICDInland Container DepotIDIdentification DetailsITCTInter-Terminal Container TransportINSAIndian National Ship-owners AssociationISOInternational Organization for StandardizationKMIKorea Maritime InstituteKPMGKnowledge Partner ManagementLBTLast Busy TruckLMCSLinear Motor Conveyance System LPLinear programmingLTFLargest Time FirstMBPP Master Bay Plan ProblemMIPMixed Integer ProgrammingMTMillion TonnesMTSMultiple Trailer SystemNLPNon-Linear ProgrammingOHBCOver-Head Bridge CranesPPTPasir Panjang TerminalPSAPort of Singapore Authority QCQuay CraneRMGCRail-Mounted Gantry CraneRTGCRubber Tired Gantry CraneSCIShipping Corporation of IndiaSCStraddle CarrierSKUStock Keeping- UnitsSTFShortest Time FirstTTonneTEU Twenty feet Equivalent UnitTKD TughlakabadUNCTADUnited Nations Conference on Trade and DevelopmentYCYard CraneYoYYear on YearINTRODUCTIONGeneralThe loading and unloading of materials is a human activity which has been performed since time immemorial. Due to rapid globalization of trade, many trade barriers have broken down during the last the few years. Loading and unloading of materials have become an important and specialized function in all trade activities. The importance of port handling and transportation systems has increased due to globalization of trade. Port handling and transportation systems include a network of terminals around the globe that allow manufacturers and shippers to deliver goods quickly to their customers. Increasing global trade has created the need for efficient container ports wherein the goal is to move containers as quickly as possible and at the minimum cost. Goods that are delayed at the port are inevitably tardy when delivered to the customer, and often incur late delivery charges. Two key activities in the port are (i) unloading of containers from truck and then storage in the export area, and (ii) removal of containers from storage area and then loading onto the trucks. Container terminals (CT) primarily serve as an interface between different modes of transportation, such as domestic rail or truck transportation and deep sea maritime transport. Worldwide container trade is growing at an annual rate of 9.5%. Percentage of containerized trade in the world sea borne trade has increased from 5.8% in 1988 to 14.9% in 2006 and it is expected to go up to 35% by 2020 (Sabonge, 2006). It is anticipated that the growth in containerized trade will continue as more and more cargo is transferred from break-bulk to containers.World containerized tradeThe use of container as a universal carrier for various goods has increased rapidly during the last century. It has become a standard in worldwide transportation due to rapid increase in containerization operations over the recent years. As result of increasing world trade, new container terminals are being built and existing ones are expanded.Figure ?1.1 Growth of world container turnover from 1988 to 2008Figure ?1.2 Continent-wise turnover of containers REF _Ref233629284 \h Figure ?1.1 shows the growth of world container turnover. Over the last two decades (1988 - 2008), the use of containers for intercontinental maritime transport has rapidly increased. Starting with 76 million twenty feet equivalent unit (TEU) in year 1988, world container turnover has reached more than 544 Million TEU in year 2008 (Drewry, 2007a). A further continuous increase in container turnover is expected in the upcoming years, especially in Asia and Europe. REF _Ref233629298 \h Figure ?1.2 shows the container turnover of different continents. Containerized trade in 2008 has shown growth of the container turnover more than 5 times since the year 1989 (Etzelmueller, 2006). The world’s top 20 container ports handled 166.7 million TEU in 2004, accounting for 49.6 per cent of the world’s container port throughput, which is defined as the average number of containers being loaded and unloaded per hour per quay crane (QC). Table STYLEREF 1 \s ?1. SEQ Table \* ARABIC \s 1 1 Busiest ports in the World in 2004 versus 2007Rank 2004Rank2007portCountry2004(TEU)2007 (TEU)Percentage change13 Hong KongChina21,984,00023,881,000+8.6%21SingaporeSingapore21,329,00027,932,000+31%32ShanghaiChina14,557,00026,150,000+79.6%44 ShenzhenChina13,615,00021,099,000+55%55BussanSouth Korea11,430,00013,270,000+16%68KaohsiungTaiwan9,714.0009,774,670+0.6276RotterdamNetherlands8,281,00010,790,600+30.3%8-*Los AngelsUS7,321,0007,702,00099HamburgGermany7,003,0008,861,454+30.3%107DubaiUnited Arab emirates7,702,0008,923,456+15.9%*It indicates the port of Qingdao in China which had a rank of 10 in the year 2007 (Source: Drewry, 2007b) REF _Ref226854951 \h Table ?1.1 presents the volume of container traffic in TEU for the most busy container terminals in the world in the year 2004 versus year 2007. The world’s top 3 container ports in terms of container throughput were Singapore, Hong Kong, and Shanghai. The port of Singapore is described in chapter 3 of this thesis. In the Asian and Pacific region, the concentration of port throughput is even more prominent, with the 10 busiest ports handling 110 million TEU or 61.3 percent of the region’s total throughput in 2004. The world’s six busiest container ports are located in the United Nations Economic and Social Commission for Asia and the Pacific (ESCAP) region, handling 27.4 per cent of world container throughput amounting to 51.1 percent of the ESCAP total. Within the South and South-West Asia sub-region, container throughput growth for Bangladesh, India and Sri Lanka has been strong. Growth in Bangladesh reached nearly 20 percent per annum during the second half of the 1990s. While Bangladesh and India suffered only a modest slowdown in 2001, the Sri Lankan transhipment port of Colombo was severely affected, recording a small absolute decline in container throughput. However, in 2003 Bangladesh recorded a comparatively strong growth rate of 19.1 per cent. The port scenario in India is briefly discussed in next section.Port scenario in IndiaIndia is one of the world’s fastest-growing economies where the gross domestic product (GDP) showed a growth of 9.2% in 2006. India has shown an average growth of 7.6% in the 10th five year plan (2002-2007) compared to a global growth rate of 3.7%. (Lahiri, 2006). But due to global financial crisis, this growth slowed down in India from 8.9 % to 7% (Vos, 2008) REF _Ref234071514 \h Figure ?1.3 shows that GDP in India has grown at a fast pace from 4.5 percent in the year 2001 to 11.5 percent in the year 2005. However, the pace of growth has shown a decline in the recent years (2006-2009). One of the fields where India has made a significant progress is the transportation and ports facility. Over 95 percent of India's international trade by volume takes place through ports. However, due to the fast growing rate of the global container trade, Indian major ports are under the pressure of meeting the international demand.The concept of ocean going containers was introduced in India for the first time in 1968 in a seminar held jointly by the Indian National Ship-owners Association (INSA), Directorate General of Shipping (DGS), the Shipping Corporation of India Ltd. (SCI) and the All India shippers Council (AISC) at Bombay.Figure ?1.3 Growth rate of real GDP in IndiaThe 7517 km long Indian coastline has 12 major ports and 187 minor/ intermediate ports out of which 139 are operable (Banger, 2007) Ports serve as the gateways to the international trade in India and are handling over 90% of foreign trade. The major ports are located at Calcutta/ Haldia, Chennai, Cochin, Ennore, Jawaharlal Nehru Port at Nhava Sheva, Kandla, Mormugao, Mumbai, New Mangalore, Paradip, Tuticorin and Vishakhapatnam, and Mundra port in Gujrat.Performance of Indian ports The 12 major Indian ports, which are managed by the Port Trust of India under Central Government Jurisdiction, have handled 463.84 MT (million tonnes) of cargo in 2006-2007, a growth of 9.1% against the same period of the previous year (Ravi, 2007). As on 13-3-2007, these ports handled 509 MT of cargo with an average growth rate of 10%. REF _Ref234071576 \h Figure ?1.4 shows the performance of major and minor ports in India in terms of traffic handled between 1990 and 2007. The major ports handled 5.541 million TEU out of which the share of the principle commodities was 12%. The 187 minor ports are under the jurisdiction of the respective State Governments, and have handled 195 MT (million tonnes) of cargo in 2006-2007. The capacity of minor ports in India has a capacity of 228 MT as on 13-3-2007 with an average growth rate of 12.6 %, (Banger, 2007). During 2005-06, major ports handled a record traffic of 423.41 million tonnes with a growth rate of 10.3 percent over the previous year, which was higher than the growth in GDP. Figure ?1.4 Traffic handled at major and minor ports of India Figure STYLEREF 1 \s ?1. SEQ Figure \* ARABIC \s 1 5 Share of principle commodities handled at major ports: 2005-2006 Of the total traffic handled at major ports, petroleum products have the largest share of about 33 percent; iron ore, 20 percent; coal, 14 percent; containers, 14 percent; fertilizer, 3 % and the rest is shared by general cargo 16 percent as shown in REF _Ref226855284 \h Figure ?1.5 The performance of Indian ports does not compare favourably with that of efficient international ports. On three important parameters- capacity, productivity and efficiency, Indian ports lack in comparison to some of the major international ports. In international terms, labour and equipment, productivity levels are still very low due to the use of outdated equipment, poor training, low equipment handling levels by labour, uneconomic labour practices, idle time at berth, and time loss at shift change. Containerization is currently at 18% largely due to healthy EXIM (export – import) growth of 15-20% (KPMG, 2006). However, this is still very low compared to the levels of 70% in other countries, primarily due to the lack of adequate infrastructure in terms of ports, roads, and railways. Table STYLEREF 1 \s ?1. SEQ Table \* ARABIC \s 1 2 Average allocation of funds in the Indian public transport sectorRailways RoadsPorts and Shipping AviationOthers52%32%6%6%4% REF _Ref226855337 \h Table ?1.2 presents the average allocation of funds in the public transport sector during the five year plan (2002-2007). With the globalization of the Indian economy and spurt in imports and exports, the container traffic is expected to grow exponentially. It has been estimated that the growth will be of the order of 15 % (Prasad, 2005).The Government of India decided to set up Inland Container Depots (ICDs) which are also called dry ports and Container Freight Stations (CFSs). ICDs which are constructed away from the ports and provide all facilities for effecting containerized shipments; CFSs are smaller than ICDs and constructed near the ports, limited only for stuffing into and de-stuffing of cargoes from the containers (BARSYL, 2009). Indian ICDs perform many functions include stuffing, de-stuffing, locking, sealing, providing trailers chassis, railway flats, repairs, handling equipment, storage, 'facilities for reefer, customs examination and processing of customs documents, issuance of combined transport documents by carriers. ContainersContainerization has been defined by the Containerization Institute, USA as “the utilizing, grouping or consolidating of multiple units into a larger container for more efficient movement” (Agerschou et al., 1983). Containerization is an important element of the logistics revolution that changed freight handling in the 20th century. Use of containers or other large size boxes to protect the cargo as a single unit throughout the journey is not new. In 1955 a very important man came into this business. His name was Malcolm McLean. He bought shipping company called “Pan Atlantic Steamship Corporation”. Soon he found out that the loading and unloading of trucks and ships took a lot of time and many people were needed to fulfil these tasks. McLean came up to an idea that there must be a special box/unit that can contain goods from the shipper’s house to the receiving party without unloading and loading again. This must result in less damage and must avoid steeling by thieves. This concept also results in faster loading/unloading trucks and ships and large packing materials is not needed (Meersmans, 2002). Nowadays, colourful steel containers can be seen in every major port. An exclusive overview of history of containers is given by Rath (1973). Indian railways used the containers for the first time in 1966 on the Bombay-Ahmadabad route.Figure ?1.6 Growth of world maritime trade versus containers 1987 to 2004A study of containerisation has shown that the saving in the cost of freight to shippers can be as high as 50% of the cost of freight without using the container (Khanna, 2005). As shown in REF _Ref234131771 \h Figure ?1.6, the strong growth in tonnage moved by container has been increasing at a rate faster than total maritime trade over the period betwen1987 and 2006 (Drewry Shipping Consultants, 2007).Total international maritime trade volumes grew at an average of 4.1 percent per annum over the period of 1980 to 2004 with the result that by 2004 total seaborne trade was almost double to that of 1990 volume. The growth of containers grew seven times from 1980 to 2004. On the other hand, the challenge with containers lies in two areas: the mismatch between ISO (the International Organization for standardization) standards and un-standardized domestic container, and the prolific growth (highly productive) of different types of containers for cargos. Global production of container boxes in terms of annual output has increased by 76 times from 40,000 TEU in the year 1966 with a cost of 1,500 US Dollars (75000 Indian Rupees) to 3,050,000 TEU with a cost of 1,850 US Dollars (92000 Indian Rupees) per container (Raghuram, 2007).Types of containersThere are three common standard lengths, 20 feet (6.1 m), 40 feet (12.2 m) and 45 feet (13.7 m). There are wide varieties of containers that are being used in practice. Most of the containers have standard widths and heights, with standard lengths varying from 20 to 53 feet. After several years of usage, some containers might lose a few inches due to minor accidents and repairs. The dimensions of ISO and non ISO containers are presented in REF _Ref234136511 \h Table ?1.3 (Source: Kang, 2006).Container capacity of ships and ports is measured in twenty-foot equivalent units (TEU). REF _Ref226855635 \h Figure ?1.7 shows 1 TEU, and 2 TEU normal, and 2 TEU high cube containers. A twenty foot equivalent unit is a measure of containerized cargo equal to one standard 20 ft (length) × 8ft (width) × 8.5 ft (height) container. Most containers today are of the 40-ft variety and are known as 2 TEU. Two TEU are referred to as one FEU or "Forty foot equivalent unit”. These two terms of measurement are used interchangeably. "High cube" containers have a height of 9.5 ft (2.9?m), and half-height containers used for heavy loads have a height of 4.25 ft (1.3 m). The cost of a 20-feet container is approximately $2,000 to $3,000 (1-1.5 lakh Indian Rupees) and a 40-foot container can be anywhere between $3,100 and $4,500 (1.6-2.25 lakh Indian Rupees).Table STYLEREF 1 \s ?1. SEQ Table \* ARABIC \s 1 3 Dimensions f ISO and non- ISO containers40’ High Cube container40’ container20’ container Figure ?1.7 Forty feet normal, forty feet high cube, and twenty feet containersContainers are also classified on the basis of the type of cargo carried in them. As per this classification, there are four basic types of containers; dry cargos, liquid cargos, bulk commodities, and special cargoes requiring protection from the environment. According to their function containers are classified into general purpose, refrigerated, high cube, open top, flat top, and tank containers, etc. REF _Ref226855819 \h Table ?1.4 shows these types with their character and applications.Table STYLEREF 1 \s ?1. SEQ Table \* ARABIC \s 1 4 Types of containersContainer TypeCharacter Application Figures Standard 20' - Max. Payload: 28,23 Tonne(T) 40' - Max. Payload: 26,7 T 40' HC (High Cubic) - Max. Payload: 26,46 T Suitable for any general cargo. Has various lashing devices on the top and bottom longitudinal rails and corner post.Hardtop20' - Max. Payload: 27,89T40' - Max. Payload: 25,78T. 40'HC-Max.Payload: 25,58 TEquipped with a removable steel roof. Especially for heavy loads and over height cargo. Loading through roof opening and doorway by swing outdoor headerOpen Top20' - Max. Payload: 28,13 T40' - Max. Payload: 26,63 TWith removable tarpaulin. Used especially for over height cargo. Loading either from top side or door side by swing outdoor header.Flat Rack20' - Max. Payload: 31,26 T40' - Max. Payload: 26,28 T40'HC-Max.Payload: 39,30 TEspecially for heavy loads and over width cargo.Platform20' - Max. Payload: 31,26 T 40' - Max. Payload: 39,30 TEspecially for heavy loads and oversized cargo.Ventilated20' - Max. Payload: 27,99 TEspecially for cargo which needs ventilation.Refrigerated20' - Max. Payload: 27,45 T40' - Max. Payload: 29,40 T40' HC - Max. Payload: 29,88 TReefer containers do have their own electrically operated cooling / heating unit. The power supply is provided by ship's electrical plant, by terminal or by "clip-on" diesel generator.Insulated20' - Max. Payload: 21,45 T40' - Max. Payload: 26,63 TThese containers do not have their own cooling facility. The cooling / heating is supplied by an onboard plant, by terminal or by a "clip-on" reefer unit.Tank24000 Litter /Litter WaterFor the transport of liquid food, e.g.: Alcohols, Juices, Edible Oils, Food AdditivesAdvantages and disadvantagesThere are many advantages of using containers as a packaging unit, some of which are outlined below: Use of containers reduces loss, pilferage and damage claims significantly.It eliminates a great deal of paper work related to shipments.It expedites door-to-door pick-up and delivery service of cargo by reducing the time for loading and unloading operations.It eliminates multiple handling of cargo because a container is handled as a unit.The consolidation of small loads into a unit load is possible with a container, leading to economy in freight costImprovement relating to handling, marketing and pattern of packaging is made possible by the containerIt is possible to reduce the cost of packaging because of possibilities of placing goods without heavy packaging inside the container without any risk of damage in transit.A container combines all the advantages of various mode of transport by rail, road and sea.Containerization has led to improvement in the construction of boxes or containers, and quick turn-round of modes of transport – whether ship, rail, road- which leads to economy in the cost of transport.The main disadvantages of using containers are as followsContainerization increases the fuel costs of transport and reduces the capacity of the transport as the container itself must be shipped around not just the goods. For certain bulk products this makes containerization unattractive.When transporting containers through railways, containers cannot be stacked in layers due to vertical height limitations. As a result transportation through railways sometimes becomes difficultContainers occasionally fall from the ships during storms. It is estimated that over 10,000 containers are lost at sea each year. Identification systemLike any vehicle, every container has an identification system based on a unique registration number. The identification system for containers (ID) is based on a series of letters and numbers that represent the owner’s code, the serial number and the code for the country of origin. The registration number is given on all four sides of the container which makes it possible to identify its owner, and to identify the contents of the container. Other important information about the container is also provided by these numbers. All containers are, therefore, required to have these identification numbers and letters. A system also been developed to check this information, and details of the type and dimensions of containers is also expressed in figures.Figure ?1.8 Example of container ID The container ID is composed of several fields as shown in REF _Ref226855681 \h Figure ?1.8, including the following fields:1. The shipping company (e.g., “UXX”)2. The equipment category (always “U” for freight containers, "Z" or "C" for chassis)3. The serial number of the container (e.g., “423697”).4. The check digit of the first 3 fields (e.g.,”0”)5. The container type (e.g.,”SE4310”)Only the first 3 fields are relevant to the identification of the container, and represent a unique identification number for each shipping container. In the above case, this ID is “UXXU 423687”. The shipping company field ("UXX"in the example) is verified against a pre-defined list of known companies. Additionally, the second field ("U") is always verified. The check digit is used in order to verify the entire 10-character identification number. If the check digit is not identified, only the 10 characters are compared and reported. If it is recognized and tested for correctness, it will also be reported (a "0" in the above case). The container type (in the above example,”SE4310”) is not part of the ID and is not identified or transmitted.Container terminal structure and handling equipment Container terminal is a facility for loading and unloading of containers from ships or another means of transportation. In general terms, a container terminal is an area designated for the stowage (see appendix A) of cargos in container, usually accessible by truck, railroad, or marine transportation. At container terminals, containers are picked up, dropped off, maintained, and housed. Types of container terminals and typical processes are given in the next section. Processes at container terminalContainer terminal can be classified mainly into three types:Sea port container terminalRail container terminal (Dry port)Inland container terminal Containerships as shown in REF _Ref233629284 \h Figure ?1.1 REF _Ref233848890 \h Figure ?1.9 are nowadays unloaded and loaded at large sea port container terminals. This loading and unloading of container process can be divided into different sub-processes as shown in Figure ?1.10.Figure ?1.9 view of containershipFigure ?1.10 Process of loading –unloading containersWhen a ship arrives at a port, a berth is assigned for unloading. After the ship is positioned under the quay crane(s) (QCs), the containers are unloaded by the QC and are loaded to fleet of trucks and transported to yard area for storage. At the storage area containers are stacked into blocks. Equipments, like cranes or straddle carriers (SCs) serve the blocks .On the berth, a necessary number of quay cranes (QCs) are allocated to unload the containers. A straddle carrier can both transport containers and store them in the stack. It is also possible to use dedicated trucks to transport containers. If a truck arrives at the stack, it puts the load down or the stack crane takes the container off the truck and stores it in the stack.Containers are stored in blocks for certain period until they are claimed by the importer. When containers are claimed, containers are retrieved from the stack by cranes and transported by trucks to transportation modes like barges, deep sea ships, trucks or trains. To load export containers onto a ship, these processes are executed in reverse order. Figure ?1.10 illustrates a summary of the main operations in a container terminal. Every process is highly dependent on the previous one. Except for arrival and departure of external trucks all the operations are under the control of port’s personnel. A large number of highly dependent operations need continuous coordination and high degree of efficiency.A complete description of various equipment used, and the operations inside the terminal have been described by various researchers with a view to facilitate decision making within the terminal (see Silberholz et al., 1991; Kozen 1997; Nevins et al., 1998; Lee et al., 2003, Linn, et al., 2003, Steenken et al, 2004; Murty et al., 2005a; Murty et al., 2005b; Dekker et al., 2006; Petering, et al., 2006; and Petering 2007).Most of the terminals make use of manned equipments, like straddle carriers, cranes and multi-trailer-systems. However, a few terminals, like terminals in Rotterdam, are semi-automated. At such terminals Automated Guided Vehicles (AGVs) are used for the transport of containers. Furthermore, the stacking process can also be done automatically by Automated Stacking Cranes (ASCs). In practice, the number of containers to be unloaded from or loaded onto a ship is fairly large, ranging from 500 to 2500 containers (Ioannou et al., 2000).Technologies for movement of containersSince containers are large and heavy, specialized material handling equipment are required for transporting them within the terminal. A container terminal provides the location, mechanical devices, space and operating conditions under which the container transfer takes place. Container yard is a materials handling/storage facility used for completely unitized loads in containers and/or empty containers (Dirk, et al., 2004). A great variety of handling equipments are involved in container yard operation (Ioannou et al., 2000).Figure ?1.11 Different types of handling equipment and their stacking capacity General information as well as particular details of technical equipment for container handling are provided by engineering oriented journals as well as by specialized outlets, brochures, or websites of suppliers of material handling equipment and services in the container sector (e.g., PTI 2006, Kalmar 2006, Noell 2006,and ZPMC 2006) Common equipment such as the chassis-based transporter, straddle carriers (SCs), Reach Stacker (RS), Rubber-Tired Mounted gantries (RTMG) crane, Rail-Mounted Gantries (RMG) crane, are compared in terms of the actual stacking capacity in REF _Ref234072182 \h Figure ?1.11. (source:Kalmar, 2006)Over the last decade, technology and automation have been introduced into the container business to improve the efficiency, increase capacity, and meet future demands. Furthermore the explosive growth of freight volume has greatly increased the load on container terminals. Recent advances in electronics, sensors, information technologies and automation have motivated the port authorities to adopt advanced technologies to cope with the booming growth. In the next section, a brief review of some of equipment used for moving the containers within the container terminal as well as details of recent technologies and automation equipment is presented. Container handling equipmentMost of the terminals make use of the equipment, like lift truck (front end loader, side loader or reach-stacker), straddle carrier, rail mounted and rubber tyred gantry crane, etc. quay crane at quayside.Straddle Carrier Straddle carriers (SCs) are four wheeled vehicles that are able to pick and drop a container by itself at high speeds. They are available for handling different sizes of containers and with different vehicle-lifting ability. SC as shown in REF _Ref226857367 \h Figure ?1.12 is often used in medium size multi-modal facilities where speed of operation is important. They are the most common form used for manned inter-terminal transport over short distances say, between the quay side and storage yard. SCs remain popular because of their relatively low purchase cost, smaller yard development cost and their economic and flexible operations (Ioannou et al., 2000). However, SCs are less space efficient, have lower operational capacity and less suited to higher automation and have greater downtime and higher maintenance cost [for more technical information see Siemens, (2007a)].Figure ?1.12 Straddle carrier at Singapore portFork liftsFork trucks are sometimes used for container handling for small capacity up to 5 tonnes. They are generally considered unsuitable and not recommended for containers because of lack of visibility to the driver, as a result of which there is possibility of damage to containers. Forklifts cannot be used for containers that are not fitted with the pockets for fork truck. Reach StackerA reach stacker (RS) is a type of fork lift with a telescopic boom and top-lift attachment used for lifting and stacking containers. Its design enables it to reach beyond the first row to pick up a container. REF _Ref232773192 \h Figure ?1.13 shows a reach-stacker that operates in the container terminal. Its main task is to stack containers and to load them into trucks, tractors or trains. It is a road vehicle, with a high tonnage capacity. Its storage capacity is approximately equal to 500 TEU per hectare. It can stack containers up to 3 containers high and can reach a maximum height equivalent to 5 containers high. The capital cost for a RS is low as compared to other container handling equipment. RS is recommended for small to medium size operations in multi-purpose terminals.Figure ?1.13 Reach Stacker at ICD, TughlakabadMultiple trailer systemA multiple trailer system (MTS) (also called multi-trailer system) is one where a towing vehicle transports more than one container to and from the container yard. It is also known as elephant trains, and is shown in REF _Ref234136779 \h Figure ?1.14. It can move eight trailers loaded with container, which can lead substantial reduction in operation and labour cost (Ioannou et al., 2000). Development of Multi-Trailer System (MTS) has been carried out by the Technical University of Delft, Netherland. The demand for (MTS) is growing rapidly. For example in a Kalmar delivery each MTS will be able to move eight 20ft containers (or an equivalent mix of 20s and 40s) simultaneously, thus providing significant benefit over single trailer systemsFigure ?1.14 Multi-trailers at the port of RotterdamStacking cranesStacking cranes are used for placing and retrieving of containers in stack. These forms of stacking cranes are known as Rail Mounted Gantry Cranes (RMG) or Rubber Tired Gantry Crane (RTGC) [for technical information see Siemens, (2007b) and Siemens (2007c)], and Over-Head Bridge Cranes (OHBC). OHBC requires huge initial investments in erecting columns sustaining crane rail girds and ground breaking works. An RTGC moves on rubber tyres over containers and is able to move among blocks. A RMG runs on rails normally serving a single storage block between the rails. REF _Ref232008076 \h Figure ?1.15 shows RMGCs at ICD, Tughlakabad terminal The RTGC has the flexibility to change stack but in practice this is time consuming and cannot be done often. Being harder to automate, they are less attractive for the terminals trying to further increase their throughput by automization. As a result yard cranes are space-efficient, fast in operation and more suited for automation. However, they require higher development cost than SCs typically around 3 times the price, because of their heavy body weight and wheel load. RTGs are typically cheaper to install, more expensive to operate and more flexible than RMGs. Comparison of OHBC, RMGC, and RTMC is given in Appendix B.Figure ?1.15 Rail mounted gantry crane at CONCOR, Tughlakabad, New Delhi.Quay craneQuay crane (QC) is manned equipment; the maximum capacity to load and unload containers from or to the ship is 50 containers per hour (Evers et al., 1996). QC is the most important determinant of the ship operation productivity at the terminal. The number of quay crane Nqc required to accomplish the proposed task, can be calculated by Nqc=NcontainersCqcTship Eq ?1.1Whereas, Ncontainers is the number of containers to be loaded and unloaded. Cqc is the maximum physical capacity of the quay cranes, Tship is the turnaround time of the ship. REF _Ref233753772 \h Figure ?1.16 shows Quay cranes (QCs) that have trolleys that can move along the crane arm to transport the container from the ship to the transport vehicle and vice versa. A spreader, a pick up device attached to the trolley, picks the containersFigure ?1.16. Quay crane at port of Paranaque, Brazil.The QCs move on rails to the different holds to take/put containers off/on the deck and holds. Technical specifications of quay cranes can be browsed in (Ceres Paragon, (2006); Dubini (2007); Corp, (2007); ZPMC (2007a); ZPMC (2007b); and ZMPC, (2007c).) It can happen that at the same moment one QC is unloading containers while another QC is loading containers. QCs are manned because automation of this process encounters practical problems. For example exact positioning of containers may not be achieved.Recent technologies for container loading -unloading Over the last decade, technology and automation have been introduced into the container business to improve the efficiency of part operations See (Dimitrijevic et al., 2005) and (Asef-Vaziri et al., 2003). Some of these technologies include: Automated guided vehicles (AGV)see (Liu et al. 2002) and (Liu et al., 2004), Automated lifting vehicle (ALV), overhead grid rail system (OHGR), linear motor conveyance system (LMCs), and high rise automated storage and retrieval structure (AS/RS) see (Asef-Vaziri et al. 2000) and (Chen, et al., 2003).Automated guided vehiclesAutomated guided vehicle (AGV) is driven by an automatic control system that serves the role of the driver, and moves along guide-paths, which can be modified easily. AGVs are considered to be the most flexible type of material handling system (Egbelu, 1984). Their size ranges from small load carriers of a few kilograms to over 125-ton transporters AGV consists of the vehicle, onboard controller management system, communication system and navigation system. AGVs are now becoming popular in automated materials handling systems, flexible manufacturing systems and container handling applications. In this concept the terminal configuration is similar to that of conventional terminals but instead of using manually operated equipment, AGVs are used to transfer containers within the yard and automated cranes are used for loading and unloading. AGVs are very well suited to be deployed for terminal operations due to the repetitive nature of movements within the terminals. The promise of deploying AGVs in container terminals lies in their capability of achieving the following benefits: high container throughput, continuous operation for 24 hours a day, 365 days a year, high controllability and reliability, high safety standards, automated and consistent container handling operation, reduced operational costs, especially labour costs, high position and heading accuracy (Evers et al. 1996). Unlike, straddle carrier, AGVs are not able to load and unload containers themselves. A crane is always needed to perform these operations. However, the system is not cost effective because it does not permit high stacking and requires wide roads to travel through the terminal. The European Container Terminal (ECT) in Rotterdam is the most advanced container terminal in the world. It uses a fleet of AGVs (as shown in REF _Ref226858604 \h Figure ?1.17 ) between the yard-cranes and ship-cranes at the terminal. The system is considered successful but the rate of success so far has been less than what was expected. Other ports considering this technology are watchful of ECT’s success as they recognize it has been a slow process. In the recent years, there have been substantial improvements in speed of vehicle as well as in the navigation technology and communications systemsFigure ?1.17 Automated guided vehicle used at Rotterdam port. Automated lifting vehicle Automated lifting vehicle (ALV) was launched by Seoho Electric Company and the Korea Maritime Institute (KMI). The design is a hybrid between a passive AGV and a low height straddle carrier (Kim, 2006). It is a vehicle which can both load and unload containers and travel from the ship to the stack during the unloading process and from the stack to the ship during the loading process under its own power. These vehicles are capable of lifting containers from the ground by themselves and that is in fact the main difference from AGV. By using lifting vehicle the loading and unloading process at the crane and the transportation process can be decoupled. A crane places a container on the ground and does not have to wait for a vehicle to place the container on. This last action is required in case when non lifting vehicles are used. Linear motor conveyance system Another technological concept that has demonstrated significant promise for the transfer of containers to and from the yard is based upon linear motor-conveyance system (LMCS). Figure ?1.18 Linear motor conveyance systemLinear induction motor operates on the same basic principles as a conventional, rotary induction motor, except that instead of the coils being wound around a shaft, the entire assembly is “unwound” into a linear configuration. Running current through the unrolled, flattened stator moves a metal flat blank, which is placed above the stator (Ioannou et al. 2000). By controlling an array of linear motors that are placed underneath a platform, one can accurately move the platform given that it is on a sliding or rolling surface. However, the technology is scalable to larger tasks. A system such as this could be ideally suited for port and terminal operations.Prototype of LMCS as shown in REF _Ref233849317 \h Figure ?1.18 has been constructed and successfully tested in Eurokai Container Terminal in Hamburg, Germany (Patrik et al. 2001).Once the necessary infrastructure is in place and the shuttles to carry the containers are constructed, the system could be operated autonomously without any constraints on the hours of operation, and at a very low cost. Linear motor driven systems could be proven to be more attractive than AGV systems for marine terminal applications in terms of maintenance cost and reliability (Ioannou et al. 2000) However, due to the fixed guide-way associated with linear motor systems, AGV system could be much more flexible in terms of their ability to travel on numerous paths depending on the navigation concept used.Overhead grid rail technologyA concept known as Overhead Grid rail technology for optimizing the use of space and improving the productivity of container terminals (OHGR) has been proposed by Sea-Land and August Design, Inc (Design, 2005). The OHGR consists of an overhead rail, passive switches, shuttles, container buffers and a computer control system. The container handling devices (shuttles) can access any part of the container yard, eliminating the need for ground vehicles in the terminal and, as a result, the need for unproductive road areas (Dougherty, 2008). The shuttles could access the gate area to transfer containers, access a rail spur to transfer to and from trains, and the shuttles could deliver cargo directly to quay cranes in order to improve productivity. Alternatively the shuttles could be isolated to operations within the OHGR and yard vehicles can be used to transfer containers between the OHGR and the gate, ship, and train buffers (Ioannou et al. 2000). The key advantages of OHGR are that it provides high density of stacked containers,, near random access to densely stacked containers, reduction in crane “dancing”, reduction of in-hoisting time, elimination of crane waiting time, valuable combination of high density and high productivity, and ability to be modified or moved from port to port (Khoshnevis et al., 2000).Automated storage/retrieval systemAutomated Storage/Retrieval Systems (AS/RS) are a storage system that uses fixed-path storage and a retrieval machine running on one or more rails between fixed arrays of storage racks. AS/RS are used to efficiently store cargo awaiting shipment or awaiting pickup by a customer, also used to increase the packing density of cargo and containers, and for storage and retrieval with minimal human effort (Asef-Vaziri et al. 2000) and (Khoshnevis et al. 2000). Physical handling systems are used to move cargo or containers within a terminal, to or from a ship, or to or from a storage location. AS/RS can also interface directly with an AGV system, further reducing labour content. These benefits offer more efficient utilization of available space, and quicker and less labour-intensive storage and retrieval (Liu et al. 2002). AS/RS is most often used in distribution centres, which stock large number of items, instead of trans-shipment terminals (such as ports). Like AGV systems, AS/RS require significant capital investment and skilled labour for operation and maintenance. Naturally, the benefits of an AS/RS would be greatest in ports where land and labour costs are especially high or where the space is constrained.Assisting systemsBesides cranes and transport vehicles, assisting systems play an important role for the organization and optimization of work flow at container terminals. This is valid especially for communication and positioning systems. The electronic communication is based on international standards (EDIFACT; Electronic Data Interchange For Administration, Commerce and Transport). Every change of container status is communicated between the respective parties. From the point of view of the terminal operator the most important messages are: the container loading and unloading lists which specify every container to be loaded or unloaded to/from a ship with specific data; the ‘bay plan’ which contains all containers of a ship with their precise data and position within the ship (it is communicated before arrival in the port); the ‘stowage instruction’ which describes the positions where export containers have to be located in a ship and which is the base for the stowage plan of the terminal; container pre-advices for delivery by train and truck, and the schedule and loading instruction for trains only to name a few. Although only some of these messages specially the stowage instruction for ships and trains interfere directly with the operational activities of the terminal, they are very important because they help to maintain completeness and correctness of container data which is necessary to optimize the work flow. Besides the communication with external partners, the internal communication systems play a major role in optimizing the terminal operation. Participants at container terminalsThere are 6 principal participants at a terminal: 1) the shipper that loads the container and sends it to the terminal, 2) the inland carrier that transports the container to and from the terminal, 3) the terminal operator that oversees the terminal operations, 4) the stevedore who loads and unloads the containerized vessels, 5) the steamship line, and 6) the consignee or recipient of import cargo. The shipper could be the owner of the cargo, freight forwarder, or broker. The inland carrier could be a truck or rail company. The terminal operator might be a public port authority that operates a facility open to any vessel that makes arrangement to call there, or a steamship line operating the terminal as a dedicated facility, serving only its own vessels and customers. The stevedore could be the terminal operator itself or an independent contractor hired by the steamship line. The steamship line is the one who owns the vessel and is a key player in the process. It interacts with the shipper, terminal operator, consignees, and government officials. Lastly, the consignee could be a retailer who bought the cargo or a subsidiary of the shipper.Problem statementThe main functions of the terminals are delivering containers to consignees and receiving containers from shippers, loading containers onto and unloading containers from vessels, trains, trucks, and storing containers temporarily. The productivity of container terminals is often measured in terms of the time necessary to load and unload containers by cranes and trucks, which are the most important and expensive equipment used in ports. The truck scheduling problem consists of determining a sequence of unloading and loading movements for trucks assigned to cranes in order to minimize completion time as well as the crane idle times. The efficiency of a container terminal is also measured by the degree of utilization of human resources, equipment, yard area, and cost of the operations.Most terminals are now taking measures to increase their throughput and capacity by introducing new technologies, reducing equipment dwell times through increasing demurrage fees and/or limiting the advance delivery of export cargo, and increasing storage density by stacking containers four or five levels. However, there are four major problem faced by container terminal managers.How to manage the flow of containers to and from the terminal How to track the highly dynamic movement of containers in the yard areaHow to allocate resources to perform loading and loading operations in the terminal optimallyHow to schedule loading and unloading operations in an optimal mannerThis major objective of this research is to develop generic models that can be used to schedule loading and unloading operations at container terminals in an optimal manner. This objective can be achieved through optimizing the makespan for loading and unloading containers in the container terminal using greedy search algorithm and mixed integer programming. The intent behind optimizing the makespan is (1) to reduce the waiting time of the trucks, (2) to cut down the operation costs, (3) to find the optimal number of trucks to be used for loading unloading containers to /from trains and (4) to contribute towards improvement in the national economy. Specific objectives of the thesis includeTo carry out a literature review of application of optimization techniques to container terminal operationsTo carry out literature review of container handling processes in container terminalsTo collect data pertaining to container laoding-unloading in Inland Container Depot in TughlakabadTo develop and evaluate the performance mixed integer programming based mathematical modelTo develop and evaluate the performance of scheduling mechanisms based on different principles using greedy and reverse greedy algorithmsTo identify and recommend models for improving container terminal operationsThe remainder of this thesis is organized as follows. Chapter two presents the literature review of research related to this work. Chapter three presents characteristics of container terminal at ICD, Tughlakabad, New Delhi owned by Container Corporation of India (CONCOR), which is the terminal selected as a case study for this research work. Chapter four discusses the development of mathematical model of truck dispatching problem using mixed integer programming which has been developed using AMPL software.Chapter five presents heuristic model based on different scheduling mechanisms to address the problem of this research work.Chapter six presents application of models based on different scheduling algorithms to solve four real-world problems. The analysis of results obtained by using the developed models is also presented in this chapter.Lastly, chapter seven summarizes key findings from this thesis work, highlights its contribution, and discusses potential areas for future research.LITERATURE REVIEWGeneral The demand on container terminals has increased due to high growth rates on major seaborne container routes. Terminals are faced with the problem of handling an increasing number of containers in short time and at low cost. Therefore, container terminals are forced to increase handling capacities and to achieve gains in productivity. The problem of dispatching and scheduling of the trucks at the container terminal has been extensively studied by many researchers. But unfortunately; most of this research is not directly applicable to container terminals due to their unique characteristics. This, in turn, requires the development of algorithm that take into account the special characteristics and constraint associated with container terminals. Since throughput is the most important objective for a container terminal thus it is important to minimize the total throughput that is the handling time of unloading / loading of all containers from / to the ship. In the following sections, a literature review of terminal operations and logistics has been presented. The review is broadly divided into two parts. In the first part, literature related to applications of optimization techniques to container terminals is presented. The second part presents a review of container terminal processes.Optimization techniquesOptimization models are used to obtain best solution of a given problem under given circumstances. Most optimisation models are based on some type of mathematical programming technique. Some successful applications of these techniques to container terminal operation have been reported in the literature. Application of various optimization models to container terminal problems has been reviewed by Sirikijpanichkul et al. (2005); Taniguchi et al. (2001); and Russell et al (2003). Basically, these techniques fall into two categories; namely, classical and heuristic. A categorization of optimization techniques has been presented in REF _Ref232779394 \h Table ?2.1. A brief review of applications of traditional and heuristic techniques to container terminal operations has been presented in this chapter.Table STYLEREF 1 \s ?2. SEQ Table \* ARABIC \s 1 1 Categorization of optimization techniquesTechnique & ApplicationAdvantagesDisadvantagesMathematical programming:Branch and bound algorithms,Lagrangian relaxation,- Branch and cut methodsProvides exact SolutionLimited to small scale simplified problems.Require many simplifiedassumptions High computationCostGreedy algorithm,Simulated annealing search,Local beam search,Tabu search,Genetic algorithms,Expert systemNeural networkMulti-agent system, Etc.Practical for complex model formulations.Flexible regarding the nature of the objective function and constraints.Reasonable computation cost.May not sometimes achieve global optimum solutionsMathematical modelA mathematical model of a system describes system behavior using equations and logical relationships. Types of mathematical models include probabilistic models, mathematical programming models, and simulation models. In addition to the functional and logical relationships that describe system behavior, mathematical models include several other components. Decision variables are the variables that affect the performance of a given system. Examples of decision variables are the number of cranes to be installed at a container berth, or the number of parking spaces at container terminal.Parameters are values over which the decision-maker has no control. Examples of parameters are the service rate of an agent at a ticket counter, or the arrival rate of trucks to a container terminal. Identifying the decision-maker for a system is an important step in the modeling activity. If the president of a distribution company is the decision-maker, the location of a warehouse might be a decision variable. If the decision-maker is the warehouse manager, then the location of the facility is a parameter. Constraints are any limitations that may be placed on the decision variables. Examples of constraints are area limitations for dockside cranes at a container terminal, budget limitations for operating container terminal, and towing capacity limitations of the trucks used in an intermodal system. A constraint may limit a single decision variable or it may involve two or more decision variables.Performance measures are quantities that capture the level to which the system is operating. Examples of performance measures are throughput, waiting times, equipment utilization, operating costs, and inventory levels. An objective function identifies an important performance measure and the optimization goal (maximize or minimize) for the measure. For example, an objective function may maximize utilization of yard tractors, minimize operating costs of a container terminal, or maximize profit generated from a container terminal. In a mathematical model, decision variables, parameters, constraints, performance measures, and objective functions are all captured using equations and/or logical relationships.According to Liu (2002), some of techniques being commonly used by the researchers can be broadly classified as follows:Linear programming (LP)Non-linear programming (NLP)Mixed integer programming(MIP)Linear programmingLinear programming (LP) is a most widely used mathematical programming technique. LP is an optimization problem with a linear objective function, a set of linear constraints, and nonnegative restrictions imposed upon the underlying decision variable. LP has been used in the optimization of container terminal operations, and the optimization model is of the formMinimize or Maximize j=1qCTj Xj Eq ?2.1Subject to j=1qAij Xj =B(i) for all i=1,...pEq ?2.2Xj ≥ 0 for all j=1,...qEq ?2.3Where is a q dimensional vector of decision variables, C is a q dimensional vector of objective function coefficients; B is a p dimensional vector of right hand side o A is a p q matrix of constraint coefficients; and T represents the matrix transpose operation.An integer programming model is the one in which all the decision variables assume integer values. Rajotia et al. (2002) applied a mixed integer linear programming model to study the deterministic case for finding out the minimum number of vehicles for loading and unloading a given number of containers. The objective of the model is to minimize empty trips made by the vehicles by taking into account the load handling time, empty travel time, and waiting and congestion time. The result of the model is compared with the result of a simulation study. They conclude that the vehicle fleet size is underestimated using the analytical methods. Holguin et al. (1998) presented a linear programming model of an intermodal container terminal. The model estimates storage charges to maximize a “pricing” function subject to the storage capacity for containers. They classify containers according to marginal operating costs, space requirements, and price elasticity of dwell times. The objective function is evaluated according to the storage charges placed on each container classification. This price function may maximize profit, or profit subject to a breakeven constraint. The model is constrained by a function of the average stack height, dwell time, and input rate for each container classification.Kim et al. (1999a) studied dispatching of containers to AGVs in a container terminal. The authors proposed a mixed integer linear programming model (MIP) and heuristics to dispatch containers to AGVs such that the delay of the ship is minimised Kim et al. (2004) presented a study that tried to synchronize ship operations with vehicle dispatching using both MIP model and a look ahead heuristic. In a numerical investigation, their heuristics were shown to outperform conventional dispatching rules. Ambrosino et al. (2006) studied the impact of yard organization on the stowage of containers in terms of unproductive export containers movement in the port. They tackled the problem using a heuristic approach based on a 0-1 linear programming model. Alessandri et al. (2007b) proposed a linear discrete-time model and a linear cost function in order to model the flows of containers through an intermodal container terminal and to optimize problems related to the strategic planning of maritime terminals. The objective of the proposed optimal control problem is the minimization of the transfer delays of containers in the terminal. The entire terminal is decomposed into three sub-terminals for ships, for trucks and trailers, and for block trains. Handshaking queues are used for describing delays in transferring containers from one resource to another one. A receding-horizon strategy is adopted in order to seek a solution of the optimization problem. The effectiveness of the proposed control scheme is evaluated by numerical experiments using data from a Mediterranean port in the Northern part of Italy.Non-linear programmingNLP technique can be applied where some of the constraints or the objective function is nonlinear. NLP can effectively handle a non-separable objective function and non-linear constraints. A general NLP problem can be expressed in the formMinimise Eq ?2.4subject to i = 1........., pEq ?2.5wherexj≤xj≤xjj = 1,....... qEq ?2.6in which F is to be minimised subject to m constraints expressed by function g(x), n is the number of decision variables, and REF _Ref233632891 \h Eq ?2.6 is a bound constraint for the jth decision variable xj with and being the lower and upper bounds, respectively.Alessandri et al. (2007a) generalized the results of Alessandri et al.( 2007b) by proposing a nonlinear predictive control approach for the allocation of the available handling resources in a maritime intermodal terminal. A mixed integer nonlinear problem is formulated for modelling the container flows within the terminal. The solution techniques developed by them treats decisions expressed by binary variables as non-differentiable functions. However, NLP requires that both the objective function and constraints are differentiable functions. Mixed integer programmingA mixed integer programming (MIP) problem results when some of the variables in the model are real valued (can take on fractional values) and some of the variables are integer valued the model is therefore “mixed”. When the objective function and constraints are all linear in form, then it is a mixed integer linear program (MILP). In common parlance, MIP is often taken to mean MILP, though mixed- integer nonlinear programs (MINLP) also accrue, and are much harder to solve.Zhang et al. (2005) presented three mixed binary integer programming models for dispatching vehicles such as AGVs or yard trucks at the quayside. The models consider the unloading phase of a vessel in one berth without taking physical settings such as buffers for vehicles into account. Furthermore, congestion free vehicle traffic is assumed, and continuous operations of quay cranes are not guaranteed since the number of vehicles is limited. The models determine the starting times of the unloading operations as well as the order of vehicles for carrying out the jobs. The objective is the minimization of the overall waiting time of the quay crane (or container jobs) which is equivalent to minimizing the job ready time of the last job. Nguyen et al.( 2009) discussed how to dispatch ALVs by utilizing information about pickup and delivery locations and time in future delivery tasks. A mixed-integer programming model is provided for assigning optimal delivery tasks to ALVs. A procedure for converting buffer constraints into time window constraints and a heuristic algorithm for overcoming the excessive computational time required for solving the mathematical model are suggestedSimulationSimulation is a modelling technique used to approximate the behaviour of a system on a computer, representing all the characteristics of the system largely by a mathematical or algebraic description. Simulation models provide the response of the system to certain inputs, which include decision rules that allow the decision makers to test the performance of existing systems or a new system without actually building it. Optimization models aim to identify optimum decisions for system operation that maximises certain given objectives while satisfying the system constraints. On the other hand, simulation models are used to explore only a finite number of decision alternatives so that the optimum solution may not necessarily be achieved. However, many simulation models now involve a certain degree of optimisation and the difference between the optimisation and simulation models is becoming less distinct.Simulation models have been routinely applied for many years by several researchers. Legato et al. (2001) and Canonaco et al. (2007) have proposed methods for integrated berth planning via simulation. Ludwik (1990) simulated a ship-to-rail intermodal freight terminal using a knowledge base and a set of algorithms. The knowledge base consisted of the physical elements of the terminal and the terminal operations processes–specifics about the loading and unloading of equipment, the type of ships arriving to the terminal, the storage facilities, the type of cargo being handled, and the interactions among these elements. Ludwik (1990), defined the vehicle, its arrival frequency and time of first arrival, its economic cost, and its required operations. He described processes by the type of cargo transfer (storage to vehicle, vehicle to vehicle, etc), the type of cargo, a process efficiency measure, and the terminal elements required to carry out the process. A microscopic simulation model based on Automated Container Terminal (ACT) has been proposed by Ioannou et al. (2001). Data was collected from a conventional terminal and simulation was carried for the ACT system for the same operational scenario in order to compare and evaluate their performances. The performance of the model was assessed by throughput, ship turn-around time, truck turn-around time, gate utilization, container dwell time, idle rate of equipment.Liu et al. (2002) and Liu et al. (2004) investigated the impact of two commonly used terminal layouts and automation using AGVs on the terminal performance. One layout is characterized by container stacks that are placed in parallel with the berth. In the second layout, the stacks are arranged perpendicular to the berth. A multi attribute decision-making method is applied in order to evaluate the terminal performance and determine the optimal number of deployed AGVs. Three operational scenarios are considered and compared for both automated yard layouts: (1) loading, (2) unloading, and (3) combined loading and unloading operations. Simulation experiments based upon real-life yard operational data from Norfolk in the United States of America. Results of simulation showed that the performance of a non automated terminal can be substantially improved by automation using AGVs. An additional finding was that the yard layout influences the terminal performance as well as the number of AGVs. It is indicated that the combined operation can increase the terminal throughput as well as the utilization of equipment in the yard.Branch and bound algorithmsBranch and bound algorithms are methods for global optimization in non-convex problems. According to Lawler et al. (1966), a branch and bound algorithm searches the complete space of solutions for a given problem for the best solution. The basic concept underlying the branch and bound technique is to divide and conquer. Since a large problem is difficult to solve directly, it is divided into smaller sub-problems until these sub-problems can be conquered. The algorithm is applied recursively to the sub-problems. If an optimal solution is found to a sub-problem, it is a feasible solution to the complete problem, but not necessarily globally optimal. Branch and bound algorithms have been applied successfully in container terminal operations by several researchers. Peterkofsky et al. (1990) formulated the static allocation model with the objective to minimize the weighted amount of time that ships spend at the port. The branch and bound method determines the best possible ship departure schedule. Dominance of infeasible solutions, boundary points, and construction of the branch and bound tree were illustrated. Branching procedures such as node selection, pruning and termination are explained with an example according to the proposed methodology. In order to determine the feasibility, the set of constraints are analyzed one by one. The feasibility of a set of constraints that have a capacitated transportation problem structure is checked through solving a derivative maximum flow problem by labelling algorithm. Computational performance of the method is evaluated by ten problems of different sized ships.Narasimhan et al. (2002) defined the problem of minimizing the time taken to load and unload the containers from the container stack yard onto the ship as transtrainer routing problem, where transtrainer is the dedicated equipment to load and unload containers from/to trucks to/from container stacking yard blocks respectively. They investigate the theoretical aspects of the problem and prove that the problem is NP-complete. The problem is formulated as an integer program with the given load and bay plans. The overall objective was to minimize the total setup and inter-bay travelling times. A branch and bound based enumerative method was developed to obtain an exact solution to the problem. The properties of optimum solutions and related proofs of lemmas are given. The problem is decomposed into enumerating the degenerate solutions and then arranging the partial sequences in the degenerate solutions to obtain final route for transtrainer. Several lower bounds to prune the size of tree were also developed.Heuristic modelsThe other alternatives that can be used for container terminal problems are heuristic techniques. By their nature, heuristic approaches are flexible regarding the nature of the objective function and constraints. As shown in REF _Ref232779394 \h Table ?2.1, heuristics models covers several techniques including greedy algorithm, simulated annealing algorithms, tabu search, genetic algorithms, etc. Greedy algorithm (GA) has been discussed in details in chapter 3 as it has been applied for optimizing container terminal operations in this research work. Literature review of container terminal processes:As mentioned in chapter 1, container terminal operations can be divided over various processes, starting from the arrival of the ship until the departure of the container to its final destination. Container terminals can be classified into two: automated and non-automated. Figure ?2.1 View of container terminal. Automated terminals are preferred in areas where manpower is costly such as the western Europe and the United States. Non-automated terminals operate in Southeast Asia, where labour is less expensive. REF _Ref226858913 \h Figure ?2.1 represents the basic structure of the container terminals. Steenken et al. (2004), Vis et al. (2003), and Henesey (2006) provide an exhaustive overview of methods for the optimization of container terminal operation operations and logistics. Various decision problems that arise at container terminal can be categorized according to the time horizon involved as i) strategic, ii) tactical, and iii) operational (Hax et al. 1984).Strategic level includes long-lasting effect decisions on the terminal (covers one to several years) concerning terminal layout, the choice of the handling equipment, and procedures.Tactical level includes mid-term and short-term decisions (once every week, every month or once every quarter) regarding which types of equipments are used and which layout is chosen.Operational level involves short-term decisions regarding daily and real-time operations (berth allocation, quay crane scheduling, scheduling routing and loading unloading of trucks, ship stowage), landside operation (transfer operation, yard management), and human resources management.A review of general classification of various decision problems addressed for container terminal processes are given in the subsequent sectionsArrival of containersContainers arrive at the ports by different means of transportation such as ships, trucks, and trains. At the strategic level, when ship arrives at the port, it has to moor at the quay side of the port. As there are a number of available berths, a decision has to be made to specify the number of berths that should be allocated to the ship. At the operational level, berth allocation can be done with the objective of maximizing the berth utilization. Logically when ship arrives at the terminal, assigning it to the available berth can be done by first arrived first served rule. However, this strategy may not be good especially when ship's handling time depends on the assigned berth. In Berth Allocating problem, ships are allocated berths closest to the stacking area where most containers for these certain ships are located. In this way, the sum of the waiting and handling time of the ship can be minimized. This problem is equivalent to a machine scheduling problem (e.g. Lawler et al., 1993 and Brucker et al., 2001).Edmond et al. (1978) used a queuing model for decisions on investment in berth construction and cargo handling equipment, and evaluated simple queuing models for container service. The objective of berth planning by evaluation of congestion and cost as suggested by Nicolau (1967) is to arrive at an optimum port capacity while incurring minimum capital cost. Thus, many container terminal managers are keen to minimize turn-around time with the resources that are available to them. According to Imai et al. (1997), Imai et al. (2001) and Nishimura et al. (2001) several versions of BAP are possible. (i) In static BAP, it is assumed that at the beginning of the planning horizon all ships have already arrived in the port. In this case, at a specific berth where the ships are to be handled, there is no idle time between them. The problem can be formulated as two dimensional assignment problem, which can be solved as polynomial time problem see (Ahuja et al. 1993). (ii) In dynamic BAP, it is assumed that more than two ships may arrive during the planning period which makes it difficult for the problem to be solved using polynomial time anymore. Imai et al. (1997) investigated static BAP under multiple objectives. Not only the sum of the waiting and handling times of the ships are minimized, but the ship's dissatisfaction that arises from the berthing order is also investigated. The multiple objectives are handled by using the weighting method, which reduces the multiple objectives into a single one. The set of non-inferior solution is identified by varying the weights. In the dynamic BAP based on a MIP formulation. Imai et al. (2001) developed a Lagrangian relaxation which was solved using the sub-gradient method. An application of genetic algorithm to dynamic berth assignment has been presented by Nishimura et al. (2001) and Cordeau, et al. (2005) considered both static and dynamic BAP. Two tabu search heuristics are presented and tasted on realistically generated instances (up to 35 ships and 10 berths), derived by a statistical analysis of traffic and berth allocation data of the port of Gioia Tauro in Italy. The terminal plans to incorporate the heuristics in its decision support system in the near future.Loading and unloading of containers At strategic level, quay cranes are often used to load and unload containers from a ship. Thus the determination of the type of material handling equipments is the decision involved at this level. At the tactical level, the determination of the number of QCs that have to work on a ship is the decision involved here. Such a problem is known as the crane scheduling problem, which can be visualized as a project scheduling problem. In the crane scheduling model, machines (cranes) work to finish independent tasks (holds) but the objective function value varies with the completion time of full job (ships). Daganzo (1989a) provides a description of a static scheduling problem where a number of quay cranes have to serve a number of ships such that the delay costs of the ships are minimized. An MIP is given for this problem, which is only solved for small problems by direct enumeration. Furthermore, a heuristic procedure is designed which is based on following crane scheduling principles:Principle 1: a crane should not be idle if there is some work it can do.Principle 2: if cranes work on a ship, at least one of them should work on "maximum hatch" The maximum hatch of the ship corresponds to the hold that requires the most crane time to be finished.Principles 3: Assume that when the first hold of a ship is about to be assigned, h crane-hours are available before time t (the latest departure time of the ships already assigned).Daganzo (1989b) studied the effect of crane operations on ship service at port terminals. In the first step, a simple, approximate approach to calculate the maximum berth throughput during periods of congestion was proposed. The approach then examines the effect that two extreme crane operating strategies have on ship delay, when the traffic level does not exceed the maximum throughput. This is done for an idealized situation designed to highlight the impact of crane operations while admitting closed-form solutions. The average ship delay can vary considerably with the crane operating strategy. Peterkofsky et al. (1990) considered the minimization of the total delay of ships as the objective function. The problem is decomposed into two stages, namely finding the best departure schedule for the ship and finding a crane allocation scheme. A branch and bound method was used to solve the static case of crane scheduling problem.At the operational level, a decision has to be made to prepare the unloading and loading of containers. The unloading plan indicates which containers are to be unloaded and where they are on the ship. Contrary to the unloading process, loading process is hardly flexible. A loading (stowage) plan indicates for each container where it is to be placed on the ship. Containers with same destination, weight, size, content and so on, belong to the same category .Wherein making stowage plan attention has to be made to find out the sequence in which containers have to be unloaded. In general the unloading and stowage plans seek to minimize the number of unnecessary movements to be performed on the ship. According to Shields (1984), the containers, that will be stowed, have to satisfy a variety of constraints, which arise as a result of physical limitations of the ship, the containers and the sequence in which port are visited by ship. The stowage problem is solved with Monte Carlo method (see Metropolis et al. 1949). Many different possible ships loading are generated and the most different one is given such that re-handlings are avoided to a large extent, physical limitations are met and unloading and loading time is minimized. Wilson et al. (2000) presented a very realistic model, taking into account all technical restrictions in order to arrive at a commercially usable decision support system. The approach by Wilson et al. (2000) is based on decomposing the planning process into two sub-processes, namely a tactical and operational process. The first process assigns containers with the same characteristics (size, port, etc.) to blocks of storage space in the ship. The second, assigning a specific container to specific location in the blocks that determined in the first process. Branch and bound is used to assign the containers to the blocks in the ship. In the tactical planning process, packing heuristics together with Tabu Search are used. Avriel et al. (2000) discussed the container ship stowage problem, its complexity, and connection to the coloring of circle graphs. The shifting of containers on board is defined as the temporary removal from and placement back of containers onto a stack of containers. For instance, if a container placed on a vertical stack has a destination of j, while the containers stacked on it have destinations further than j, the latter containers should be shifted. Although shifting cost could be considerable for large ships, container stowage placement decisions are based on port operations efficiency and ship stability, but not enough attention has been given to minimize the number of shifts for a particular route. Avriel et al. (2000) showed that the problem is NP-complete, where a polynomial time algorithm for single column case exists. Also, they derive upper and lower bounds on the number of columns for which a plan can be found in polynomial time that will result in zero shifts. Further, they show that finding the minimum number of columns for which there is a zero shifts stowage plan is equivalent to finding the coloring number of circle graphs. Avriel et al. (1998) proposed a binary linear programming formulation to solve the problem of stowage planning such that the number of unnecessary moves is minimized. It is shown that the stowage planning problem is NP-hard. Therefore, also a heuristic is developed for solving the problem. Figure ?2.2 (a) Single cycling unloading (b) Double cycling unloading and loading.Goodchild et al. (2004) described the double cycling technique that can be used to improve the efficiency of quay cranes by eliminating some empty moves instead of using the current method, where often all relevant containers are unloaded from the ship before any are loaded (single cycling). In double cycling, containers are loaded and unloaded simultaneously (see REF _Ref233695738 \h Figure ?2.2). A solution for this problem has been presented through simple formulae to determine reductions in the number of operations and the operating time.Ambrosino et al. (2006) proposed a model for the Master Bay Plan Problem (MBPP) where the main goal is the minimization of the loading time of all containers, given that all other ship movements have fixed and known duration. The authors propose a three phase algorithm based on partitioning procedure of the ship, an assignment phase of containers to ship portions and heuristic algorithm. They also propose methods to check and validate the ship stability of the overall stowage plan. Imai et al. (2004) presented a multi-criteria optimization method to the ship stowage problem which takes into account two contrasting objectives: the ship stability and the number of container re-handles. The authors propose a multi-objective integer programming model and they implement a weighting method to come up to a single objective function. Computational experiments for instances with up to 504 containers are provided. Sciomachen et al. (2006) formulate the MBPP as a three-dimensional bin packing problem and present a heuristic solution method which is based on this relation. Objectives are to minimize the total loading time as well as to efficiently use the quay equipment. The approach is validated by using real test cases from the port of Genova (Italy). Transport of containers from quayside to stack and vice versaAt strategic level, several types of equipment could be used (e.g. truck, straddle carrier, AGV) to transport containers from quayside to stack and vice versa. One of the decisions here concerns with the type of material handling equipment, which take care of the transport of containers. According to Baker (1998) the use of straddle carriers instead of non-lifting trucks improves QC productivity. For the transport of multiple containers, multi-trailer systems can be used (see REF _Ref234131843 \h Error! Reference source not found.). This system, in this figure, uses a truck that pulls five trailers, each capable of carrying 2 TEU.After deciding which system will be used tactical decision entails determining the necessary number of material handling equipment needed to carry out day to day operations. Steenken (1992) developed an optimization system to determine the number of straddle carriers and their route. Because of the fact that the system had to be implemented into a radio data transmission system, it had to fulfil the conditions of a real-time application. The problem is solved as a linear assignment problem.Vis et al. (2001) presented a model and an algorithm to determine the necessary number of AGVs at an automated container terminal. To solve the problem a network formulation was presented.At the operational level it should be decided which vehicle transports which container and which route is chosen. The objectives are to minimize empty travel distances, delay of ships, or total travel time of the vehicles. A complete review of the routing and scheduling of vehicles in general is given by Bodin et al., 1983 and by Steenken (1992). Steenken et al. (1993) described the more specific problem of the routing of straddle carriers at the container terminal. The objective is to minimize empty-travel distances by combining unloading and loading jobs. Routing and scheduling systems are tested and integrated into a radio data transmission system of a real terminal. Steenken (1992) obtained savings of 13% in empty drives compared with the previously existing situation at the terminal, by solving the problem as a linear assignment problem. Steenken et al. (1993) solve the problem by formulating it as a network problem with minimum costs. Savings of 20–35% in empty-travel distances can be obtained within acceptable computation times.Bish et al. (2001) considered the truck dispatching problem in a container terminal. They model both the loading and unloading of the ship by a quay crane which is serviced by a fleet of identical trucks. Their model attempts to minimize the makespan to complete the entire loading and unloading operation. It was shown that the problem was NP-hard. Bish (2003) extended this study to examine the problem of determining a storage location for each discharging container, dispatching vehicles to containers, and scheduling the discharging and loading operations of quay cranes to minimize the maximum time needed to serve a given set of ships. The problem also was shown to be NP-hard and they proposed heuristic algorithms to solve it.Kim et al. (1999a) discussed dispatching containers to AGVs so as to minimize the delay of the ship and the total travel time of the AGVs. MIP formulations and a heuristic method for such a problem is given with numerical experiments. Kim et al. (1999b) investigated the single transfer crane routing problem. They focus on the minimization of total handling time of transfer crane at the container storage yard by determining the optimal number of containers to be picked up at each yard bay as well as the optimal route of the transfer crane. Their modelling approach and optimal algorithm is applied without major changes to the straddle carrier routing problems for single and multiple carrier cases as illustrated below. Kim et al. (1999c) discussed the optimal routing of single straddle carrier, which is the frequently used transhipment equipment in port container terminals. They propose a MIP model with the objective of minimizing the total travel time of the straddle carrier and investigate the properties of optimal solutions to devise a solution procedure. The solution procedure is decomposed into two stages. In the first stage, the number of containers to be picked up during a sub tour is determined. In the second stage, the visiting sequence of yard bays by the straddle carrier is found. Their solution procedure could be summarized as follows. First, with respect to a set of transportation model constraints involved in MIP model all basic feasible solutions are generated. Then the set of basic feasible solutions subject to the whole constraints is constructed by enumerating the solutions found in the first step. Next, the routing problem is solved by dynamic programming according to the solution set found in the second step and the least cost route is selected.Stacking of containersAs already mentioned in chapter 1, there are two ways of storing containers can be seen in the container terminal, storing on the ground and stacking on chassis. The stack as shown in REF _Ref226859045 \h Figure ?2.3 is an area in the terminal where import and export containers can be stored for a certain period. The stack covers the major part of the terminal and it is used for temporary storage of containers, it can be divided into blocks, each consisting of number of rows, as per terminal the stack's height varies between two to eight storey high (Cools, 2005). A transfer point at end of each lane is situated; at this point the crane unloads - loads the container off/on the truck that transports the container. Empty containers are usually stored in separate area.Figure ?2.3 Yard crane and a container blockTo stack and retrieve containers, several types of equipment could be used (e.g. gantry yard crane, reach stacker, top loader, etc). At strategic level one decision is how to choose the material handling equipment which is best suited for the stack layout. Another strategic decision which affects greatly the efficiency of stacking is the stack layout itself. The stack height and strategies for storage and retrieval of export and import containers are the factors involved in determining the stack layout. Chen, (1999) described various storage strategies. At the stack, reaching to demanded container it is necessary to move the containers that are placed on the top of it. Reshuffling and removing the containers at the idle time, leads to minimize the delay. Chen (1999) presented a systematic approach to the terminal system which provides a cornerstone for the empirical study of the terminal operations. Using the approach presented by Chen (1999) several factors such as terminal management strategy, shortage of storage capacity, poor quality of container information received, operational rules, higher container storage which influence operational efficiency and cause `unproductive container movements’ can be taken into account. Chen (1999) concluded that improvement of all surrounding conditions has to be carried out to achieve higher stacking.Chung et al. (1988) proposed the idea of using a buffer area where the number of empty chassis is available to store export containers temporarily. They developed and tested strategies that can reduce the unproductive movements of the stack crane during the loading process and as result reduce the total container loading time. They developed a simulation model to investigate the effect of buffer area on the port operation. A reduction of 4% in the loading time can be obtained by utilizing the buffer area. De Castilho et al. (1993) concluded that for a good configuration of the stack area, the amount of handling effort required to retrieve a container from the stacks depends on stack heights and on the operation strategy used. As a result, it is possible to trade off extra handling effort for higher stacking against space requirements. Moreover, the best operating strategy can be selected for the chosen configuration.Kim et al. (1999d) examined the storage space allocation problem with stack height and allocation space as the decision variables. The objective was to minimise the number of reshuffles under the condition that the space requirements are met. First, the case in which import containers arrive with a constant arrival rate is observed. The stack height and the amount of space are decision variables. It was concluded that the optimal height of the stack equals the total number of import containers during the length of the planning horizon divided by the total number of available locations in the stack. Secondly, it is assumed that the arrival rate of import containers follows a cyclic pattern with the period of one week. Thirdly, the case in which the arrival rate of containers varies in an irregular way on a rolling horizon is observed. Both problems can be solved by formulating a linear program model. The solution can be obtained by solving the dual problem and related sub-problems by applying the sub-gradient optimization technique. The problem is solved for different cases by determining firstly a formula representing the relationship between the stack height and number of re-handles and secondly by determining methodologies based on Lagrangian relaxation.Taleb-Ibrahimi et al. (1993) obtained results for long-term and operational planning. They discuss space allocation and storage strategies for export containers. Given the vessel arrival patterns and workloads they find space requirements. The minimum amount of storage space needed is determined at the strategic level. At the operational level, the problem of minimising and predicting the amount of work is discussed. Models are given that reflect the relationship between available handling effort, storage space and traffic demand.Kim et al. (2000) discussed the problem of determining storage locations for export containers with a certain weight with the objective of minimizing the expected number of re-handles for the loading of containers on the ship. These re-handles occur for example if containers are stacked on top of heavier containers, which, as assumed by Kim et al. (2000), are needed first in the ship. A dynamic programming model is formulated to solve this problem. For making real time decisions, a decision tree is given, the performance of which is evaluated by comparing its solutions to the solutions of the dynamic programming model. Maximally, 5.5% of the decisions made with the decision tree are wrong. One of the decisions that have to be made at the tactical level is the determination of the number of transfer cranes necessary to ensure an efficient storage and retrieval process.Lee et al. (2006) address a yard storage allocation problem in a transhipment hub with the objective of reducing re-shuffling and traffic congestion. They proposed a mixed integer programming model to minimize the number of cranes needed to handle the total workload. Two heuristics, a sequential method and column generation algorithm, were proposed and tested on generated instances: Other operational decisions include 1) determining which crane(s) should serve the ship trucks (seaside) and which crane(s) should serve the road trucks (landside), 2) determining where to store export containers, and 3) determining the order in which ship and road trucks are served. Ng et al. (2005) studied the problem of scheduling a yard crane to perform a given set of loading/unloading jobs with different ready times. The objective was to minimize the sum of job waiting times. A branch and bound algorithm was proposed to solve the scheduling problem optimally. Efficient and effective algorithms are proposed to find lower bounds and upper bounds. The performance of the proposed branch and bound algorithm is evaluated by a set of test problems generated based on real life data. The results show that the algorithm can find the optimal sequence for most problems of realistic size. Inter-terminal container transport Inter-terminal container transport (ITCT) means that containers have to be transported from the stack to other modes of transportation, like barges, rail and road. In future, there is likely an increased need for container transport between the various modalities (rail, road, barge, sea),, Also, the transport between these modalities and other service centres (empty depot, DistiParks) will increase. Kozan (1997a) developed an analytically based computer simulation model to describe the container process at a rail container terminal. The major factors influencing the throughput time of containers, which is a function of cranes, stackers and transfer systems, are discussed by Kozan (1997a). The simulation model is combined with heuristic rules to describe the progress of containers in the system. Firstly, a cyclic heuristic rule is used to assign handling equipment to trains. This rule selects the first available resource beginning with the successor of the last resource seized. As a result, workloads are balanced and utilisation of handling equipment and throughput are higher. Secondly, a new heuristic rule is developed to dispatch trains to tracks. When a train enters the system there may or may not be a queue for the tracks. If there are no free tracks, the train will join the queue. Otherwise, the system sends trains first to track 1 and then to track 2 or 3 if they become available for track 1 and if they minimise total throughput time. In case more than one track is used, the train with the fewest number of containers will be unloaded first. A simulation model is developed by using data from a terminal in Australia. Due to cyclic train schedules a weekly simulation period was used.Bostel et al. (1998) studied the allocation of containers on trains. Different models and solution methods are presented and tested on realistic data. It can be concluded that the number of container moves and the use and quantity of equipment can be minimized. Ballis et al. (1996) developed a simulation model that can be used in the design and evaluation of terminal facilities at the landside. Five heuristics are incorporated in the model to investigate the performance of the system. To obtain a realistic model, experiences of operations managers are included in the model. The comparison between different studies indicates that a shorter truck service time is feasible but this leads to an increase of traffic conflicts in the internal transport plete container terminalsIn previous sections, problems for individual types of material handling equipment are discussed. Within a container terminal it is obvious that in order to obtain an efficient terminal, it is also necessary to address all problems in an integrated manner. The methods and algorithms obtained by optimising the single processes can be used as a base to the optimisation of processes in the entire terminal. Gambardella et al. (1998) showed how operations research techniques can be used to generate resource allocation plans. These plans can be used by terminal managers to determine the best management strategies. Ramani (1996) develops an interactive planning model to analyse container port operations and to support its logistics planning. It is assumed that all unloading operations are completed before loading operations are started. In the simulation model of Yun et al. (1999) an object-oriented approach is used. The performance of a simple model, in which many design parameters affecting the performance are changed, is observed. A decision support system for the capacity planning of container terminals has been developed by Van Hee et al. (1988). Several mathematical models, each describing parts of the complete process, are incorporated in this system. The system can support decisions at the strategic and tactical level. Kozan (1997b) compared analytical and simulation planning models for a complete terminal. It was stated that containers arrive at the seaside in batches, namely on the ship, and not alone. Consequently, a batch-arrival multi-server queuing model is developed and compared with a simulation model. The results of this comparison indicate that, at a 95% level of significance, there exists little difference between the models. However, before implementing the analytical model, long-term data collection is necessary.Kozan (2000) examined the problem of minimisation of handling and travelling times of import and export containers from the time the ship arrives at the port until the time they are leaving the terminal and vice versa. The complete trajectory that containers go through from the ship to road or rail terminals via storage areas is included into a network model. Improvements in operational methods are not incorporated in this model. The objective of the model was to minimise total throughput time. The model is, however, subject to several constraints. Firstly, the expected number of containers moved from node i to node j in a time interval larger than or equal to the minimum amount of containers required in node j within this time interval. Secondly, space constraints at node j should be met. Further, the sum of containers moved to each section of the stack should equal the total number of containers moving into the stack. Also, the sum of containers moved into the stack should equal the sum of containers moved out of the stack. The incoming flow in each node should equal the outgoing flow of containers. Finally, the total number of containers moved should equal the number of containers unloaded from the ship and no more than the maximum number of equipment available is used. It is shown that the expected number of moves per container is the average of the maximum stack height and the minimum stack height. It is explained that this model can be used as decision tool in the context of investment appraisals of multimodal container terminals.Container Terminal OperationsOperations at Singapore portThe port of Singapore handled more than 182 million tonnes of cargo in 2007 thereby occupying first rank in the world in terms of throughput, Through continual infrastructure development and growth in world trade, Singapore has become the port with the largest container throughput in the world (Chou, 2002 and Singapore, 2009). Singapore has unique geographical position in the terms of having natural deep water harbour. No other port in the South East Asian region is close to Singapore in terms of number of ship calls and containers handled. The Port of Singapore holds the title of world’s busiest container port. The port is set to grow by 12.5% in the year 2008 bringing the total throughput of the port up to 29, 918, 20 TEUs. This growth is largely due to the influx of intra-Asia and Asia-Europe trade. Figure ?3.1 Container throughput at SingaporeSingapore’s strategic location has made it a giant in the shipping industry. 20% of the world’s transhipment trade passes through the Port of Singapore. In 2007, transhipments accounted for 5% more than the total of imports and exports of Singapore. It can be seen from REF _Ref226859707 \h Figure ?3.1that the throughput has increased from 15,571.10 TEUs in the year 2001 to 29,918.20 TEUs container in year 2008.The Port of Singapore is one of the busiest ports in the world serving more than 500 shipping routes, and connecting over 700 ports world-wide. The port typically handles 800 ships on site at any one time.Table STYLEREF 1 \s ?3. SEQ Table \* ARABIC \s 1 1Characteristics of Singapore Container Port (2007)Ports/TerminalsNumber of BerthsNumber of TerminalsGantryCranesTerminal Area (acre)Yard capacity (TEUs/day)Singapore5441188 3875,000 REF _Ref234137176 \h Table ?3.1 shows the characteristics of Singapore container port in terms of throughput, number of berths, terminals, and gantry cranes, terminal area, and yard capacity (Singapore, 2007). There are four terminals in Singapore; namely Tanjong Pagar, Keppel, Brani, and Pasir Panjang. In order to handle continuous growth, the Port of Singapore is in the process of automating the cargo handling process within its terminals, The Port has developed integrated technology systems and software to facilitate electronic transfer of trade data and vessel clearance. This has encouraged international carriers and ship-management companies to set up regional offices in Singapore. The Port of Singapore Authority (PSA) has become an international identity in container stevedoring with representation in several major ports including Italy, China and Belgium.The Port of Singapore manages the highest volume of containerized cargo than any other port in the world. Due to technological advances that are utilized within the Port of Singapore, greater volumes of cargo are able to pass through the Port of Singapore. The port of Singapore Authority has been investing over $7 billion to develop 26 berths over four phases at Pasir Panjang Terminal. When fully developed, the state-of-the-art Pasir Panjang Terminal will be able to handle 36 million TEUs a year. The terminal has the world’s first remotely operated Bridge Cranes which will speed up container handling in the yard and further maximise yard utilization by stacking containers nine storey high. Built by a consortium comprising Mitsui Engineering and Shipbuilding and Keppel Engineering, these cranes will substantially boost worker productivity, by enabling each crane operator to manage a number of cranes. The Pasir Panjang terminal can handle an average of 750,000 TEUs a year, 25% more containers than PSA’s other terminals; and one operate can operate several cranes.In order to overcome the growing shortage of skilled labor and improve productivity the Port of Singapore Authority (PSA) is considering the design of the most advanced automated terminal system. PSA plans to operate hundreds of AGVs under a sophisticated traffic management schedule for container movements. A contract for 5 prototype AGVs was awarded to Kamag of Germany and Mitsui of Japan. The vehicles were designed to be able to accelerate from 0 to 5 mph in under 10 seconds, with the top speed of 15.5 mph – loaded or unloaded. They can accept either 20- or 40-foot containers with 50 tons maximum payload and can operate independent of the weather conditions. The pilot AGV system started in the late 1994 at Brani Terminal and was completed in 1997. In May 1998, PSA signed another agreement for the phase II program to develop and test AGV systems for container terminal operations. The completion date for phase II is scheduled for 2002. It is expected that with the use of AGVs each berth will be able to handle 25% or more containers that the PSA currently handles.Operations at container terminals in IndiaIndian Railway's strategic initiative to containerize cargo transport put India on the multi-modal map for the first time in 1966. Since then, India has made good progress in container transportation facilities. Given the continental distances in India (almost 3,000 km from North to South and East to West), rail transport is seen as cost effective option for all cargo over medium and long distances, especially if the cost of inter-modal transfers could be reduced (KPMG, 2007). Containerized multi-modal door-to-door transport provided the ability to deliver variety of cargo at the doorstep at the clients. Though the first ISO marine container had been handled in India at Cochin as early as 1973, it was in 1981 that the first ISO container was moved inland by the Indian Railways to India's first Inland Container Depot (ICD) at Bangalore, also managed by the Indian Railways. Expansion of the network to 7 ICDs by 1988 saw the increase in the handling of containers, and along the way, a strong view had emerged that there was a need to set up a separate pro-active organization for promoting and managing the growth of containerization in India. Presently, containerized cargo represents about 30% by value of India’s external trade, and this proportion is likely to grow as containerization increasingly penetrates the general cargo trades and increases its share from the current 68% to levels that are comparable to international levels. With increased penetration, and growth in India’s trade, container traffic is projected to grow from 4.5 million TEUs per annum in 2005 to around 21 million TEUs by 2015 (World Bank, 2007). There is a movement of 30 percent of EXIM containers by rail, and the remaining is transported by road. Container corporation of IndiaContainer Corporation of India (CONCOR) is a public sector was set up in March, 1988 with the objective of developing multimodal logistics support for India’s international and domestic containerised cargo and trade. Its operations are directed towards efficient, economical and expeditious handling and transit of containerised goods by rail through India. Although more than 90 per cent of its inland transport service is by rail. Road and coastal shipping services are also provided according to the market demand. The company`s core business is characterized by three distinct activities that of a carrier, a terminal operator, and a warehouse operator. The company provides a single-window facility coordinating with all the different agencies and services involved in the containerized cargo trade right from customs, gateway ports, and railways, to road haulers, consolidators, forwarders, custom house agents and shipping lines. It has value-added services like linking of road or short lead rail shuttle services to long lead point-to-point train services (hub and spoke services), integrated freight terminals, coastal shipping, transportation of perishable products from source to end-user, and total logistics solutions.CONCOR terminals are equipped with the most modern, sophisticated and state of art cargo and container handling equipment like rail-mounted gantry crane (RMGC), tyred mounted gantry crane (RTGC) and loaded and empty handling reach stackers. Besides, it has over 5,200 state-of-the-art high-speed bogies, low-height container flat-wagons in service. The company has a total of 57 terminals, of which 48 are export-import container depots, and there are nine exclusive domestic container depots. The customs bonded inland container depots are dry ports in the hinterland and serve to bring all port facilities including customs clearance to the customer`s doorstep. Till 2005, CONCOR was a sole service provider for rail transportation of containers The Company has a large fleet (about 8,000) of owned and leased containers. These are not just general purpose boxes, but include various special type of containers such as tank containers, open tops, high cube 22ft. containers etc. to facilitate the carriage of all types of cargo. Over the years, CONCOR has diversified into several container logistics activities. It has recently partnered with Maersk for taking up the construction of third container terminal at the Jawaharlal Nehru Port at Nhava Sheva in Mumbai.Financials Container Corporation of India registered a 24% growth in net profits to Rs 1,692.40 million for the quarter ended March, 2007 from Rs 1,362.20 million for the quarter ended March, 2006. Net sales rose 18.74% to Rs 8,081.20 million for the quarter ended March, 2007 compared with Rs 6,805.60 million for the quarter ended March, 2006. Total income rose 18.12% to Rs 8,229.5 million in the quarter ended March, 2007, from Rs 6,967.1 million for the quarter ended March, 2006. The earnings per share (EPS) of the company stood at Rs 26.04 in the quarter ended March, 2007. Container Corporation of India Ltd Company has posted a net profit of Rs 2018.336 million for the quarter ended June 30, 2008 as compared to Rs 1870.923 million for the quarter ended June 30, 2007. Total Income has increased from Rs 8134.720 million for the quarter ended June 30, 2007 to Rs 8681.145 million for the quarter ended June 30, 2008. CONCOR recorded 16.5% rise Year on Year (YoY) in throughput to 618,534 TEU led by strong growth in domestic volumes at 38.3% YoY to 113,786 TEU. For the first time in six years, the company has recorded such high growth in domestic throughput. This is mainly due to premium service of dedicated rakes, that is, running point to point schedules. Also, an increase in the share of non-bulk cargo triggered an increase in containerization, boosting domestic volumes. On the other hand, EXIM volume grew by 12.6% to 504,748 TEU, below the expectations mainly because the company ran empty rakes due to unfavourable import export mix. This will continue due to appreciation of rupee affecting exports. CONCOR has started giving lucrative discounts for export volumes to combat higher empty rakes.Physical performance Company's operations have seen the traffic grow from a level of total 594118 TEUs in 1995-96 to 2105266 TEUs in 2006-07.where the international traffic have grown from 349141 TEUs in 1995-96 to 1715661 TEUs in 2006-07 and domestic traffic have grown from 244977 TEUs to 389605 TEUs in 2006-07. Total traffic handled by CONCOR, separately for international and domestic streams, during the last decade clearly brings out the success story of CONCOR's growth as shown in REF _Ref234131900 \h Figure ?3.2 (see Raghuram, 2007).Figure ?3.2 Total traffic handled at CONCOR terminalsCase study at ICD, Tughlakabad, New DelhiThe ICD Tughlakabad is the largest dry port in South Asia and the leading centre for importers and exporters of the Northern Region of India. This ICD began functioning at Tughlakabad, New Delhi in 1993. It is situated near Okhla Industrial Area and is spread over 44 hectares of land. It has three storied administrative block that houses Offices of Customs, CONCOR, Bank, and Shipping Lines. Four full length rail lines are available in the customs area which brings the containers by train from Gateway ports such as Mumbai, Nhava Sheva, Chennai, besides bringing the containers by road from other ports such as Haldia, Calcutta and Kandla,A part of CONCOR terminal at Tughlakabad is shown in REF _Ref233756663 \h Figure ?3.3, it can be seen that there are four rail tracks available out of which three are shown loaded with trains. Gantry cranes, shuttle trucks, and a part of the storage yard are also shown in REF _Ref233756663 \h Figure ?3.3. Details of equipments and facilities available at CONCOR are given in the next section.Figure ?3.3 ICD, Tughlakabad, New DelhiFacilities and EquipmentICD, Tughlakabad as shown in REF _Ref233756663 \h Figure ?3.3 is equipped with most modern facilities and it has the following infrastructure facilities for operations located inside the custom bonded area (CONCOR, 2007).4 full train-length rail lines can serve full loaded trains with 45 wagons ( the wagons used here is high speed bogie container flat wagons)6,000 square meters. covered warehouse space for imports which is sufficient to accommodate cargo of 160 TEUs110,000 square meters covered warehouse space for export cargo which is sufficient to accommodate a cargo of 240 TEUs1,500 square meters of especially reserved space for LCL consolidation.Open space for stacking of 5,000 loaded containersOpen space for stacking 6,000 empty containers.Six hectares parking area to accommodate 400 trailersFully computerised import and export documentationAdministrative building of 8,000 sq. mtrs. of built up area housing officers of CONCOR, customs, bank, shipping lines, CHAs, surveyors, transporters, Business Centre, puterised weighbridge facilityContainer repair facilitiesTwo rail mounted gantry cranes each of capacity of 40 tonnes service at the rail sideThree Rubber Tier diesel powered Gantry Cranes each with a capacity of 40 tonnes service at the yard sideEight loaded reach stackers (40 tonnes)Six empty reach stackers (16 tonnes).25 internal trucksWith these ultra-modern facilities, ICD, Tughlakabad has developed into the largest hub of multi-modal centre in the Indian sub-continent.? Containers meant for ICDs: Patparganj, Faridabad and Gari Harsaru are first brought at ICD, Tughlakabad by rail and then transported to their respective destinations.The traffic volume at lCD, Tughlakabad is increasing every year. With the increase in volumes, the numbers of reach stackers/cranes are also likely to be enhanced. CONCOR presently owns 3600 Containers. About 8000 containers are taken on operation lease bringing the total population to about 12000. While acquiring new containers, CONCOR is also replacing its old containers, which have either out-lived their life or are beyond repair.Figure ?3.4 Schematic of ICD, Tughlakabad.A schematic of ICD, Tughlakabad, New Delhi is shown in REF _Ref233697906 \h Figure ?3.4.Loading-unloading operations at ICD, TughlakabadContainers arrive to the terminal by train and trucks, and are stored in the storage area (yard side). The containers then leave the terminal by the same means to reach their final destinations. Various operations at ICD, Tughlakabad can be divided into three parts as follows.Rail Side operations The rail yards are characterized by the number of available tracks for unloading/loading, the distribution of load types processed and the rates of arrival for trains and outgoing loads. A rail mounted gantry cranes provides an important operation associated with loading and unloading trains. Approximately 7 to 8 trains are loaded-unloaded in a day. Numbers of trains to be handled varies from time to time (CONCOR, 2008). Each train consists of 45 Bogie containers flat wagons (Hadi, 1998). The particulars of Bogie Container flat wagon can be seen in Appendix B. Each train is described by a line that contains the transport mode, a unique identity (ID), an arrival day and time, and the numbers of containers to be loaded and unloaded. Then the attributes of all containers to be loaded and unloaded follow, that is, a unique container ID, size, destination, weight, information on the type (empty, refrigerated, dangerous content, oversized), as well as pick-up information (which mode of transport will pick it up on what day).Rail mounted gantry cranes are widely used in container loading and unloading. It is built in the form of a bridge, supported by a trestle at each end. Its fixed horizontal boom projects over trains being loaded or unloaded. Therefore RMGC works on the offside of the containers being loaded/ unloaded at the rail siding and position them in a way so as to be visible to the crane operator. For more technical information about RMGC used in CONCOR see Appendix B. To unload a train the RMGC as shown in REF _Ref233698404 \h Figure ?3.5 picks up the containers from the train and put them on shuttle trucks that move them to the storage yard in the terminal. To load trains the RMGC unload containers from shuttle trucks and put them on the train.Figure ?3.5 Rail mounted gantry craneA reach stacker is used to load unload container to/from trains. It has more flexibility to move inside the terminal. There are several reach stackers that are being used in ICD, Tughlakabad to load/unload containers, out of which four are owned by the CONCOR while the rest are owned by different agencies.Figure ?3.6 Truck used for transhipment of containersTrucks as shown in REF _Ref226867074 \h Figure ?3.6 are used for transhipment of containers. Each truck has its own identity number and performs its task according to the available container to be loaded and unloaded.Storage yard operationIn storage yard, the yard is divided into three parts. The first part is the main storage area where shuttle trucks move containers from/to the rail side. The storage area has 5 blocks, and each block contains 7 rows and 72 columns except the first and the last blocks which contain 4 rows and 72 columns, and 7 rows 70 columns respectively. TMGC serve the main storage yard area as shown in REF _Ref226867144 \h Figure ?3.7. Technical information of TMGC are given in Appendix B. Containers can be loaded unloaded reshuffled, and staked on the top each other up to 5 storey high. There are some constraints which impose a sequence to be repeated in storing containers (e.g. size, weight, port of distinction, series of distinctive characteristics such as hazard class and the kind of goods transported).Figure ?3.7 Part of storage yard in CONCOR served with TMGC.The second part consists of storage area for empty containers. It is divided into four blocks each block consist of 5 rows and 25 columns, except the first block which consists of 4 rows 6 columns. This part is serviced by reach stackers which can stack containers to 4 storey high. The third part is used for temporary storage of containers whenever necessary.To enable online availability of data pertaining to container stacking, CONCOR has installed a Management Information System (MIS) at ICD, Tughlakabad. As soon as there is any change in the stack position, it is instantly fed to the computer server by a Radio Data Terminal operated by the operational task force.Gate operation At the gate of ICD, Tughlakabad, checking of all in and out containers and trucks is done by a designated clerk. All the reservations and paperwork are checked at the “gatehouse” which is a structure at the gate where the clerk inspects and clears the entrance and exit of all containers and trucks.Summary of operations at ICD, TughlakabadThe entire operations at ICD have been further divided into micro operations. Analysis of control, operation and scheduling of container handling operations can be summarized in Table ?3.2. It can be seen that except container stock and booking position, none of the operations are scheduled or planned using the real time planning of logistics.Table STYLEREF 1 \s ?3. SEQ Table \* ARABIC \s 1 2 Summary of loading/unloading operations at ICD, TughlakabadActivitiesMethod of control/ operation/ schedulingArrival /Departure of container trainInformation submitted by communication systemArrival/ departure of container carrier (input/ exit of container)Information transmitted by communication systemUnloading activity Manually scheduledUnloading from container train by gantry cranesManually scheduled, crane operationPlacing over the shuttle truckCrane operationMovement of shuttle truck to stack positionShuttle truck operationDirection to the shuttle truck operator to transfer the container to stack positionManual indication to the shuttle truck operatorUnloading of the container from the shuttle truck to placing on the stackReach stacker operation, directed by information from MIS Any mid course instruction to the truck driverDelivered manually aloneLoading activity (nearly same as for the unloading)Nearly same as for unloadingStock inventory position of containersAvailable on MISRequirement of movement of a particular container Available on MISAvailability position of empty containerAvailable on MISCustom position of a container pertaining to export/ import Container delivery requirement of clientAvailable on MISContainer booking position for onward transportAvailable on MISSurvey and data updatingGate in / Gate Out of containers / trucks at ICD,TKDRail in / Rail out of containers at ICDITKDInternal shifting within the yardMathematical Model FormulationIntroductionThis case study for this work is the inland container terminal (ICD) at Tughlakabad in New Delhi. ICD, Tughlakabad is a dry port served by trains. The terminal consists of a rail-side area where trains arrive, get serviced, loaded, unloaded and depart from the terminal. There is a yard area, where containers are stored until they are transported to their destination. The terminal handles a number of trains, and each train is served by variety of equipments that load and unload containers onto and from trains. Similarly, there are a number of yard cranes in the yard-side that load and unload containers onto and from trucks. Most containers handled by the terminal are of standard sizes (e.g. REF _Ref234136511 \h Table ?1.3) and the containers are transported in the terminal area using a fleet of trucks of unit carrying-capacity, each truck can transport only one container at a time. With the use of MIS, the location of each container in the terminal can be tracked.Problem description Typically, there are large numbers of containers to be loaded onto or unloaded from Trains everyday in a terminal. On an average, 7-8 trains arrive to the terminal everyday to unload 500- 600 containers. The containers are then required to be loaded to transport them to their destination. Throughout the container handling operation, trucks, RTMG and YCs need to be available to ensure a continuous container flow. A truck that finds the RMGC/TMGC at its job location busy with handling containers for other trucks will join the rail-side crane queue and wait until the crane becomes available to serve it. Similarly, a RMGC/TMGC that does not find a truck assigned with a job parking under it will be idle until a truck arrives with a service request.In order to reduce terminal turnaround times, it is of utmost importance to ensure an efficient and effective transportation of containers between the rail-side and the yard-side using a fleet of trucks. A gain in terminal productivity cannot be necessarily achieved by increasing the number or the speed of trucks operating in the terminal. This is because the possibility of congestions in the terminal increases with the number of trucks operating at higher speeds. At the same time, if less number of trucks are used then it would results in idle cranes. Therefore, an efficient and effective scheduling mechanism is needed to schedule containers on trucks using some principles to minimize unnecessary truck waiting times and cutting down capital investment and operating costs. This can be efficiently achieved by minimizing the makespan. Similar scheduling problems in container terminals have been analyzed by various researchers (for example, Bish et al. 2001; Li et al. 2004; and Nishimura et al. 2005). These researchers focused on a class of truck dispatching rules called the vessel-based truck dispatching policy in which a fleet of trucks is usually assigned to a specific vessel until their work is completed.One major issue in terminal planning is how to determine the sequence of containers to be handled on a fleet of trucks. This sequencing decision affects the operation efficiency of both the rail-side and the yard-side to a large extent .Unnecessary truck waiting time would lead to a longer terminal turnaround time. .A few hours before arrival of an incoming trains the terminal receives detailed information about their contents; i.e., containers that are to be unloaded into the yard, as well as the list of containers currently in the yard that should be uploaded onto the trains. This information allows the terminal dispatchers to generate so-called container sequence.It is no surprise that managing, controlling and operating such system is a very complex phenomenon. At the operational level the question is how trucks con be routed in this complex system, in which mechanism should trucks be dispatched to containers, and what is an effective traffic control mechanism? Similarly, at the strategic level, the issues include optimizing the number of cranes, trucks etc. The truck dispatching problem can be considered similar to the job scheduling problem on parallel machines. In a truck dispatching problem, the crane operations represent the setups, crane represents the operator, each container corresponds to job and trucks correspond to machines. However, the job scheduling problem for container terminals has not been studied in the literature. Therefore, this study aims to develop models for effective and efficient loading and unloading operations for ICD, Tughlakabad in New Delhi.Truck dispatching model formulationThis section describes the formulation of mathematical model for the truck dispatching problem by considering one or more number of trains serviced with a single crane. Let R number of trains to be serviced with a K number of trucks using a single crane. The number of trains to be considered in the model depends upon the availability of trains in the terminal. The container loading and loading problem with a single crane can be formally described as follows: we would like to minimize the time required to execute a given set of unloading containers in a predetermined sequence, followed by a given set of loading containers 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 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, the decision problem is to assign the loading and unloading jobs to trucks so as to minimize the makespan of the schedule. The formulation of truck dispatching problem as a mixed-integer program is presented below.ParametersN number of jobsM number of trucks available (N>M)Si Processing time, where i=1,2,...,N.di half travel time where i=1,2,...,N.tia arrival time(completion time of job i) where i=1,2...,N.tid departure time of job i, where i=1,2...,N.K large positive numberDecisions Variables Xijm is a binary variable number whose value is 1 if truck m (m=1,2,....,M) handles job j after job i (i=1,2,...,N), otherwise it is zero.Yim is a binary variable whose value is 1 if truck m (m=1,2,...,M) handles job i (i=1,2,...,N) otherwise it is zeroT is the makespan for N Jobs.Denoting the set of Xijmby X, the set of Yim by Y, and the set tiaof by t, the truck dispatching can be stated as followsMinimize TSubject totia≤T i=1, 2...,N Eq ?4.1m=1MYim=1i=1, 2 ...,NEq ?4.2i=1and i≠jNXijm≤Yim i=1,2,…,N Eq ?4.3i=1and i≠jNXijm≤Yjm j=1,2,…,N Eq ?4.4Xijm+Xjim≥Yim+Yjm-1≤1 i, j=1,2,…,N and i≠ j , m=1,2,...,MEq ?4.5tia≤K1-Xijm+tja i, j=1,2,...,N ; i≠j ; m=1,2,...,MEq ?4.6ti d+2di=tia , i=1, 2 ...,NEq ?4.7tid=a=1jSa j=1, 2 ...,MEq ?4.8tid=mina=i-Mtaa+mina=i-Mtaa-maxa=i-Mtad+Si i=M+1…,N Eq ?4.9Xijm∈0,1i=1,2,...,N; j=1,2,...N+1; m=1,2,...,MEq ?4.10tiaand T≥0 i=1,2,...,NEq ?4.11The objective in the truck dispatching problem is to minimize the makespan of the N jobs. Constraint (4.1) states the relationship between the arrival times and the makespan. Constraints (4.2) ensure that each job is handled by only one truck. Constraints (4.3) to (4-5) give the relationship between X and Y for jobs handled by the same truck. Constraint (4.3) ensure that Yim must be equal to 1 if truck m handles a job after job i. Constraints (4.4) ensure that Yjm must be equal to 1 if truck m handles a job before job i. Constraint (4.5) ensure that if Yim+Yjm equals 2, truck m handles either job i before job j or job j before job i. Constraint (4.6) gives the relationship between the completion time of a job and that of its successor job i completes before job j. Constraint (4.7) states the relationship between a job’s completion time, travel time, and departure time of job i. Constraints (4.8) give the initial scheduling of M number of jobs to M Number of trucks . Constraints (4.9) describes the second assignments of i-m jobs to M number of trucks .constraints (4.10) and (4.11) are simple constraint to ensure that X, Y, and t are non-negative. In typical container terminals such as ICD, Tughlakabad, trucks travel at the speed of 15 km/h in the terminal area. The layout of the terminal is shown in REF _Ref233670476 \h Figure ?4.1. The respective times taken by a RMGC and TMGC to handle a container are 1.5 minutes and 5 minutes. All the locations of containers are uniquely identified by the (x, y) coordinates with respect to a defined origin. The initial location of each truck is next to RMGC so that it is ready to be loaded with containers for transhipment to its predefined location in the storage yard area. The travel time of each container is the distance covered divided by the speed of the truck. The duration of a loading or unloading time of a container is equal to the sum of the travel time and the total crane handling time plus waiting time, if any. A terminal operations control system is typically used to determine the container ready time and truck ready time.Solution of truck dispatching problemA real-world problem of dispatching 2 trucks to transport 5 containers is solved with the objective to minimize the makespan of the operation. The values of input data 2di,si of the problem are given in Table ?4.1. The problem is formulated and solved using the AMPL software (AMPL, 2009) for the input data given in REF _Ref233093590 \h Table ?4.1. Using the mixed integer programming model, the makespan for the problem was found to be 23 minutes. Table ?4.2 gives the truck schedule of problem, including the container departure time tid and the completion time of each container on each truck.Table STYLEREF 1 \s ?4. SEQ Table \* ARABIC \s 1 1 Input data for truck dispatching problemContainer Number iTravel time, 2di (minutes)Processing Time, s (minutes)13225 232.5244252 2Table STYLEREF 1 \s ?4. SEQ Table \* ARABIC \s 1 2 Output from MIP modelContainer NumberDeparture time tid MinutesCompletion time of the jobs (makespan) tia minutesTruck number128124142310151416232517211Figure ?4.1Layout of ICD, TughlakabadSeveral computational experiments were conducted for various combinations of number of trucks and containers. For each combination, the solutions were obtained using AMPL on a personal computer with 2.10 GHz CPU. It was found from the computational results that even for these problems, the average computational time required to find the optimal schedule is about few minutes while for large problem the computational time required is over 3 hours, Table ?4.3 shows the computational time for different combinations of number of trucks and number of containers.Table STYLEREF 1 \s ?4. SEQ Table \* ARABIC \s 1 3 Computational time requirements for combinations of number of trucks and containersNO.Number of TrucksNumber of containersComputational time12516 Minutes23923 minutes341531 Minutes451842 MinutesThe results of the computational analysis carried out in this chapter clearly indicate that AMPL is capable of finding optimal schedule for large container unloading and loading problem. However, the computational time required for solving large problems is quite high. In view of large computational time, application to AMPL to solving real-life terminal operation problems is not practical. Therefore, a heuristic algorithm is proposed in the following chapter to solve the truck dispatching problem.Solution MechanismsIntroductionThis chapter describes mechanisms for scheduling a number of containers on a number of trucks. In such mechanisms, trucks are the players of the mechanism. According to Noam Nisan (2007), mechanism is a special class of algorithm. According to Heydenreich et al. (2008), a scheduling mechanism is a scheduling algorithm on an operating system. A flowchart of the solution mechanism is shown in REF _Ref233761128 \h Figure ?5.1Figure ?5.1 Flow chart of scheduling mechanism From the flowchart shown in REF _Ref233761128 \h Figure ?5.1, the mechanism can be done by applying scheduling algorithm on operating system through number of principles. to get the makespan, then finding out the minimum makespan followed by finding number of trucks , operation cost, and waiting time corresponding to the minimum makespan The problem of obtaining scheduling mechanism through different algorithms to get an optimal solution is not new. Many researchers including Gillett et al. (1974), Aarup et al. (1994), and Zeng et al. (2009 ) have studied the similar problem. Greedy algorithmOne of the first applications of greedy algorithm (GA) to computational optimization problem was reported by Edmonds (1971). Greedy algorithms are simple and straightforward. They are short-sighted in their approach in the sense that they take decisions on the basis of information at hand without worrying about the effect these decisions may have in the future. They are easy to invent, easy to implement and most of the time quite efficient. Greedy algorithms are used to solve optimization problems (for example Kleinberg et al. 2005, and Khuller et al. 2007). GA has been applied to wide variety of disciplines ranging from stock portfolio management to choosing a University. GA is easy to code, easy to debug, executes quickly, and is robust. GA has been applied to a wide variety of problems from several fields of science, technology, and management.Elements of a GAAn optimization problem involves finding a subset, ∈ from a collection of candidates?; the subset, ∈, must satisfy some specified criteria, i.e. be a solution and be such that the objective function is optimised by ∈. `Optimised' may mean maximized or minimized, depending on the precise problem being solved. Greedy methods are distinguished by the fact that the selection function assigns a numerical value to each candidate. All GA’s have exactly the same general form. A GA for a particular problem is specified by describing the predicates `solution' and `feasible'; and the selection function `select'. Consequently, GAs are often very easy to design for optimization problems.The General Form of a Greedy Algorithm is function select ( ?: candidate_set) return candidate;function solution (∈ : candidate_set) return boolean;function feasible (∈ : candidate_set) return boolean;***************************************************function greedy (C : candidate_set) return candidate_set is? : candidate;∈ : candidate_set;begin∈ := {};while (not solution(∈)) and ? /= {} loop ?:= select(?);? := ? - {? };if feasible(∈union {? } ) then∈:= ∈union { ?};end if;end loop;if solution(∈) thenreturn∈;else return e∈;end if;end greedy;One useful concept for proving the correctness of greedy algorithms is the definition of a promising set ,that is a feasible set is promising if it can be extended to produce not merely a solution but an optimal solution to the problem . It follows that:Lemma. If ∈ is promising at every step of the Greedy procedure and the procedure returns a solution, then the solution is optimalThe working principle of a GA can be understood with the help of an example. Consider that it is required to count a certain of money using the fewest possible number of bills. Assume that the following bills are available: Rs. 50, Rs. 20, Rs. 10, Rs. 5 coin, Rs. 1 coin, and 50 paisa coin. The set ? of candidates is the collection of coins (1; 2; 5; 10; 20; 50), The feasibility function is that the next coin must not bring the total to more than what is required. The selection function is the value of the coin. The solution function is whether the selected coins reach the desired target. A GA would start the solution process by picking up the largest possible bill or coin that does not overshoot. Suppose, the problem is to count Rs. 79.50. The choices would be:a Rs. 50 billa Rs. 20 bill, to make Rs. 70a Rs. 5 coin, to make Rs. 75two Rs. 2 coins, to make Rs. 79a 50pais coin, to make Rs. 79.50It is noted that that GA is able to achieve the optimal solution for this problem. However, GA may not be able to achieve an optimal solution for every monetary system. For example, consider a problem where a vending machine needs to return 41 cents to a customer using the available coins of 25-cent, 10-cent, and 1-cent. The GA would start he solution procedure in the following manner.Pick up a 25-cent coin, to make 25-centPick up a 10-cent coin, to make 35-centPick up six 1-cent coins, to make 41-centIt can be seen that although the GA was able to achieve the solution but it is not an optimal one. The total number of coins as determined by GA is 7 while it is a possible to achieve a better solution that requires only 5 coins. The optimal solution, can, therefore, be achieved using four 10-cent coins and one 1-cent coin.Types of GAGreedy algorithms are equally applicable to simple problems such as the money change problems as discussed above to large complex problems that are difficult to solve using classical techniques. GA can be effectively used as a selection algorithm to prioritize options within a search, or branch and bound algorithm. GA is sometimes characterized as being 'short sighted', and as 'non-recoverable'. However, if a greedy algorithm can be proven to yield the global optimum for a given problem class, it typically becomes the method of choice because it executes faster than other optimization methods like dynamic programming. Examples of such GA’s are Kruskal's algorithm and Prim's algorithm for finding minimum spanning trees, Dijkstra's algorithm for finding single-source shortest paths, and the algorithm for finding optimum Huffman trees (Thomas, 2001)There exist several versions of greedy algorithm. The four most commonly used are:Pure Greedy AlgorithmOrthogonal greedy algorithm Relaxed greedy algorithmsstepwise projection algorithmsGreedy algorithm and scheduling problemsScheduling problem of set of job on one machineSuppose we have n jobs and every job i has start and finish time (si, fi). The goal is to schedule the maximum number of non overlapping jobs on a single machine. GA can be applied to this problem by scheduling jobs successively ensuring that no assigned jobs overlap with previously scheduled jobs. The decision problem is to determine the order in which the jobs should be processed so that the scheduling mechanism is optimal. There are several ways to solve this problem. Suppose for example, jobs can be picked in increasing order of size. It is easy to see that this does not necessarily lead to the optimal solution. Likewise, scheduling jobs in order of their arrivals (start times), or in increasing order of the number of conflicts that they have, also does not work. Thus the possible greedy algorithms strategies are as below:Earliest start time: ascending order of sj.Earliest finish time: ascending order of fj.Shortest interval: ascending order of (fj – sj).Fewest conflicts: For each job j, count the number of conflicting jobs cj. Schedule in ascending order of cj.Solution using GAGreedy 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…….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 assumptionsAssumptionsThroughout 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 REF _Ref233670476 \h Figure ?4.1). The GA is applied to unloading operations using the FAT principle.GA for unloading container operationOut 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.NotationConsider 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,…,n, as the arrival time of Ji and denote it as tia(λ) and it is known as the completion time of all the jobs. Similarly, we refer to tid(λ) as the departure time for each unloading jobJiU, 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 tia and tid. As mentioned above, job precedence constraints for J_ :{ J1, J2,..., Jn} job sequence are applied in two stagesfor i=1,2,…,m tia≥ti-1a+si i=2,…,mEq ?5.1tia≥tid+2di+si i=1,2,...,mEq ?5.2for i= n-m, …, ntia≥tid+2di+sii= n-m,...,nEq ?5.3The 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.w=mina=i-Mtima-maxa=i-Mtimd Eq ?5.4To calculate tia and tid we use the following equationstijd=Cur mini=mtima+sim +wEq STYLEREF 1 \s ?5. SEQ Eq \* ARABIC \s 1 5tija=tijd+2×dij Eq ?5.6 The cost C of each job from its starting time to completion time is given in the following equation?=4×tija-tijd+0.5×wij+sij Eq ?5.7Costs 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 SEQ Theorem \* ARABIC 1 For any unloading job sequence, the greedy algorithm is optimal. that is, the greedy algorithm minimizes the makespan.ProofSuppose 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 1≤ i ≤n 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 T2+s. Thus, in schedule γ, truck Mj is idle from time T1 to T2+s. Now consider schedule λ?obtained from schedule λ by assigning job i to the first available truck, that is, to truck Mj at timeT1. In schedule λ*the successors of job i can be taken by trucks after time T1+s, where T1+s ≤T2+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 JU:{J1, J2 ,J3, J4,J5}With half travel time d1=2 minutes,d2=5 minutes, d3=2.5 minutes, d4=4 minutes, d5=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 = wt11d=s1=2 t11a=t11d+ 2d11 = 2+ 2 ×2=6t22d=s2+ w=2+2=4 t22a=t22d+ 2d2 =4+2×5=14By comparing t11a and t22a we find truck 1 return back earlier to the rail-side area so next container will assign to it, where is t31d=t11a+s13+ w=6+2+0=8 t31a=t31d+ 2d3 =8+2×2.5= 13Now by comparing t22a and t31a we find t31a=13 and t22a =14, then truck 2 reach to the rail-side earlier, so next container will assign to truck 1, w=0t41d=t31a+s41+ w=13+2+0=15 t42a=t42d+ 2d34 =15+2×4= 23By the same way we find T1 reached to the rail side before T2 so the next container will assign to it t52d=t22a+s52+ w=14+2+1=17 t52a=t52d+ 2d52 =17+2×2=21The 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 REF _Ref230371296 \h Figure ?5.2 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????J1J3J5Waiting time 2 41308100189865 141517 21Truck2????J2J4Figure ?5.2 The greedy algorithm for an unloading job sequence using FAT principleThe 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 REF _Ref234117901 \h Table ?5.1.Table STYLEREF 1 \s ?5. SEQ Table \* ARABIC \s 1 1 Performance Comparison of GA and MIP MIPGAMakespan (minutes)23 23 Computational time(minutes)16 0.5 Greedy algorithm for loading container operationThe 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}tia≥ti-1a+si i=2,…,nEq ?5.8the 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 REF _Ref230376853 \h Figure ?5.3. 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)685165187960 waiting time 0 4 6 111250292020447014 18 2224Truck1??????J1J3J5 0 10 12 2022Truck2????J2J4Figure STYLEREF 1 \s ?5. SEQ Figure \* ARABIC \s 1 3 GA for an loading job sequence using FAT principleReverse greedy algorithm for loading container operationGiving 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… 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 SEQ Theorem \* ARABIC 2 The reverse greedy algorithm is optimal for any loading job instanceProofTo prove Theorem 2 the following lemma is needed.Lemma Consider the dispatching policy λL applied to loading job sequence JL with a makespan of H (λL). There exists policy λUL applied to the reverse job sequence JR.UL associated with JL that achieve the same makespan, i.e., H (λL) =H(λUL) Proof Consider loading job sequence JL=J1,J2,…,Jn, and the dispatching policy λLLet Ml: J1,J2,…,Jlfl, denote the job sequence assigned to vehicle l, l=1, 2,..., m, under this dispatching policy. The precedence constraints for this JL job sequence imply that job i=2, …,n, can not be completed until all its successors in JL i.e., J1,J2, …,Ji-1 are completed. Hence the following equation is given CTiλL≥ CTi-1λL+s i=2,…,n Eq ?5.9Clearly the makespan for this dispatching policy is H (λL)=. CTnλL.Now considers the corresponding reverse unloading jobs sequence, JRU: {Jn2, Jn2 -1…, J2, J1}.the objective is to find a dispatching policy λL for the reverse job sequence with a makespan H (λL) such that H (λL) = H (λUL).For this purpose consider the dispatching policy λL obtained as follows.Reverse the job sequence Ml, l=1,2, …, k , define as above, and denote the resulting sequence as Ml R: Jlfl,Jfl-1,…, Jl1. Under this policy, truck l starts with job Jlfl, continues with job Jlfl-1, and so on. Start job Jn, an unloading job now , at time H (λL)- CTiλL=0, job Jn-1 at H (λL)- CTn-1λL,..., and job J1 at H (λL)- CT1λL.The question here it can be able to show the schedule obtained by dispatching policy λL satisfies (a) the precedence constraints for the JUR job sequence, and (b) truck capacity constraints, when we have dispatching for which H (λUL) = H (λL)- CT1λL+ 2d1+s= H (λL)Consider jobs Ji-1 and Ji, i=2,…,n. under dispatching policy λL then it has STi-1λUL-STiλUL=H λL-CTi-1λL- H (λL) +CTiλL=CTiλL-CTi-1λL≥ s from REF _Ref233793942 \h Eq ?5.9And hence the precedence constraints job JURjob sequences are satisfied.next it has to show that the schedule obtained by dispatching policy λUL is also satisfy the truck capacity constraints. Truck l, l=1,2, …, k, can serve jobs Jlfl,Jfl-1,…, Jl1.under dispatching policy λUL, since for jobs Jlh-1 and Jlh, h=2,…,fl .STlh-1λUL-STlhλUL=H λL-CTlh-1λL- H (λL) +CTlhλL=CTlhλL-CThl-1λL≥2dlh +sHence, dispatching policy λULgenerates a feasible schedule for the JUR job sequence with a makespan of H λL. .This complete the proof of lemma which lead to the following corollary:Corollary2: Consider the dispatching policy λUL applied to unloading job sequence, with a makespan of H (λUL). There exists a dispatching policy λL for the reverse loading job sequence wth unloading job such that it achieves exactly the makespan, i.e., H (λL) = H (λUL).Now it is ready to prove Theorem 2Proof of Theorem 2 Let λL be the optimal dispatching policy for an unloading job sequence, with a makespan of H (λL*). By Lemma 2 it can be found a dispatching policy λUL for the corresponding reverse unloading job sequence JUR such that H (λUL).= H (λL*).Now considering the optimal dispatching policy λUL*.for this JUR job sequence with a makespan of H (λUL*) by corollary2 the dispatching policy λL for the corresponding reverse loading job sequence JL which is the original JL job sequence such that H (λUL*).= H (λL), by optimality of H (λUL*) for the JUR job sequence , it has :H (λL*). = H (λL)≥ H (λUL*). = H (λL),Eq ?5.10On the other hand, the optimality of H (λL*). For loading jobs sequence implies that H (λL*).≤ H (λL) and hence REF _Ref233800122 \h Eq ?5.10 hold as equality. That is H (λL*).≤ H (λUL*)H (λL*).≤ H (λUL*)Eq ?5.11Finally REF _Ref233713092 \h Theorem 2 tell us that greedy algorithm is an optimal dispatching policy for JUR job sequence .thus, given a loading job sequence, it can obtain the reverse job sequence JUR associated with loading job and find the optimal schedule for this JUR 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 (λUL*).≤ H (λL*) by REF _Ref233801048 \h Eq ?5.11. 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 JUR :{J5,J4,J3,J2,J1)={2, 4, 2.5, 5, 2}Apply greedy algorithm on this sequence we get t51d=s5=2 t51a=t51d+ 2d5 = 2+ 2 ×2=6t42d=s4+ w=2+2=4 t42a=t42d+ 2d4 =4+2×4=12By comparing t51a and t42a we find truck 1 return back earlier to the rail-side area so next container will assign to it, where is t31d=t51a+s31+ w=6+2+0=8 t31a=t31d+ 2d3 =8+2×2.5= 13Now by comparing t42a and t31a we find t31a=13 and t42a =12, then truck 2 reach to the rail-side earlier, so next container will be assigned to truck 2, w=0t22d=t42a+s2+ w=12+2+0=14 t22a=t22d+ 2d2 =14+2×5= 24By 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.t11d=t31a+s1+ w=13+2+1=16 t11a=t11d+ 2d1 =16+2×2=20Reversing the order again yields an optimal makespan of 22 minutes. REF _Ref230383846 \h Figure ?5.4 illustrates the mechanism of reverse greedy algorithm as applied to a J+ job sequence for the problem described above. It can be seen from REF _Ref230383846 \h Figure ?5.4 that application of reverse greedy algorithm resulted in an optimal makespan of 22 minutes for the loading problem described above. The schedule in REF _Ref230383846 \h Figure ?5.4 (a) is obtained by applying the greedy algorithm to the reserved job sequence in the first step of algorithm. The schedule in REF _Ref230383846 \h Figure ?5.4 (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 On2 (see Appendix D).?Crane processing time (minutes)?Truck Travel Time (minutes)(a)waiting time 0 2 6 862484010795488315226695 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.4. Reverse greedy algorithm for loading containers using LBT principleSolution using shortest job time first scheduling algorithmSTF 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.si+2di≤si+1+ 2di+1≤…≤sn+2dnEq ?5.12The 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.2.Table STYLEREF 1 \s ?5. SEQ Table \* ARABIC \s 1 2 Schedule obtained using STF algorithmJob 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.2 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 REF _Ref233764119 \h Figure ?5.5.?Crane processing time (minutes)?Truck Travel Time (minutes) 0 2 6 8 13 15 25Truck1??????J1J3J2 2 4 8 10 18Truck2????J5J4Figure ?5.5 STF scheduling algorithm for unloading containersSTF 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 REF _Ref233764119 \h Figure ?5.5. Solution using largest job time first scheduling algorithmLTF 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.LTF works as follows the jobs with total handling time are handled first and completed. The algorithm requires the data pertaining to the number of jobs, the job names, the processing time and the travel time as the input. The second step is sorting out the largest sum of processing time and travel time among the jobs. In the third step, jobs are rescheduled and assigned to the trucks according to the sequence generated through the second step.si+2di≥si+1+ 2di+1≥…≥sn+2dn Eq ?5.13In the end, the makespan is computed by using equations (5-4), (5-5), (5-6) used in FAT.Table STYLEREF 1 \s ?5. SEQ Table \* ARABIC \s 1 3 Schedule obtained using LTF algorithmJob NumberHandling time (minutes)Handling time (minutes),in increasing orderJob number according to the new scheduling12+4=612222+10=1210432+5=77342+8=106552+2=461The results of application of LTF algorithm to the 2 truck- 5 jobs problem is presented in REF _Ref230546344 \h Table ?5.3. The job sequence as determined by STF is {J2, J4, J3 ,J5 ,J1}. LTF algorithm suggests the following schedules for each truck: T1:{J1, J3,J2} and T2:{J5, J4 }, which results in a makespan of 25 minutes of completion time . This schedule is given in Gantt chart shown in REF _Ref230462443 \h Figure ?5.6.?Crane processing time (minutes)?Truck Travel Time (minutes) 0 2 12 14 1921 25Truck1??????J2J3J1 Waiting time-61595197485 2 410287022225012 14 1620Truck2??????J4J5Figure ?5.6 The LTF scheduling algorithm for unloading containersModel Application to Real World Case StudiesThis chapter describes the application of models described in the previous chapter to optimize loading and unloading operations in ICD, Tughlakabad. Four real world case studies based on the data collected from CONCOR for ICD, Tughlakabad are solved using different mechanisms. The mechanisms considered are greedy algorithm, reverse greedy algorithm, shortest time first algorithm, and longest time first algorithm solved on personal computer. Performance of each of the models is evaluated through application to the four real-world case studies as shown in REF _Ref230466174 \h Table ?6.1. The model for the greedy algorithms, reverse greedy algorithm and shortest time first and longest time first have been coded using Microsoft Visual C++.Table STYLEREF 1 \s ?6. SEQ Table \* ARABIC \s 1 1 Four different real world case studiesCase study TrainsTrucksJobs11970221214533152104418270Four different combinations of number of containers, number of trucks and number of trains considered in the computational experiments for each loading and unloading operation are listed in REF _Ref230466174 \h Table ?6.1. For the problems considered here, the number of containers (N) to be handled ranges from 70 to 270 and the number of trucks (M) employed ranges from 9 to 18 and number of trains (R) ranges from 1 to 4. The performance of all the four models for each of the problems has been evaluated on the basis of the objective function values achieved and the execution time required. Model runs have been conducted on a personal computer with 2.10 GHz CPU and 2GB RAM. Case study 1This section describes the results of application of greedy algorithm model based on FAT principle, reverse greedy algorithm model based on LBT principle, greedy algorithm model based on STF principle, and greedy algorithm model based on LTF principle. In a typical container terminal, trucks travel at the speed of 15 km/h in the terminal area. The time taken by a RMGC to handle a container is typically between 1.5 minutes and 5 minutes. The initial location of each truck and the location of each job’s pick-up/drop-off are randomly generated based on a terminal area of 1500 metres by 1500 metres. The travel time is the time that truck takes to travel from rail-side and return back to the same point. The duration of a job is equal to the sum of the total travel time from its pick-up location to its drop-off location and the total crane handling time. A terminal operations control system is typically used to determine the job ready time and truck ready time. The processing time (s) and travel time (2d) for each job for case study 1 is given in REF _Ref233263727 \h Table ?6.2. Table STYLEREF 1 \s ?6. SEQ Table \* ARABIC \s 1 2 Input data for case study 1Job.s (min)2d(min)Jobs (min)2d(min)JobS(min)2d(min)13.007.00 243.009.00 474.005.00 24.009.00 251.007.00 482.003.00 34.003.00 261.005.00 492.005.00 43.004.00 273.004.00 502.007.00 52.005.00 282.00 5.00 512.004.00 63.007.00 293.007.00 522.003.00 72.009.00 303.0012.00 532.0012.00 83.005.00 313.003.00 542.005.00 93.004.00 323.005.00 552.007.00 102.005.00 335.007.00 564.003.00 113.008.00 343.004.00 574.009.00 124.005.00 353.009.00 582.005.00 134.007.00 36 2.007.00 594.0012.00 143.0010.00 372.0010.00 604.005.00 152.005.00 383.005.00 613.007.00 163.007.00 392.003.00 622.005.00 172.003.00 403.004.00 633.006.00 183.005.00 414.005.00 642.004.00 193.009.00 423.007.00 654.005.00 202.006.00 434.008.00 664.007.00 212.005.00 443.007.00 674.003.00 223.003.00 453.0010.00 685.007.00 232.005.00 463.007.00 693.0010.00 703.504.00 Makespan for unloading operationsThree different models namely greedy algorithm based on FAT, STF, and LTF were used to determine the makespan for the case study 1. Comparison of the makespan obtained using the three models are presented in REF _Ref230473951 \h Figure ?6.1. It can be observed from REF _Ref230473951 \h Figure ?6.1 that the minimum makespan of 201.5 minutes is achieved using the model based on FAT. Figure ?6.1 Comparison of makespan for unloading one train The number of trucks obtained corresponding to the minimum makespan of 201.5 is 5. For the existing situation, the minimum makespan with 9 trucks is 214.5 minutes. Therefore, there is a saving of 13 minutes and 4 trucks when the model based on FAT principle is used. In terms of makespan, the worst performance was obtained by using the STF model. The minimum makespan and the corresponding number of trucks for the three models and for the existing situation are shown in REF _Ref232525044 \h Table ?6.3.Table STYLEREF 1 \s ?6. SEQ Table \* ARABIC \s 1 3 Minimum makespan and the corresponding number of trucks of unloading operationSTFLTFFATExistingMakespan (minutes)214.5201.5201.5214.5Number of trucks5959Computation of makespan for loading operationsThree different models namely greedy algorithm based on LBT, STF, and LTF were used to determine the makespan for case study 1. Comparison of makespan obtained using the three models is presented in REF _Ref230475459 \h Figure ?6.2. It can be observed from REF _Ref230475459 \h Figure ?6.2 that the minimum makespan of 204.5 minutes is achieved using the model based on STF. Figure ?6.2 Comparison of makespan for loading one trainThe number of trucks obtained corresponding to the minimum makespan of 204.5 is 6. For the existing situation, the minimum makespan with 9 trucks is 213.5 minutes. Therefore, there is a saving of 9 minutes and 3 trucks when the model based on STF principle is used. In terms of makespan, the worst performance was obtained by using the LTF model. The minimum makespan and the corresponding number of trucks for the three models and for the existing situation are shown in REF _Ref232525152 \h Table ?6.4Table STYLEREF 1 \s ?6. SEQ Table \* ARABIC \s 1 4 Minimum makespan and the corresponding number of trucks for loading operationSTFLTFLBTExisting Makespan (minutes)204.5213.5208.5213.5Number of trucks6759Cost of unloading operationsThe cost of unloading a container from a train and transporting it to its location in the storage yard depends upon the travel time of the truck, processing time taken by the crane, and waiting time for the truck. The following equation ( REF _Ref233432928 \h Eq ?6.1 )has been used to compute the cost Cof unloading a single container.?=4×tija-tijd+0.5×wij+siji=1,...n and j=1,...mEq ?6.1Where tija is arrival time of job i on truck j, tijd is departure time of job i on truck j, wij is waiting time of job i on truck j, and sijis the processing time of job i to be loaded on truck j. REF _Ref230478544 \h Figure ?6.3 gives the comparisons of the cost obtained through three models based on the SFT, LFT, and FAT principle. It can be seen from REF _Ref230478544 \h Figure ?6.3 that the lowest cost of operation is obtained using the model based on FAT principle while the SFT model produces the worst results in terms of cost.Figure ?6.3 Comparison of cost of unloading one train REF _Ref232541703 \h Table ?6.5 shows the cost of operation corresponding to minimum makespan obtained through three different models. The existing operation cost is also given in REF _Ref232541703 \h Table ?6.5. Table STYLEREF 1 \s ?6. SEQ Table \* ARABIC \s 1 5 Comparison of costs for unloading operationsSTFLTFFATExistingCost(Rupees)2146.5273221642674Number of trucks5959Cost of loading operationThe cost of loading a container onto a train after bringing container from its location in the storage yard depends upon the travel time of the truck, processing time taken by the crane, and waiting time for the truck. The REF _Ref233432928 \h Eq ?6.1 is used to compute the cost Cof loading a single container REF _Ref230478867 \h Figure ?6.4 gives the comparisons of the cost obtained through three models based on the SFT, LFT, and LBT principles. It can be seen from REF _Ref230478867 \h Figure ?6.4 that the lowest cost of operation is obtained using the model based on LBT principle while the LTF model produces the worst results in terms of cost.Figure ?6.4 Comparison of cost of loading one train REF _Ref233432196 \h Table ?6.6 shows the cost of operation corresponding to minimum makespan obtained through three different models. The existing operation cost is also given in REF _Ref233432196 \h Table ?6.6Table STYLEREF 1 \s ?6. SEQ Table \* ARABIC \s 1 6 Comparison of costs for loading operationsSTFLTFLBTExisting Cost (Rupees)1684186915632176Number of Truck6759Waiting time of unloading operationA truck might have to wait before loading could start on it if there are other trucks in the rail side on which the jobs are being processed. The waiting time of truck depends upon the arrival time and departure time of a truck. The following equation ( REF _Ref233432636 \h Eq ?6.2) has been used to compute the waiting time w of unloading a single containerw=mina=i-Mtija-maxa=i-Mtijd i=1,...n and j=1,...mEq ?6.2where mina=i-Mtija is the minimum arrival time value among set a=i-m, and maxa=i-Mtijd is the maximum departure time value within a set a=i-m. REF _Ref234074431 \h Figure ?6.5 gives the comparisons of the waiting time obtained through three models based on the SFT, LFT, and FAT principles. It can be seen from REF _Ref234074431 \h Figure ?6.5 that the lowest waiting time of operation is obtained using the model based on FAT principle while the LTF model produces the worst results in terms of waiting timeFigure ?6.5 Comparison of waiting time for unloading one train REF _Ref232542612 \h Table ?6.7 shows the waiting time of unloading operation corresponding to minimum makespan obtained through three different models. The existing waiting time for unloading operation is also given in REF _Ref232542612 \h Table ?6.7.Table STYLEREF 1 \s ?6. SEQ Table \* ARABIC \s 1 7 Comparison of waiting time for unloading operationsSTFLTFFATExistingWaiting time (minutes)39711653221165Number of trucks5959Waiting time of loading operationThe waiting time of truck to load a container to a train after coming back from the storage yard depends upon the arrival time and departure time of a truck. The REF _Ref233432636 \h Eq ?6.2 is used to compute the waiting time wof loading a single container REF _Ref234128989 \h Figure ?6.6 gives the comparisons of the waiting time obtained through three models based on the SFT, LFT, and LBT principles. It can be seen from REF _Ref234128989 \h Figure ?6.6 that the lowest waiting time of operation is obtained using the model based on LBT principle while the LTF model produces the worst results in terms of waiting time.Figure ?6.6 Comparison of waiting time for loading one train REF _Ref233357402 \h Table ?6.8 shows the waiting time of loading operation corresponding to minimum makespan obtained through three different models. The existing waiting time for loading operation is also given. It is found that LBT gives a minimum waiting time of 333 minutes while LTF gives a worst waiting time of 838 minutes.Table STYLEREF 1 \s ?6. SEQ Table \* ARABIC \s 1 8 Comparison of waiting time for loading operationsSTFLTFLBTExistingWaiting time(Minutes)562.5 838 3331235Number of trucks6759Case study 2In this case study, as shown in REF _Ref230466174 \h Table ?6.1, there are two trains, 12 trucks and 145 jobs to be processed. The processing time (s) and travel time (2d) for each job is given in REF _Ref233367027 \h Table ?6.9.Table STYLEREF 1 \s ?6. SEQ Table \* ARABIC \s 1 9 Input data for case study 2Job.s(min)d (min)Job.s(min)d (min)Jobs(min)d(min)13.003.50492.002.50972.002.5024.002.50502.003.50982.503.0034.001.50512.002.00992.003.5043.002.00522.001.501002.002.5052.002.50532.006.001013.003.5063.003.50542.002.501022.001.5072.004.50552.003.501033.004.5083.002.50564.001.501043.004.0093.002.00574.004.501052.002.50102.002.50582.002.501062.002.00113.004.00594.006.001074.004.50124.002.50604.002.501086.002.50134.003.50613.003.501093.003.00143.005.00622.002.501103.002.50152.002.50633.003.001115.006.00163.003.50642.002.001121.503.00172.001.50654.002.501133.003.50183.002.50664.003.501145.004.00193.004.50674.001.501153.002.00202.003.00685.003.501165.003.50212.002.50693.005.001174.004.50223.001.50703.502.001181.503.00232.002.50713.003.501192.003.50243.004.50723.001.501202.002.50251.003.50733.002.001212.004.00261.002.50742.002.501222.503.50273.002.00752.503.001236.002.50282.002.50762.003.501245.003.50293.003.50772.002.501252.003.00303.006.00782.501.501264.003.50313.001.50793.003.501272.004.00323.002.50802.002.501284.002.50335.003.50812.002.001294.003.50343.002.00823.004.001302.002.50353.004.50833.002.001313.002.00362.003.50843.002.501325.003.00372.005.00852.006.001332.002.50383.002.50863.002.001342.003.00392.001.50872.004.501353.003.50403.002.00881.502.501364.004.00414.002.50891.501.501372.002.50423.003.50902.002.501384.003.00434.004.00912.503.001396.002.50443.003.50925.003.501403.004.00453.005.00933.002.001413.001.50463.003.50942.003.501424.003.00474.002.50951.504.501434.002.50482.001.50962.005.001443.003.001452.003.5Makespan for unloading operationsThree different models based on FAT, STF, and LTF principles were used to determine the makespan for the case study 2. Comparison of the makespan obtained using the three models is presented in REF _Ref233851849 \h Figure ?6.7. It can be observed from REF _Ref230499490 \h Figure ?6.7 that the minimum makespan of 421 minutes is achieved using the model based on FAT. The number of trucks obtained corresponding to the minimum makespan of 421 is 7. For the existing situation, the minimum makespan with 12 trucks is 437 minutes. Therefore, there is a saving of 16 minutes and 5 trucks when the model based on FAT principle is used. In terms of makespan, the worst performance was obtained by using the LTF model. The minimum makespan and the corresponding number of trucks for the three models and for the existing situation are shown in REF _Ref233710100 \h Table ?6.10.Figure ?6.7 Comparison of makespan for unloading two trains Table STYLEREF 1 \s ?6. SEQ Table \* ARABIC \s 1 10 Minimum makespan and the corresponding number of trucks for unloading operationsSTFLTFFATExisting Makespan (minutes) 434 422.5 421 437Number of trucks56712Makespan for loading operationsThree different models namely greedy algorithm based on LBT, STF, and LTF were used to determine the makespan for the case study 2. Comparison of the makespan obtained using the three models to load two trains is presented in REF _Ref234074646 \h Figure ?6.8. It can be observed from REF _Ref234074646 \h Figure ?6.8 that the minimum makespan of 423.5 minutes is achieved using the model based on STF. The number of trucks obtained corresponding to the minimum makespan of 423.5 is 5. For the existing situation, the minimum makespan with 12 trucks is 432.5 minutes. Therefore, there is a saving of 9 minutes and 7 trucks when the model based on STF principle is used. In terms of makespan, the worst performance was obtained by using the LTF model. Also, there is no decrease in the makespan even the number of trucks are increased beyond 7. The minimum makespan and the corresponding number of trucks for the three models and for the existing situation are shown in REF _Ref232543289 \h Table ?6.11Figure ?6.8 Comparison of makespan of unloading two trainsTable STYLEREF 1 \s ?6. SEQ Table \* ARABIC \s 1 11 Minimum makespan for loading two trainsSTFLTFLBTExistingWaiting time (minutes)423.5 432.5 427.7 432.5Number of trucks56712Cost of unloading operationsThe cost of unloading a containers from trains and transporting it to its location in the storage yard depends upon the travel time of the truck, processing time taken by the crane, and waiting time for the truck. The REF _Ref233432928 \h Eq ?6.1 used to compute the cost Cof unloading a single container. REF _Ref234074800 \h Figure ?6.9 gives the comparisons of the cost obtained through three models based on the SFT, LFT, and FAT principles. It can be seen from REF _Ref234074800 \h Figure ?6.9 that the lowest cost of operation is obtained using the model based on STF principle while the FAT model produces the worst results in terms of cost.Figure ?6.9 Comparison of cost for unloading two trainsTable ?6.12 shows the cost of operation corresponding to minimum makespan obtained through three different models. The existing operation cost is also given in Table ?6.12. Table STYLEREF 1 \s ?6. SEQ Table \* ARABIC \s 1 12 Operation cost for unloading two trainsSTFLTFFATExistingCost (Rupees)4400 4695 48616375 Number of trucks56712Cost of loading operationsThe cost of loading a container onto a train after bringing it from its location in the storage yard depends upon the travel time of the truck, processing time taken by the crane, and waiting time for the truck. The REF _Ref233432928 \h Eq ?6.1 used to compute the cost Cof loading a single container. REF _Ref234129243 \h Figure ?6.10 gives the comparisons of the cost obtained through three models based on the SFT, LFT, and LBT principles. It can be seen from REF _Ref234129243 \h Figure ?6.10 that the lowest cost of operation is obtained using the model based on LBT principle while the LTF model produces the worst results in terms of cost.Figure ?6.10 Comparison of cost for loading two trains REF _Ref232543766 \h \* MERGEFORMAT Table ?6.13 shows the cost of operation corresponding to minimum makespan obtained through three different models. The existing operation cost is also given in REF _Ref232543766 \h Table ?6.13.Table STYLEREF 1 \s ?6. SEQ Table \* ARABIC \s 1 13 Operation cost for loading two trainsSTFLTFLBTExistingCost (Rupees)3574 3935.533845059.5 Number of trucks78612Waiting time for unloading operationsThe waiting time of truck to unload a container from a train after return back to the rail yard depends upon the arrival time and departure time of a truck. The equation 6-2 has been used to compute the waiting time w of unloading a single container REF _Ref234129553 \h Figure ?6.11which give the comparisons of the waiting time obtained through three models based on the SFT, LFT, and FAT principles. It can be seen from REF _Ref234129553 \h Figure ?6.11 that the lowest waiting time of operation is obtained using the model based on STF principle while the FAT model produces the worst results in terms of waiting time.Figure ?6.11 Comparison of waiting time for unloading two trains REF _Ref233374705 \h Table ?6.14 shows the waiting time of unloading operation corresponding to minimum makespan obtained through three different models. The existing waiting time for unloading operation is also given in REF _Ref233374705 \h Table ?6.14.Table STYLEREF 1 \s ?6. SEQ Table \* ARABIC \s 1 14 Waiting time for unloading two trainsSTFLTFFATExistingWaiting time (minutes)81412341525.53856Number of trucks56712Waiting time for loading operationsThe waiting time of truck to load a container to a train after coming back to the storage yard depends upon the arrival time and departure time of a truck. The REF _Ref233432636 \h Eq ?6.2 is used to compute the waiting time wof loading a single container. REF _Ref230504283 \h Figure ?6.12 presents the comparisons of the waiting time obtained through three models based on the SFT, LFT, and LBT principles. It can be seen from REF _Ref230504283 \h Figure ?6.12 that the lowest waiting time of operation is obtained using the model based on LBT principle while the LTF model produces the worst results in terms of waiting time.Figure ?6.12 Comparison of waiting time for loading two trains REF _Ref232544204 \h Table ?6.15 shows the waiting time of unloading operation corresponding to minimum makespan obtained through three different models. The existing waiting time for unloading operation is also given in REF _Ref232544204 \h Table ?6.15.Table STYLEREF 1 \s ?6. SEQ Table \* ARABIC \s 1 15 Waiting time for loading two trainsSTFLTFLBTExistingWaiting time (minutes)1576.5211711513779Number of trucks78612Case study 3 This section describes the results of application of greedy algorithm model based on FAT principle, reverse greedy algorithm model based on LBT principle, greedy algorithm model based on STF principle, and greedy algorithm model based on LTF principle. In this case study, as given in REF _Ref230466174 \h Table ?6.1 there are three trains, 15 trucks and 210 jobs to be processed. The processing time (s) and travel time (2d) for each job for case study 3 is given in REF _Ref233402865 \h Table ?6.16Table STYLEREF 1 \s ?6. SEQ Table \* ARABIC \s 1 16 Input data for case study 3jobs(min)2d(min)jobs(min)2d(min)job.s(min)2d(min) 14.00 5.00 713.007.00 1412.007.00 22.007.00 722.009.00 1422.005.00 32.008.00 733.005.00 1432.503.00 42.004.00 743.004.00 1443.007.00 52.506.00 752.005.00 1452.005.00 62.005.00 763.008.00 1462.004.00 72.006.00 774.005.00 1473.008.00 82.005.00 784.007.00 1483.004.00 92.0010.00 793.0010.00 1493.005.00 103.005.00 802.005.00 1502.0012.00 113.006.00 813.007.00 1513.00 4.00 125.007.00 822.003.00 1522.009.00 134.003.00 833.005.00 1531.505.00 143.007.00 843.009.00 1541.503.00 153.006.00 852.006.00 1552.005.00 162.005.00 862.005.00 1562.506.00 172.004.00 873.003.00 1575.007.00 183.008.00 882.005.00 1583.004.00 192.005.00 893.009.00 1592.007.00 203.004.00 901.007.00 1601.509.00 213.506.00 911.005.00 1612.0010.00 223.00 7.00 923.004.00 1622.005.00 232.508.00 932.005.00 1632.506.00 242.005.00 943.00 7.00 1642.007.00 253.003.00 953.0012.00 1652.005.00 262.005.00 963.003.00 1663.007.00 273.008.00 973.005.00 1672.003.00 281.504.00 985.007.00 1683.009.00 293.007.00 993.004.00 1693.008.00 302.005.00 1003.009.00 1702.005.00 314.007.00 1012.007.00 1712.004.00 323.004.00 1022.0010.00 1724.009.00 332.005.00 1033.005.00 1736.005.00 343.008.00 1042.003.00 1743.006.00 352.004.00 1053.004.00 1753.005.00 363.007.00 1064.005.00 1765.0012.00 372.004.00 1073.007.00 1771.506.00 383.0010.00 1084.008.00 1783.007.00 393.504.00 1093.007.00 1795.008.00 402.005.00 1103.0010.00 1803.004.00 413.006.00 1113.007.00 1815.007.00 424.005.00 1124.005.00 1824.009.00 434.008.00 1132.003.00 1831.506.00 443.007.00 1142.005.00 1842.007.00 452.004.00 1152.007.00 1852.005.00 462.0010.00 1162.004.00 1862.008.00 472.005.00 1172.003.00 1872.507.00 483.004.00 1182.0012.00 1886.005.00 493.009.00 1192.005.00 1895.007.00 502.005.00 1202.007.00 1902.006.00 513.006.00 1214.003.00 1914.007.00 522.005.00 1224.009.00 1922.008.00 532.004.00 1232.005.00 193 4.005.00 543.007.00 1244.0012.00 1944.007.00 554.005.00 1254.005.00 1952.005.00 562.004.00 1263.007.00 1963.004.00 573.007.00 1272.005.00 1975.006.00 583.005.00 1283.006.00 1982.005.00 592.0010.00 1292.004.00 1992.006.00 605.007.00 1304.005.00 2003.007.00 613.005.00 1314.007.00 2014.008.00 624.004.00 1324.003.00 2022.005.00 631.506.00 1335.007.00 2034.006.00 642.005.00 1343.0010.00 2046.005.00 652.007.00 1353.504.00 2053.008.00 663.007.00 1363.007.00 2063.003.00 674.005.00 1373.003.00 2074.006.00 684.003.00 1383.004.00 2084.005.00 693.004.00 1392.005.00 2093.006.00 702.005.00 1402.506.00 2102.007.00 Makespan for unloading operationsA comparison of the makespan obtained using the three models STF, LTF, and FAT is presented in REF _Ref230504733 \h Figure ?6.13 It can be observed from REF _Ref230504733 \h Figure ?6.13 that the minimum makespan of 598.5 minutes is achieved using the model based on LTF. The number of trucks obtained corresponding to the minimum makespan of 598.5 is 8. For the existing situation, the minimum makespan with 15 trucks is 622 minutes. Therefore, there is a saving of 23.5 minutes and 7 trucks when the model based on LTF principle is used. In terms of makespan, the worst performance was obtained by using the STF model. Figure ?6.13 Comparison of makespan for unloading three trainsThe minimum makespan and the corresponding number of trucks for the three models and for the existing situation are shown in REF _Ref233385071 \h Table ?6.17.Table STYLEREF 1 \s ?6. SEQ Table \* ARABIC \s 1 17 Minimum Makespan for unloading three trainsSTFLTFFATExisting Makespan(minutes)610.5 598.5601622Number of trucks58715Makespan for loading operationsA Comparison of the makespan obtained using the three models STF, LTF, and LBT is presented in REF _Ref230505433 \h Figure ?6.14 It can be observed from REF _Ref230505433 \h Figure ?6.14 that the minimum makespan of 599.5 minutes is achieved using the model based on STF. The number of trucks obtained corresponding to the minimum makespan of 599.5 is 8. For the existing situation, the minimum makespan with 15 trucks is 608.5 minutes. Therefore, there is a saving of 9 minutes and 7 trucks when the model based on STF principle is used. In terms of makespan, the worst performance was obtained by using the LTF model. The minimum makespan and the corresponding number of trucks for the three models and for the existing situation are shown in REF _Ref232544650 \h Table ?6.18.Figure ?6.14 Comparison of makespan for loading three trainsTable STYLEREF 1 \s ?6. SEQ Table \* ARABIC \s 1 18 Minimum makespan for loading three trainsSTFLTFLBFExistingMakespan599.5 608.5601.5608.5Number of trucks88615Cost for unloading operationsThe cost of unloading a containers from trains and transporting it to its location in the storage yard depends upon the travel time of the truck, processing time taken by the crane, and waiting time for the truck. The REF _Ref233432928 \h Eq ?6.1 is used to compute the cost Cof unloading a single container. REF _Ref230505727 \h Figure ?6.15 gives the comparisons of the cost obtained through three models based on the SFT, LFT, and FAT principles. It can be seen from REF _Ref230505727 \h Figure ?6.15 that the lowest cost of operation is obtained using the model based on STF principle while the LTF model produces the worst results in terms of cost.Figure ?6.15 Comparison of cost for unloading three trains REF _Ref233391722 \h Table ?6.19 shows the cost of operation corresponding to minimum makespan obtained through three different models. The existing operation cost is also given in REF _Ref233391722 \h Table ?6.19.Table STYLEREF 1 \s ?6. SEQ Table \* ARABIC \s 1 19 Operation cost for unloading three trainsSTFLTFFATExistingCost (Rupees)6265 7326.5 690810057 Number of trucks58715Cost for loading operationsThe cost of loading a container onto a train after bringing it from its location in the storage yard depends upon the travel time of the truck, processing time taken by the crane, and waiting time for the truck. The REF _Ref233432928 \h Eq ?6.1 is used to compute the cost Cof loading a single container REF _Ref230506289 \h Figure ?6.16 gives the comparisons of the cost obtained through three models based on the SFT, LFT, and LBT principles. It can be seen from REF _Ref230506289 \h Figure ?6.16 that the lowest cost of operation is obtained using the model based on LBT principle while the LTF model produces the worst results in terms of cost.Figure ?6.16 Comparison of cost for loading three trains REF _Ref232544729 \h Table ?6.20 shows the cost of operation corresponding to minimum makespan obtained through three different models. The existing operation cost is also given in REF _Ref232544729 \h Table ?6.20. it is found that STF gave the minimum cost while LTF gave the worst results.Table STYLEREF 1 \s ?6. SEQ Table \* ARABIC \s 1 20 Operation Cost for loading three trainsSTFLTFLBTExistingCost (Rupees)535655104746.58209.5 Number of trucks88715Waiting time for unloading operationsThe waiting time of truck to unload a container from a train after return back to the rail yard depends upon the arrival time and departure time of a truck. The REF _Ref233432636 \h Eq ?6.2 has been used to compute the waiting time w of unloading a single container REF _Ref230506675 \h Figure ?6.17 gives the comparisons of the waiting time obtained through three models based on the SFT, LFT, and FAT principles. It can be seen from REF _Ref230506675 \h Figure ?6.17 that the lowest waiting time of operation is obtained using the model based on STF principle while the LTF model produces the worst results in terms of waiting time.Figure ?6.17 Comparison of waiting time for unloading three trains REF _Ref233396553 \h Table ?6.21 shows the waiting time of operation corresponding to minimum makespan obtained through three different models. The existing operation cost is also given in REF _Ref233396553 \h Table ?6.21 Table STYLEREF 1 \s ?6. SEQ Table \* ARABIC \s 1 21 Waiting time for unloading three trainsSTFLTFFATExistingWaiting time (minutes)1139 29082225.58209.5Number of trucks58715Waiting time for loading operationsThe waiting time of truck to load a container to a train after coming back to the storage yard depends upon the arrival time and departure time of a truck. The REF _Ref233432636 \h Eq ?6.2 is used to compute the waiting time wof loading a single container. REF _Ref230507735 \h Figure ?6.18 gives the comparisons of the waiting time obtained through three models based on the SFT, LFT, and LBT principles. It can be seen from REF _Ref230507735 \h Figure ?6.18 that the lowest waiting time of operation is obtained using the model based on LBT principle while the LTF model produces the worst results in terms of waiting timeFigure ?6.18 Comparison of waiting time for loading of three trains REF _Ref233402263 \h Table ?6.22 shows the waiting time of operation corresponding to minimum makespan obtained through three different models. The existing operation cost is also given in REF _Ref233402263 \h Table ?6.22Table STYLEREF 1 \s ?6. SEQ Table \* ARABIC \s 1 22 Waiting Time for loading three trainsSTFLTFLBTExistingWaiting time(minutes)2818.5 2969.516647093Number of trucks88615Case study 4This section describes the results of application of greedy algorithm model based on FAT principle, reverse greedy algorithm model based on LBT principle, greedy algorithm model based on STF principle, and greedy algorithm model based on LTF principle. In this case, as given in REF _Ref230466174 \h Table ?6.1 there are four trains, 18 trucks and 270 jobs to be processed. The processing time (s) and travel time (2d) for each job for case study 3 is given in REF _Ref233402766 \h Table ?6.23Table STYLEREF 1 \s ?6. SEQ Table \* ARABIC \s 1 23 Input data of case study 4jobs(min)d (min)job.s(min)d (min)job.s (min)d (min)14.002.50911.002.501814.002.5022.003.50923.002.001822.002.0032.004.00932.002.501833.003.5042.002.00943.003.501843.002.50 52.503.00953.006.001852.005.00 62.002.50963.001.501865.003.50 72.003.00974.004.001873.002.50 82.002.50983.00 3.501884.002.00 92.005.00993.005.001891.503.00103.002.501003.003.501902.002.50113.003.001014.002.501912.003.50125.003.501022.001.501925.003.50134.001.501032.002.501934.001.50143.003.501042.003.501943.003.50153.003.001052.002.001953.003.00162.002.501063.002.501962.002.50172.002.001075.003.501972.002.00183.004.001083.002.001983.004.00192.002.501093.00 4.501992.002.50203.002.001102.003.502001.504.50213.503.001112.005.002012.005.00223.003.501123.002.502022.002.50232.504.001132.001.502032.503.00242.002.501143.002.002042.003.50253.001.501154.002.502052.002.50262.002.501163.003.502063.003.50273.004.001172.001.502072.001.50281.502.001182.006.002083.004.50293.003.501192.002.502093.004.00302.002.501202.003.502102.002.50314.003.501214.001.502113.002.00323.002.001224.004.502122.002.00332.002.501232.002.502134.004.50343.004.001244.006.002146.002.50352.002.001254.002.502153.003.00363.003.501263.003.502163.002.50372.002.001272.002.502175.006.00383.005.001283.003.002181.503.00393.502.001292.002.002193.003.50402.002.501304.002.502205.004.00413.003.001314.003.502213.002.00424.002.501324.001.502225.003.50434.004.001335.003.502234.004.50443.003.501343.005.002241.503.00452.002.001353.502.002252.003.50462.005.001364.002.502262.002.50472.002.501372.003.502272.004.00483.002.001382.004.002282.503.50493.004.501392.002.002296.002.50502.002.501402.503.002305.003.50513.003.001412.002.502312.003.00522.002.501422.003.002324.003.50532.002.001432.002.502332.004.00543.003.501442.005.002344.002.50554.002.501453.002.502354.003.50562.002.001463.003.002362.002.50573.003.501473.503.002373.002.00583.002.501483.003.502385.003.00592.005.001492.504.002392.002.50605.003.501502.002.502402.003.00613.002.501513.001.502413.003.50624.002.001522.002.502424.004.00631.503.001533.004.002432.002.50642.002.501541.502.002444.003.00652.003.501553.003.502452.004.50663.004.001562.002.502461.502.50674.002.501574.003.502471.501.50684.003.501583.002.002482.002.50693.005.001592.002.502492.503.00702.002.501603.004.002505.003.50713.003.501612.002.002513.002.00722.001.501623.003.502526.002.50733.002.501632.002.002533.004.00743.004.501643.005.002543.001.50752.003.001653.502.002554.003.00763.003.501662.002.502564.002.50774.002.501673.003.002573.003.00784.001.501684.002.502582.003.50793.002.001694.004.002593.003.50802.002.501703.003.502603.001.50813.003.501712.002.002613.002.00822.004.501722.005.002622.002.50833.002.501732.002.502632.503.00843.002.001743.002.002642.003.50852.002.501753.004.502652.003.50862.002.501762.002.502662.002.50873.001.501773.003.002672.501.50882.002.501782.002.502683.003.50893.004.501792.002.002692.002.50901.003.501803.003.502702.002.00Makespan for unloading operationsA Comparison of makespan obtained using the three models based on STF, LTF, and FAT principles is presented in REF _Ref230507995 \h Figure ?6.19 It can be observed from REF _Ref230507995 \h Figure ?6.19 that the minimum makespan of 760 minutes is achieved using the model based on FAT. The number of trucks obtained corresponding to the minimum makespan of 760 is 7. For the existing situation, the minimum makespan with 18 trucks is 774 minutes. Therefore, there is a saving of 14 minutes and 11 trucks when the model based on FAT principle is used. The minimum makespan and the corresponding number of trucks for the three models and for the existing situation are shown in REF _Ref233408376 \h Table ?6.24. In terms of makespan, the worst performance was obtained by using the STF model.Figure ?6.19 Comparison of makespan for unloading four trainsTable STYLEREF 1 \s ?6. SEQ Table \* ARABIC \s 1 24 Minimum makespan for unloading four trainsSTFLTFFATExistingMakespan (minutes)771 760.5760774Number of trucks88718Makespan for loading operationsA comparison of the makespan obtained using the three models based on STF, LTF, and LBT principles is presented in REF _Ref230508374 \h Figure ?6.20. It can be observed from REF _Ref230508374 \h Figure ?6.20 that the minimum makespan of 761.5 minutes is achieved using the model based on STF. The number of trucks obtained corresponding to the minimum makespan of 761.5 is 8. For the existing situation, the minimum makespan with 18 trucks is 770.5 minutes. Therefore, there is a saving of 9 minutes and 11 trucks when the model based on STF principle is used. In terms of makespan, the worst performance was obtained by using the LTF model. The minimum makespan and the corresponding number of trucks for the three models and for the existing situation are shown in REF _Ref232545418 \h Table ?6.25. Figure ?6.20 Comparison of makespan for loading three trainsIt can be seen from REF _Ref230508374 \h Figure ?6.20 that there is no reduction in the makespan even when the number of trucks are increased beyond 7. This results shows that no further savings in terms of makespan could be achieved by increasing the number of trucks beyond 7 with either of the three models considered here. However, the optimal number of trucks in this case study is 5.Table STYLEREF 1 \s ?6. SEQ Table \* ARABIC \s 1 25 Minimum makespan for loading four trainsSTFLTFLBFExistingMakespan( minutes)761.5 770.5763.5770.5Number of trucks87518Cost for unloading operationThe cost of unloading a containers from trains and transporting it to its location in the storage yard depends upon the travel time of the truck, processing time taken by the crane, and waiting time for the truck. The REF _Ref233432928 \h Eq ?6.1 is used to compute the cost Cof unloading a single container. The comparisons of the cost obtained through three models based on the STF, LTF, and FAT principles is presented in REF _Ref234127146 \h Figure ?6.21. It can be seen from REF _Ref232544729 \h Table ?6.20 that the lowest cost of operation is obtained using the model based on FAT principle while the LTF model produces the worst results in terms of cost.Figure ?6.21 Comparison of cost of unloading four trains REF _Ref232545638 \h Table ?6.26 shows the cost of operation corresponding to minimum makespan obtained through three different models. The existing operation cost is also given in REF _Ref232545638 \h Table ?6.26.Table STYLEREF 1 \s ?6. SEQ Table \* ARABIC \s 1 26 Comparison of operation cost for unloading four trainsSTFLTFFATExistingCost (Rupees.)912492788784.513974Number of Trucks88718Cost for loading operationThe cost of loading a container onto a train after bringing it from its location in the storage yard depends upon the travel time of the truck, processing time taken by the crane, and waiting time for the truck. The REF _Ref233432928 \h Eq ?6.1 is used to compute the cost Cof loading a single container. REF _Ref234130037 \h Figure ?6.22gives the comparison of cost obtained through three models based on the SFT, LFT, and LBT principles. It can be seen from REF _Ref234130037 \h Figure ?6.22 that the lowest cost of operation is obtained using the model based on LBT principle while the STF model produces the worst results in terms of cost.Figure ?6.22 Comparison of cost for loading four trains REF _Ref232545654 \h Table ?6.27 shows the cost of operation corresponding to minimum makespan obtained through three different models. The existing operation cost is also given in REF _Ref232545654 \h Table ?6.27.Table STYLEREF 1 \s ?6. SEQ Table \* ARABIC \s 1 27 Operation cost of for loading four trainsSTFLTFLBTExistingCost (Rupees)6780.5 6488.5 560411621 Number of trucks87518Waiting time for unloading operationThe waiting time of truck to unload a container from a train after return back to the rail yard depends upon the arrival time and departure time of a truck. The REF _Ref233432636 \h Eq ?6.2 has been used to compute the waiting time w of unloading a single container REF _Ref234130127 \h Figure ?6.23 gives the comparison of the waiting time obtained through three models based on the SFT, LFT, and FAT principles. It can be seen from REF _Ref234130127 \h Figure ?6.23 that the lowest waiting time of operation is obtained using the model based on FAT principle while the LTF model produces the worst results in terms of waiting time. Figure ?6.23Comparison of waiting time for unloading four trains REF _Ref232545893 \h Table ?6.28 shows the waiting time of operation corresponding to minimum makespan obtained through three different models. The existing operation cost is also given in REF _Ref232545893 \h Table ?6.28 Table STYLEREF 1 \s ?6. SEQ Table \* ARABIC \s 1 28 Waiting time for unloading four trainsSTFLTFFATExistingWaiting time(minutes)3645.5 3694.5286311287.5Number of trucks88718Waiting time of loading operationThe waiting time of truck to load a container to a train after coming back to the storage yard depends upon the arrival time and departure time of a truck. The REF _Ref233432636 \h Eq ?6.2 is used to compute the waiting time wof loading a single container. REF _Ref234130199 \h Figure ?6.24 gives the comparisons of the waiting time obtained through three models based on the STF, LTF, and LBT principles. It can be seen from REF _Ref234130199 \h Figure ?6.24 that the lowest waiting time of operation is obtained using the model based on LBT principle while the STF model produces the worst results in terms of waiting timeFigure ?6.24 Comparison of waiting time for loading four trains REF _Ref233412110 \h Table ?6.29 shows the waiting time of operation corresponding to minimum makespan obtained through three different models. The existing operation cost is also given in REF _Ref233412110 \h Table ?6.29.Table STYLEREF 1 \s ?6. SEQ Table \* ARABIC \s 1 29 Waiting time for loading four trainsSTFLTFLBTExistingWaiting time (minutes)3605 29951396.511232.5Number of trucks87518Summary of loading and unloading resultsIn this section, summary of results of minimum makespan and related number of trucks, cost and waiting time is presented in REF _Ref230510185 \h Table ?6.30, REF _Ref230552173 \h Table ?6.31, REF _Ref230552175 \h Table ?6.32. The results presented here have obtained from models based on STF, LTF, FAT, and LBT scheduling mechanisms as discussed in the previous sections. The number of jobs considered in case studies 1 to 4 ranges from 70 to 270. The number of trucks varies from 9 to 18, and upto four trains have been considered in the four case studies discussed in the previous sections. Summary of minimum makespan with related number of trucks obtained with four models based on different scheduling algorithms for loading unloading operations with different number of trains are given in REF _Ref230510185 \h Table ?6.30. The summary of cost related to the minimum makespan with number of trucks is given in REF _Ref230552173 \h Table ?6.31. In same way, the summary of waiting time is given in REF _Ref230552175 \h Table ?6.32. Table STYLEREF 1 \s ?6. SEQ Table \* ARABIC \s 1 30 Summary of minimum makespan for loading-unloading operationsScheduling MechanismsSTFLTFLBTFATOne Train (loading operations)Makespan(min)204.5213.5208-Trucks675-One Train (unloading operations)Makespan(min)214.5204.5-201.5Trucks59-5Two Trains(loading operations)Makespan(min)423.5432.5427.7-trucks786-Two Trains(unloading operations)Makespan(min)434422.5-421trucks56-7Three Trains(loading operations)Makspan(min)599.5608.5601.5-trucks886-Three Trains(unloading operations)Makespan(min)610.5602.5-601trucks55-7Four Trains(loading operations)Makespan(min)761.5770.5763.5-trucks875-Four Trains(unloading operations)Makspan(min)771760.5-760trucks88-7Table STYLEREF 1 \s ?6. SEQ Table \* ARABIC \s 1 31 Summary of cost corresponding to the minimum makespan for loading and unloading operationsScheduling mechanismSTFLTFLBTFATOne Train(loading operations)Cost (Rs)168418691563-trucks675-One Train (unloading operations)Cost(Rs)21462180-2164.5trucks55-5Two Trains(loading operations)Cost(Rs)35743935.53384-trucks786-Two Trains(unloading operations)Cost(Rs)44004695-4861trucks56-7Three Trains(loading operations)Cost(Rs)535655104746.5trucks886-Three Trains(unloading operations)Cost (Rs)62656319-6908trucks587Four Trains(loading operations)Cost(Rs)6780.56488.55604-trucks875-Four Trains(unloading operations)Cost(Rs)91249278-8784.5trucks88-7Table STYLEREF 1 \s ?6. SEQ Table \* ARABIC \s 1 32 Summary of waiting time corresponding to the minimum makespan for loading and unloading operationsScheduling mechanismSTFLTFLBTFATOne Train(loading operations)Waiting time(min)562.5838333-trucks675-One Train (unloading operations)Waiting time(min)397391-322trucks55-5Two Trains(loading operations)Waiting time(min)1576.521171151trucks786-Two Trains(unloading operations)Waiting time(min)8141234-1525.5trucks56-7Three Trains(loading operations)Waiting time(min)2818.52969.51664trucks886-Three Trains(unloading operations)Waiting time(min)11392908-2225.5trucks58-7Four Trains(loading operations)Waiting time(min)360529951396.5-trucks875-Four Trains(unloading operations)Waiting time(min)3645.53694.5-2863trucks88-7Analysis of models resultsOptimal number of trucksIn this section, analysis of results obtained from models based on STF, LTF, FAT, and LBT scheduling mechanisms has been carried out. The results have been presented for optimal number of trucks, makespan, cost, and waiting time for different number of trains. In each case study, the results have presented for loading, unloading and combined loading-unloading operations. The optimal number of trucks required to unload different number of trains is presented in REF _Ref234130289 \h Figure ?6.25. It can be seen from REF _Ref234130289 \h Figure ?6.25 that for unloading one to three trains, the best results in terms of minimum number of trucks required is obtained using STF model. For unloading four trains, the best results were obtained using FAT model. Results obtained by FAT model are as good as those obtained by STF model for unloading one train. The results produced by LTF model are inferior to STF and FAT models for unloading any number of trains. REF _Ref234130374 \h Figure ?6.26 shows optimal number of trucks required for loading a given number of trains using STF, LTF, and LBT models. The optimal solution obtained using LBT model is superior to those produced by other models for loading operations. For loading one train, the STF model suggests that six numbers of trucks must be used for loading one train. However, a better optimal solution (five trucks) is obtained using LBT model. Similarly, LBT model produces the best solution for loading two to four trains. The worst results are produced by the LTF model.Figure ?6.25 Number of trucks versus number of trains in unloading processFigure ?6.26 Number of trucks versus number of trains in loading processFigure ?6.27 Number of trucks versus number of trains in loading-unloading processThe optimal results obtained by using different models for combined loading and unloading operations are presented in REF _Ref230559416 \h Figure ?6.27. The STF and LTF model have been applied to both loading and unloading operations. The LBT model is used for loading operations only while FAT model can be used for unloading operations. It can be seen from REF _Ref230559416 \h Figure ?6.27 that ten trucks are required for loading and unloading a single train. For processing both loading and unloading jobs for two and three trains, the best results are obtained using STF model. For four trains, the best results (12 trucks) are obtained by using FAT and LBT models. The worst results for combined operations are produced by the LTF model.Optimal makespan REF _Ref230559876 \h Figure ?6.28 shows optimal makespan for unloading different number of trains using STF,LTF, and FAT models while REF _Ref230560026 \h Figure ?6.29 shows optimal makespan for loading different number of trains using STF, LTF, and LBT model. REF _Ref230560163 \h Figure ?6.30 shows optimal makespan for combined loading and unloading number of trains using STF, LTF, LBT, andFAT algorithms. The optimal makespan for combined laoding and unloading process is shown in REF _Ref230560163 \h Figure ?6.30.Figure ?6.28 Makespan versus number of trains in an unloading processFigure ?6.29 Makespan versus number of trains in a loading processFigure ?6.30 Makespan versus number of trains in loading and unloading processIt can be seen from REF _Ref230559876 \h Figure ?6.28 that the FAT model produces the best results for unloading one, two and four number of trains. For unloading three trains, LTF model produces the best results. For unloading three trains, the results produced by FAT are only marginally lower than the LTF model. Therefore, FAT model can be considered as the best model for unloading processes in terms of makespan, This result is consistent with the theorem 1 which states that greedy algorithm based on FAT principle produces optimal results for unloading processes. The worst results are produced by the STF model for unloading any number of trains. For loading jobs, STF model produces the best results for any number of trains considered. The worst results in case of loading jobs were produced by LTF as can be seen from REF _Ref230560026 \h Figure ?6.29. For combined loading and unloading process, FAT and LBT models together produce the best results. The worst results for combined loading and unloading of one, three or four number of trains are produced by the STF model. However, for combined loading and unloading of a single train, the worst results are obtained by LTF model.Optimal cost REF _Ref230560407 \h Figure ?6.31 shows optimal cost for unloading different number of trains using STF, LTF, and FAT algorithms while REF _Ref234130499 \h Figure ?6.32 shows optimal cost for loading different number of trains using STF, LTF, and LBT models. For combined loading and unloading operations, the results are shown in REF _Ref234130548 \h Figure ?6.33. Figure ?6.31 Cost versus number of trains in unloading processFigure ?6.32 Cost versus number of trains in loading processFigure ?6.33 Cost versus number of trains in combined loading-unloading processIt can be seen from REF _Ref230560407 \h Figure ?6.31 that the STF model produces best results for unloading one, two or three number of trains. For unloading trains, FAT model produces the best results. The LTF model produces worst results for most cases for unloading operations. For loading operations, LBT produces the best results for all cases of number of trains. The worst results for loading operations are produced by LTF for one, two and three number of trains. For loading four number of trains, STF produces the worst results as can be seen from REF _Ref234130499 \h Figure ?6.32. For combined loading and unloading operations, the FAT and LBT model produces the best results in terms of cost of operation for one and four number of trains. For combined loading and unloading operations of two and three trains, STF model produces the best results. The LTF model produces the worst results for most of the cases.Optimal waiting time REF _Ref234130665 \h Figure ?6.34 shows optimal waiting time for unloading different number of trains using STF, LTF, and FAT models. REF _Ref234130690 \h Figure ?6.35 shows optimal waiting time for unloading different number of trains using STF, LTF, and LBT models. REF _Ref234130724 \h Figure ?6.36 shows optimal waiting time for combined loading and unloading operations for different number of trains.Figure ?6.34 Waiting time versus number of trains in an unloading processFigure ?6.35 Waiting time versus number of trains in loading ProcessFigure ?6.36 Waiting time versus number of trains in combined loading-unloading processFrom the REF _Ref234130665 \h Figure ?6.34, it can be seen that the best results are obtained for two and three number of trains using STF model. For one and four number of trains the best results are obtained by FAT model. The FAT model produces worst results for two and three number of trains while for one and four number of trains the LTF model produces result that are substantially inferior to that produced by FAT. For unloading a single train, the results produced by LTF model are 3 times inferior to those produced by FAT model. For loading operations, LBT produces far better results that are produced by other two models ( REF _Ref234130690 \h Figure ?6.35). It can be seen from REF _Ref234130690 \h Figure ?6.35 that the worst results for loading operations are produced by LTF models for one, two, or three number of trains. For four number of trains, STF produces the worst results. For combined loading-unloading operations, the best results for one, three and four trains are obtained using the LBT and FAT models together. For combined loading-unloading of two trains, the best results are obtained using STF. The worst results for all the cases except for four trains are obtained by LTF. When the numbers of trains are four, the STF model produces the worst results.Recommended ModelsThis section presents a summary of recommended models for loading operations, unloading operations and combined loading and unloading operations for different number of trains. REF _Ref233779047 \h Table ?6.33 presents the recommended models and associated savings for loading, unloading and combined loading-unloading processes for a single train. The computation of savings has been carried out with respect to the existing operation procedures being followed at ICD, Tughlakabad. It can be seen from REF _Ref233779047 \h Table ?6.33 that by using the models recommended in this study, a substantial savings in operation costs can be achieved. REF _Ref233780343 \h Table ?6.34, REF _Ref234138637 \h Table ?6.35, and REF _Ref234139681 \h Table ?6.36 present a summary of recommend models, cost savings, savings in resources for loading, unloading, and combined loading and unloading processes for two, three and four trains respectively. The computations of savings in cost, time and resources (trucks) is presented in REF _Ref234139827 \h Table ?6.37, REF _Ref234139834 \h Table ?6.38, and REF _Ref234139840 \h Table ?6.39. It can be seen from these Tables that substantial savings can be achieved by using the models developed in this study.Table STYLEREF 1 \s ?6. SEQ Table \* ARABIC \s 1 33 Recommended models for loading and unloading one trainLoading operationsMin ValueRecommended ModelSavings (minute)Percentage savingsMakespan (minutes)204.5STF213.5 – 204.5 = 73.4%Cost (Rs.)1563LBT2176-1563=61339,2%Waiting time (minutes)333LBT1235-333=902270%trucks5LBT9-5=480%Unloading operationMakespan (minutes)201.5FAT214-201.5=12.56.2%Cost (Rs.)2146STF2732-2146=58627%Waiting time (minutes)322FAT1235-322=913283.5%trucks5FAT, STF9-5=480%Combined operationMakespan (minutes)406STF(L)FAT(UL)428-406=225.4%Cost (Rs.)3709LBT(L)STF(UL)4908-3709=119932%Waiting time (minutes)655LBT(L)FAT(UL)2400-655=1745266%trucks10LBT(5L)FAT(UL)18-10=880%Table STYLEREF 1 \s ?6. SEQ Table \* ARABIC \s 1 34 Recommended models for loading and unloading two trainsLoading OperationsMin ValueRecommended ModelSavings (minute)Percentage savingsMakespan (minutes)423.5STF432.5-423.5=92.1%Cost (Rs.)3384LBT5059.5-3384=1675.549.5%Waiting time (minutes)1151LBT3779-1151=2628 228%trucks6FAT12-6=6100%Unloading operationMakespan (minutes)421FAT437-421=163.8%Cost (Rs.)4400STF6375-4400=1975 44.8%Waiting time (minutes)814STF3856-814=3042 373.7%trucks5STF12-5=7 140%Combined operationMakespan (minutes)844.5STF(L)FAT(UL)869.5-844.5=25 2.9%Cost (Rs.)7748LBT(L)STF(UL)11434.5-7748= 3686.547.5%Waiting time (minutes)1965LBT(L)STF(UL)7635-1965=5670 288.5%trucks12(7+5)LBT(L)FAT(UL)24-12=12 trucks100%Table STYLEREF 1 \s ?6. SEQ Table \* ARABIC \s 1 35 Recommended models for loading and unloading three trainsLoading OperationsMin ValueRecommended ModelSavings Percentage savingsMakespan (minutes)599.5STF608.5-599.5 = 91.5%Cost (Rs.)4746.5LBT8209.5-4746.5=346377.2%Waiting time (minutes)1664LBT7093-1664=5429326%trucks6LBT15-6=9 150%Unloading operationMakespan (minutes)598.5LTF622-598.5=23.53.9%Cost (Rs.)6265STF10075-6265=379260%Waiting time (minutes)1139STF8209.5-1139=7070620%trucks5STF15-5=10200%Combined operationMakespan (minutes)1200.5STF(L)FAT(UL)1230.5-1200.5=302.4%Cost (Rs.)11011LBT(L)STF(UL)17325-11011=6314 57.3%Waiting time (minutes)2803LBT(L)STF(UL)5302.5-2803= 12500446%trucks13(8+5)or(6+7)STF(L+UL) or FAT(L)LBT(UL)30-13=17130%Table STYLEREF 1 \s ?6. SEQ Table \* ARABIC \s 1 36 Recommended models for loading and unloading four trainsLoading OperationsRecommended ModelSavings Percentage savingsMakespan (minutes)761.5STF770.5-761.5 = 91.18%Cost (Rs.)5604LBT11621-5604 =6017107%Waiting time (minutes)1396.5LBT112232-1396=9836704 %trucks5LBT18-5=13260%Unloading operationMakespan (minutes)760FAT774-760=141.8%Cost (Rs.)8784.5FAT13974-8784.5= 5189.559%Waiting time (minutes)2863FAT11287.5-2863= 8424.5294%trucks7FAT18-7= 11157%Combined operationMakespan (minutes)1521.5STF(L)FAT(UL)1544.5-1521.5=23 1.5%Cost (Rs.)14388.5LBT(L)FAT(UL)25595-14388 =11206 77.8%Waiting time (minutes)4259.5LBT(L)FAT(UL)22520-4259.5 =18260.5 428.7%trucks12(5+7)LBT(L)FAT(UL)36-12=24200%Table STYLEREF 1 \s ?6. SEQ Table \* ARABIC \s 1 37 Computations for savings in cost for one trainSaving per train (Rs.)Daily Saving for 8 trains (Rs)Annual saving (Rs.)Loading61349041789960Unloading58646881711120Combined119995923501080Table STYLEREF 1 \s ?6. SEQ Table \* ARABIC \s 1 38 Computations for time savings for unloading one trainSaving per train (minutes.)Daily Saving for 8 trains(minutes)Annual saving (minutes/day.)Loading75620440=14.2 daysUnloading12.510036500=25.35 daysCombined2216760955=42.33 daysTable STYLEREF 1 \s ?6. SEQ Table \* ARABIC \s 1 39Computations for resource savings for one trainSaving per train (truck)Daily Saving for 8 trainsAnnual saving (truck.)Loading43211680 Unloading43211680Combined86423360Conclusions and future workThis chapter summarises the research reported in this thesis, outlining the limitations of the research and providing recommendations for future research. Containerization of general cargo has been increasing steadily over the last three decades. Starting with 76 million twenty feet equivalent unit (TEU) in year 1988, world container turnover has reached more than 544 Million TEU in year 2008. As a result of the increasing volume of the world container turnover, container terminals have become an important component of the global transportation network. Due to and rising competition, handling an enormous volume of containers speedily and accurately is of paramount importance to a container terminal. To achieve better operations efficiency, a container terminal needs to address the complicated process of transporting containers between various containers handling equipment.The transportation of containers between the quayside and the yard-side can be decomposed into a number of separate sub-processes according to the type of equipment involved. In most container terminals, trucks are commonly used for transporting containers. Determining the sequence of containers to be handled by trucks is one of the major issues in terminal planning. This sequencing decision directly affects the operation efficiency of both the quayside and the yard-side to a large extent. Unnecessary truck waiting times would lead to a longer terminal turnaround time; terminals need to develop optimal truck schedules to ensure a high terminal throughput. Scheduling problems have been studied extensively in the operations research and management science literature but very few studies have been carried out to study scheduling problems of container transporting equipment such as trucks.The research presented in this thesis describes the development and application of models to solve truck scheduling problem that is the problem of scheduling a fleet of trucks to handle a set of non-preemptive jobs with sequence-dependent processing times and different arrival time to minimize the makespan. In this research, development and implementation of several kinds of models for optimal scheduling of loading and unloading operations in container terminals has been presented. A generic model based on mixed integer programming (MIP) has been developed and its effectiveness in scheduling container loading and unloading operations has been studied. In addition to MIP model, four generic models based on different scheduling algorithms have been developed in this research. The performance of these models has been evaluated in terms of the quality of solution achieved by them. Comparison of the performance of MIP model with that of other models has revealed that although MIP model is able to produce optimal solutions but its execution time is quite high. Due to the high execution time requirements, it was concluded that MIP model has limited practical applicability to the real world problems. It was decided to apply greedy algorithm for truck scheduling problem in ICD, Tughlakabad. The main motivation behind using greedy algorithm is that easy to implement in real-world situations because it is highly efficient in terms of time requirements. Following this introduction, section ?7.1 presents the achievements of the research. section ?7.2 describes the limitations and section ?7.3 presents a few pointers towards the future work.Achievement of the thesisThe research presented in this thesis is made up of three distinct parts. The first part of the thesis presents the literature review related to the application of optimization techniques to container terminal operations. Review of container terminal processes has also been presented in the first part of the thesis. In the second part, development of a MIP model has been described. Application of MIP model to a number of container loading and unloading problems has also been described in the second part of the thesis. Finally, development and application of models based on different scheduling mechanisms to several real world problems has been presented. Major achievements of the thesis highlighting the contributions at each stage are presented below.Following the introduction to global and Indian port scenario, chapter 2 of the thesis, presents a review of optimization techniques for improving the efficiency and productivity of container terminals. A review of container terminal processes is also presented in chapter 2 of the thesis. Chapter 3 of the thesis describes the characteristics of the Port of Singapore. The factors that are responsible for making Singapaore the leading port in the world have been discussed. Operations at Container Corporation of India’s ICD at Tughlakabad in New Delhi have been described in chapter 3 of this thesis. Various facilities available at ICD, Tughlakabad have also been described. A summary of control, handling and scheduling operations has been presented in tabular form in chapter 3. It was observed that except for container stock and booking position, none of the operations are scheduled or planned using the real time planning of logistics. Therefore, there is an urgent need to develop models for improving the efficiency of terminal operations in ICD, Tughlakabad.In Chapter 4 of the thesis, formulation of truck dispatching problem has been presented. A generic model based on MIP has been developed using AMPL programming language. Four different problems with combinations of number of trucks and number of trucks were solved using MIP model. It was concluded that the execution time requirements are quite high for problems of larger size. Therefore, application of MIP model to solving real world problems is not practical. In chapter 5 of the thesis, heuristic models based on greedy and reverse greedy algorithms have been described. Four different models based on shortest time first (STF), longest time first (LTF), last busy truck (LBT), and first available truck (FAT) scheduling mechanisms have been developed, and described in this chapter.Application of models based on STF, LTF, LBT, and FAT to four real-world case studies based on the data collected from CONCOR for ICD, Tughlakabad has been described in chapter 6 of the thesis. The data pertaining to job processing and travel times as obtained from CONCOR is presented in tabular form in the chapter. Using the real world data, optimal scheduling of container loading and unloading jobs has been carried out. Comparison of optimal results achieved by each of the four models has also been made. Major achievements of the research carried out in this thesis may be summarized as follows:A comprehensive review of literature related to application of optimization techniques for improving container terminal operations has been carried out with a view to provide ready reference for any future work.A comprehensive review of processes being followed, and equipment being used in container terminals has been carried out in order to put the work carried out in this research in context.Real-world data pertaining to processing time and travel time for each container has been procured from CONCOR, and has been used to test the developed modelsA generic MIP model that is transportable to any other container terminal with minimal changes has been developed for the truck scheduling problemAnalysis of several computational experiments carried out using the MIP model has revealed that the execution time requirements are quite high for solving even moderate size problems, thereby ruling out the application of MIP model to large real-world problemsFour generic models based on STF, LTF, FAT, and LBT scheduling mechanisms have been developed and their practicality in solving complex problems has been demonstrated through application to four real-world problems.It has been demonstrated that the application of recommended models for unloading different number of trains as presented in section REF _Ref233779821 \r \h ?6.7 could lead to substantial savings in the cost of operationsA distinct practical advantage of the model developed in this work are that they are transportable to any other container terminal without any difficultyModels developed in this work can be used by terminal operations managers for optimizing container terminal processesModels recommended in this work provide a wider choice to the terminal managers as well as to customersFinally, implementation of models developed in this work is straightforward due to the ease of interfacingLimitations of the researchThis section presents the limitations of the research presented in this thesis.The location for storing containers in the storage yard has not been taken into account by the models developed in this work. Each container was randomly assigned to a location in the storage yard. The time taken by the yard crane has not been separately considered. Instead, it was included in the travel time of the jobs. To prevent congestion and accidents in the terminal, the speed of each truck was restricted to 15 km/hr. Assigning higher speeds could have led to decrease in the makespan. The capacity of each truck has been assumed to be one container although some trucks could carry two number of TEU containers. Further, due to space limitations each train could carry a maximum 90 TEU containers.Recommendations for further researchTo conclude the thesis, the following recommendations are made for further research which could lead to further improvement in efficiency and productivity in container terminals.In practice, one important issue is how to determine a storage location for each unloading container. In the models described here, the storage location is not considered as a decision variable. Considering storage location as a decision variable is likely to improve the efficiency of terminals but it makes the problem highly complex. Another aspect that could be considered in future work is to identify routes for each truck with the objective to minimize the makespan and at the same time avoid congestion in the terminal. This would lead to decrease in the cost of operations. In this work, the time taken by the yard crane to load and unload the containers was assumed to be included in the travel time. In future work, the time taken by the yard for loading and unloading may be considered separately.References BIBLIOGRAPHY Aarup, M., Zweben, M., & Fox, M. S. (1994). Intelligent scheduling. Toronto, Ont., Canada : Morgan Kaufmann Publishers Inc.Agerschou, H., Lundgren, H., & Sorensen, T. (1983). Planning and Design of Ports and Marine Terminals. New York: Wiley Interscience Publication.Ahuja, R., Magnanti, T., & Orlin, J. (1993). Network Flows : Theory, Algorithms and Applications. New Jersey: Prentice Hall.Alessandri, A., Cervellera, C., Cuneo, M., Gaggero, M., & Soncin, G. (2007a). Nonlinear Predictive Control for the Management of Container Flows in Maritime Intermodal Terminals. ISSIA, Italy: University of Genova, DIPTEM/CNR.Alessandri, A., Sacone, S., & Siri, S. (2007b). Modelling and Optimal Receding-Horizon Control of Maritime Container Terminals. Journal of Mathematical Modelling and Algorithms , 6 (1), 109–133.Ambrosino, D., Sciomachen, A., & S, T. (2006). A Decomposition Heuristics for the Container Ship Stowage Problem. journal of Heuristics , 12 (3), 211-233.AMPL. (2009). A Modeling Language. Retrieved March 22, 2009, from Asef-Vaziri, A., & B, K. (2000). AS/RS in Maritime Container Terminal. Proceedings of the 6th International Colloquium on Material Handling Research. York, PA (USA).Asef-Vaziri, A., Khoshnevis, B., & Parsaei, H. (2003). Potentials for ASRS and AGVS in Maritime Container Terminals. University of Houston.Avriel, M., Penn, M., & Shpirer, N. (2000). Ship Stowage Problem: Complexity and Connection to the Coloring of Circle Graphs. Discrete Applied Mathematics , 103 (1-3), 271-279.Avriel, M., Penn, M., Shpirer, N., & Witteboon, S. (1998). Stowage planning for container ships to reduce the number of shifts. Annals of Operations Research , 76 (0), 55-71.Baird, A. J. (2006). Optimising the container transhipment hub location in northern Europe. Journal of Transport Geography , 14 (3), 195-214.Baker, C. (1998). High Time for Straddles. Cargo Systems , 23-26.Ballis, B., & Abacoumkin, p. (1996). A Container Terminal Simulation Model with Animation Capabilities. Journal of Advanced Transportation , 30 (1), 37-57.Banger, C. M. (2007). Port of India -Future Developments and Challenges. Port and terminal Operations -International Conference. 1, pp. 1-12. Mumbai: Infor-Media India.BARSYL. (2009, January). Balaji Railroad Systems Limited. Retrieved February 11, 2009, from Bulletin 4 ,Containerization Poised for Rapid Growth : , E. (2003). A Multiple-Crane-Constrained Scheduling Problem in a Container Terminal. European Journal of Operational Research , 144 (1), 83-107.Bish, E., Leong, T., Li, C., Ng, J., & Simchi-Levi, D. (2001). Analysis of a New Vehicle Scheduling and Location Problem. Naval Research Logistics , 48 (5), 363 - 385.Bodin, L., Golden, B., Assad, A., & Ball, M. (1983). Routing and scheduling of vehicles and crews: The state of the art. Computer and Operation Reseach , 10 (2), 63-211.Bostel, N., & Dejax, P. (1998). Models and Algorithms for Container Allocation Problems on Trains in a Rapid Transshipment Shunting Yard. Transportation Science , 32 (4), 370-379.Brucker, P., & Kampmeyer, T. (2001). Tabu Search Algorithms for Cyclic Machine Scheduling Problems. Journal of Scheduling , 8 (4), 303-322.Canonaco, P., Legato, P., Mazza, R. M., & Musmann, R. (2007). A Queuing Network Model for the Management of Berth Crane Operations. Computers and Operations Research , 35 (8), 2432-2446.Ceres Paragon, T. B. (2006). Ceres Paragon Terminal: a revolutionary concept. Port Technology International , 30, 121-124.Chen, C., Huang, S.-Y., Hsu, W.-J., Toh, A., & Loh, C. (2003). Platform-based AS/RS for Container Storage. Proceedings of the 2003 IEEE international conference on robotics and automation (pp. 181-187). Taipei: IEEE.Chen, T. (1999). Yard Operations in the Container Terminal–A Study in the Unproductive Moves. Maritime Policy & Management: The flagship journal of international shipping and port research , 26 (1), 27 – 38.Chou, C.-C. (2002). Analysis of container throughput of major ports in Far Eastern region. 12 (59-71).Chung, Y., Randhawa, S., & McDowell, E. (1988). A simulation analysis for a transtainer-based container handling facility. Computers and Industrial Engineering , 14 (2), 113 - 125.CONCOR. (2007). Container Corporation of India, ICD,Tughlakabad. Delhi: Yearbook 2007—ICDs/Dry Ports.CONCOR. (2008). Survey of Containers & Cargo And Container Location& Inventory Updating By Operation of Handheld Terminals. New Delhi: Container Corporation of India Ltd. TKD (A Govt. of India Undertaking).Cools, J. (2005, September). cargo-containers. Retrieved December 23, 2005, from , J., G, L., P, L., & Moccia, L. (2005). Models and Tabu Search Heuristics for the Berth-Allocation Problem. Transportation science , 39 (4), 526-538.Corp, K. V. (2007). Ship-to-Shore gantry cranes. Retrieved May 4, 2007, from brochures/sts_low.pdfDaganzo, C. F. (1989b). Crane Productivity and Ship Delay in Ports. Transportation Research Board (1251), 1-9.Daganzo, C. (1989a). The crane scheduling problem. Transportation Research Part B: Methodological , 23 (3), 159-175.De Castilho, B., & Daganzo, C. (1993). Handling strategies for import containers at marine terminals. Transportation Research Part B: Methodological. , 27, 151-166.Dekker, R., Voogd, P., & Van, A. E. (2006). Avanced Methods for Container Stacking. OR Spectrum , 28 (4), 563-586.Design, A. (2005). Ablaze Development Corporation (ABLAZE), GRAIL A,utomated Container Terminal. Retrieved October 21, 2005, from , B., & Spasovic, L. N. (2005). Analysis of Applicability of Innovative Systems for Transport of Marine Containers. Annual Forum Program and Proceedings. Washington: Transportation Research Forum.Dirk, K., Sefan, V., & Robert, S. (2004). Container Terminal Operation and Operation Research- A Classification and literature Review. OR Spectrum , 26 (1), 3-49.Dougherty, E. (2008). GRAIL Auromated Overhead Automated Container Terminal. In Ioannou P.A., Intelligent Freight Transportation (pp. 39-40). CRC Press.Drewry. (2007b). Dewry Corporation, Shipping Report. Retrieved December 4, 2007, from shipping: . (2007a). Drewry Coperation, Global Terminal Operation Report. Retrieved October 12, 2007, from Hafan-Hamburg: Shipping Consultants. (2007). Annual Container Market. UNCTAD.Dubini, G. (2007). Optimising the efficiency of automated container lifting and handling systems. Port Technology International , 31, 100-102.Edmond, E. D., & Maggs, R. P. (1978). How Useful are Queue Models in Port Investment Decisions for Container Berths? Journal of Operations research Society , 29 (8), 741–750.Edmonds, J. (1971). Matroids and the Greedy Algorithm. Mathematical Programming , 1 (1), 127-136.Egbelu, P. T. (1984). Characterization of Automatic Guided Vehicle Dispatching Rules. International Journal of production Research , 22 (3), 22(3),359-374.Etzelmueller, R. (2006, October 16). European Ports are Hot Propertes for Hungry. Retrieved March 12, 2007, from Standard and Poors: , J. M., & Koppers, S. J. (1996). Automated Guided vehicle Traffic Control at a Container Terminal. Transportation Research , 30 (1), 21-34.Froyland, G., Koch, T., Megow, N., Duane, E., & Wren, H. (2008). Optimizing the landside operation of a container terminal. OR Spectrum , 30 (1), 53-75.Gambardella, L., & Rizzoli, A. Z. (1998). Simulation and Planning of an Intermodal Container Terminal. Simulation , 71 (2), 107-116.Gillett, B. E., & Miller, L. R. (1974). A Heuristic Algorithm for the Vehicle-Dispatch Problem. Operational Research , 22 (2), 340-349.Goodchild, A. V., & Daganzo, C. F. (2005). Crane Double Cycling in Container Ports: Effect on Ship Dwell Time. Berkeley: Institute of Transportation Studies ,University of California .Goodchild, A., & Daganzo, C. (2004). Double-Cycling Strategies for Container Ships and Their Effect on Ship Loading and Unloading Operations. Transportation Science , 40 (4), 473–483.Günther, H.-O. a. (2005). Container terminals and automated transport systems. Berlin: Springer.Hax, A., & Candea.D. (1984). Production and Inventory Management. New Jersey: Prentice-Hall,Enlewood Cliffs.Henesey, L. (2006). Multi-Agent Container Terminal Management. Karlshamn: Blekinge Institute of Technology.Heydenreich, B., & Mishra D, M. R. (2008). Optimal Mechanisms for Scheduling Jobs on a Single Machine. In Internet and Network Economics (pp. 414-425). Springer Berlin / Heidelberg.Holguin, J., & Jara-Diaz, S. (1998). Practical Implications of Optimal Space Allocation and Pricing. Ports 98. 1, pp. 89-97. Long Beach, California: Michael Kraman.Imai, A., Nagaiwa, K., & Tat, C. (1997). Efficient Planning of Berth Allocation for Container Terminals in Asia. Journal of Advanced Transportation , 33 (1), 75-94.Imai, A., Nishimura, H., & Papadimitriou, S. (2001). The dynamic berth allocation problem for a container port. Transportation research part B , 35 (4), 401-417.Imai, A., Sasaki, K., Nishimura, E., & Papadimitriou, S. (2004). Multi-Objective Simultaneous Stowage and Load Planning for a Container Ship with Container Rehandle in Yard Stacks. European Journal of Operational Research , 171 (2), 373-389.Ioannou, E. B., Kosmatopoulos, J. H., Collinge, A., Liu, C. I., & Asef-Vaziri., A. (2000). Cargo Handling Technologies. Los Angeles, California: University of Southern California Center for Advanced Transportation Technologies.Ioannou, P. A., Jula, H., Liu, C. I., Vukadinovic, K., & Pourmohammadi, H. (2001). Advanced Material Handling: Automated Guided Vehicles in Agile Ports. California: Center for Advanced Transportation Technologies University of Southern California.Jinxin, C., SHI, Q., & Lee, D.-H. (2008). A Decision Support Method for Truck Scheduling and Storage Allocation Problem at Container. Tsinghua Science and Technology , 15 (51), 211-216.Kalmar. (2006). Kalmar Industries Corporate. Retrieved May 18, 2006, from , J.-H. (2006). Inegreated International Transport and Logistics System for North-East Asia. New York: United Nations, ESCAP, Korea Transport Institute.Khanna, K. K. (2005). Intermodal Transportation. In Physical Distribution Management: Logistical Approach (pp. 349-377). Delhi: Himalaya Publishing House.Khoshnevis, B., & Asef-Vaziri, A. (2000). 3D Virtual and Physical Simulation of Automated Container Terminal and Analysis of impact on In Land Transportation. Los Angeles, US,: Metrans Transportation Center.khuller, S., Baghavachari, B., & Young, N. e. (2007). Greedy Method. In T. F. Gonzalez, Handbook of approximation algorithms and metaheurististics. Boca Raton : CRC Press.Kim, D. (2006). INS-Aided RTK GPS System for ALV at the Container Handling Port. University of New Brunsswick: Seoho Electrical Co.Ltd.Kim, H. K., & Bae, W. J. (2004). A Look-Ahead Dispatching Method for Automated Guided Vehicles in Automated Port Container Terminals. Transportation Science. v38 i2. 224-234 , 38 (2), 224-234.Kim, K. H., & Bae, J. W. (1999a). A Dispatching Method for Automated Guided Vehicles to Minimize Delay of Containership Operations. International Journal of Mangement Science , 5 (1), 1-25.Kim, K. Y., & Kim, K. H. (1999c). A Routing Algorithm for a Single Straddle Carrier to Load Export Containers onto a Containership. International journal of production economics, , 59 (1-3), 425-433.Kim, K., & Kim, K. (1999b). An Optimal Routing Algorithm for a Transfer Crane in Port Container Terminals. Transportation Science , 33 (1), 17-33.Kim, K., & Kim, K. (1999d). Segregating Space Allocation Models for Container Inventories in Port Container Terminals. International Journal of Production Economics , 59 (1-3), 415-423.Kim, K., Park, Y., & Ryu, K. (2000). Deriving Decision Rules to Locate Export Containers in Container Yards. European Journal of Operational Research , 124 (1), 89-101.Kleinberg, J., & Tardos, E. (2005). Greedy Algorithm. In J. Kleinberg, Algorithm Design. Addison-Wesley.Kozan, E. (1997b). Comparison of Analytical and Simulation Planning Models of Seaport Container Terminals. Transportation planning and Technology , 20 (3), 235 – 248.Kozan, E. (1997a). Increasing the operational efficiency of container terminals in Australia. Journal of the Operational Research Society , 48 (2), 151-161.Kozan, E. (2000). Optimising Container Transfers at Multimodal Terminals. Mathematical and Computer Modelling, , 31 (10), 235-243.Kozen, E. (1997). Comparison of Analytical and Simulation Planning Models of Seaport Container Terminal. Transportation Planning and Technology , 20 (3), 235-248.KPMG. (2006). Indian Martime Landscape. New Delhi: Confederation of Indian Industry.KPMG. (2007). International Railway Conference. New Delhi: Confederation of Indian Industry.Lahiri, A. K. (2006, December 31). Fact Sheet 2007. Retrieved November 20, 2008, from Asian Developing Bank and India: Documents/Books/ADO/2007/IND.pdfLawler, E. L., & Wood, D. E. (1966). Branch-and-Bound Methods: A survey. Operation Reseach , 14 (4), 699-719.Lawler, E. L., Lenstra, J. K., Rinnooy, K. A., & Shmoys, D. B. (1993). Sequencing and scheduling: algorithms and complexity. In S. C. Graves, K. A. Rinnooy, & P. H. Zipkin, Handbooks in Operations Research and Management Science, Volume 4: Logistics of Production and Inventory (pp. 445-508). North-Holland, Amsterdam.: Elsevier Science.Lee, L., Chewn, E., Tan, K., & Han, Y. (2006). An Optimization Model for Storage Yard Management in Transhipment Hubs. OR Spectrum , 28 (4), 539-561.Lee, T., Park, N., & Lee, D. (2003). A simulation study for the logistics planning of a container terminal in view of SCM. Maritime Policy & Management: , 30 (3), 243-254.Legato, P., & Mazza, R. M. (2001). Berth Planning and Resources Optimisation at a Container Terminal via discrete event simulation. European Journal of Operational Research , 133 (3), 537-547.Li, C.-L., & Vairaktarakis, G. L. (2004). Loading and unloading operations in container terminals. IIE Transactions , 36 (4), 287-297.Linhua Jiang, K. I. (2009). AMP User Manual. Netherelands: Leiden University.Linn, R., & Zhang, C. (2003). A heuristic for Dynamic Yard Crane Deployment in a Container Terminal. IIE Transactions , 35 (2), 161-174.Liu, B. (2002). Theory and practice of uncertain programming. Heidelberg, Germany: Springer.Liu, C. I., Jula, H., & Ioannou, P. A. (2002). Design Simulation and Evaluation of Automated Container Terminals. IEEE Transactions on Intelligent Transportation Systems , 3 (1), 12-26.Liu, C. I., Jula, H., Vukadinovic, K., & Ioannou, P. (2004). Automated Guided Vehicle System for Two Container Yard Layouts. Transportation Research Part C: Emerging Technologies , 12 (5), 349-368.Ludwik, K. J. (1990). Simulation methodology for intermodal freight transportation terminals. Simulation , 55 (1), 49-57.Meersmans, P. J. (2002). Optimization of Cntainer Handling System . Erasmus University Rotterdam: Tinbergen Institute Research Series .Metropolis, N., & Ulam, S. (1949). The Monte Carlo Method. Journal of The Americal Statistcal Association , 44 (247), 264-275.Murty, K. G., Chiu, H. C., Liu, J., Tseng, M. M., Leung, E., & Lai, K. K. (2005b). Hong Kong International Terminals Gains Elastic Capacity Using a Data-Intensive Decision-Support System. Interfaces , 35 (1), 61-75.Murty, K. G., Liu, J., Wan, Y. W., & Linn, R. (2005a). A Decision Support System for Operations in a Container Terminal. Decision Support Systems , 39 (3), 309-332.Narasimhan, A., & Palekar, U. S. (2002). Analysis and algorithms for the transtrainer routing problem in container port operations. Transportation Science , 36 (1), 63-78.Nevins, M. R., Macal, C., & Joines, J. (1998). A Discrete-Event simulation Model for Seaport Operations. Simulation , 70 (4), 213-223.Ng, W. (2005). Crane scheduling in container yards with inter-crane interference. European Journal of Operational Research , 164 (1), 64-78.Ng, W., & Mak, K. (2005). Yard crane scheduling in port container Terminal. Applied mathematical modelling , 29 (3), 263-276.Nguyen, V., & Kim, K. (2009). A dispatching method for automated lifting vehicles in automated port container terminals. Computers and Industrial Engineering, , 56 (3), 1002-1020.Nicolau, S. N. (1967). Berth planning by evaluation of congestion and cost. Journal of the Waterways and Harbors Division , 93 (4), 107-132.Nishimura N, I. A. (2005). Yard trailer routing at a maritime container terminal. Transportation Research Part E: Logistics and Transportation Review , 41 (1), 53-76.Nishimura, E., Imai, A., & Papadimitriou, S. (2001). Berth Allocation Planning in the Public Berth System by Genetic Algorithms. European Journal of Operational Research , 131 (2), 282-292.Nishimura, N., Imai, A., & Papadimitriou, S. (2005). Yard trailer routing at a maritime container terminal. Transportation Research Part E: Logistics and Transportation Review , 41 (1), 53-76.Noam Nisan, T. R. (2007). Algorithmic game theory. Cambridge: Cambridge University Press.Noell. (2006). Noell Crane System. Retrieved May 18, 2006, from Noell, Power with care: , J., & Rommert, D. (2001). Operation Research Support Container Terminal. Rotterdam: Econometric Institute Report.Petering, M. (2007). Design, Analysis, and Real-Time Control of Material Handling Systems in Container Terminals. Ph.D. dissertation, University of Michigan,, IOE Department, Ann Arbor.Petering, M., & Murty, K. (2006). Simulation Analysis of Algorithms for Container Storage and Yard Crane Scheduling at a Container Terminal. The Second International Intelligent Logistics Systems Conference. Brisbane, Australia: the Australian Society for Operations Research Inc.Peterkofsky, R. J., & Daganzo, C. F. (1990). A Branch and Bound Solution Method for the Crane Scheduling Problem. Transportation Research Part B: Methodological , 24 (3), 159-172.Prasad, L. (2005, Fevruary 26). Introducing the Railway Budget 2005-2006 , Container Traffic.PTI. (2006). The Online Journal of Advanced Technologies for Ports and terminals. Retrieved May 23, 2006, from , G. R. (2007). Containerization – Building Global Trade Competitiveness. Ahmedabad: Indian Institute of Management.Rajotia, S., Shanker, K., & Batra, J. (2002). Determination of optimal AGV fleet size for an FMS. International Jorunal of Production Research , 36 (5), 1177-1198.Ramani, K. (1996). An Interactive Simulation Model for the Logistics Planning of Container Operations in Seaports. Simulation , 66 (5), 291-300.Rath, E. (1973). Container Systems. New York: Wiley Interscience publication.Ravi. (2007). Indian Martime 2007-Prospective Insight of the Shipping Industry. Shipping Today , 1 (17), 06.Rose, O. (2001). The Shortest Processing Time First (SPTF) Dispatch Rule and Some Variants in Semiconductor Manufacturing. the 2001 Winter Simulation Conference, (pp. 1220-1224). Arlington, VA, USA.Russell, S. J., & Norvig, P. (2003). Arteficial Intelligence: A Modern Approach,(2nd edition). New Jersey: Prentice Hall.Sabonge, R. (2006). Expanding Capacity of The Panama Chanal. TRB Summer Conference (pp. 1-32). California: TCP.Sciomachen, A., & Tanfani, E. (2006). A 3D-BPP approach for optimizing stowage plans and terminal productivity. European Journal of Operation Research , 183 (3), 1433-1446.Shields, J. (1984). Container Stowage: A Computer Aided Pre-planning System. Marine Technology , 21 (4), 370-382.Siemens, A. G. (2007b). Siemens—crane solutions—ports & terminals—rail mounted gantry (RMG) cranes. Retrieved December 21, 2007, from /en/c5eb153b-a15e-11d7-b54c-0050da4caaa9/index.aspx.Siemens, A. G. (2007c). Siemens—crane solutions—ports & terminals—rubber tired gantry (RTG) cranes. Retrieved December 21, 2007, from cranes/en/c5eb153a-a15e-11d7-b54c-0050da4caaa9/index.aspx.Siemens, A. G. (2007a). Siemens—crane solutions—ports and terminals—straddle carrier. Retrieved December 21, 2007, from b54c-0050da4caaa9/index.aspx.Silberholz, M., Golden, B., & Baher, E. (1991). Using Simulation to Study the Impact of Work Rules on Productivity at Marine Container Terminal. Computer and Operation Research , 18 (5), 433-452.Singapore Department of Statistics. (2007, August). Yearbook of Statistics Singapore. Retrieved November 23, 2007, from Ministry of Trade and Industry: Port. (2009). Container Throughput. Retrieved March 23, 2009, from Maritime and Port Authority of Singapore (MPAS): , A., & Ferreira, L. (2005). Multi-Objective Evaluation of Intermodal Freight Terminal Location Decisions. Proceedings of the 27th Conference of Australian Institute of Transport Research (CAITR) (pp. 1-16). Brisbane: Queensland University of Technology (QUT),.Steenken, D. (1992). Fahrwegoptimierung am Containerterminal unter Echtzeitbedingungen. OR Spectrum , 14 (3), 161– 168.Steenken, D., Henning, A., Freigang, S., & Vo?, S. (1993). Routing of Straddle Carriers at a Container Terminal with the Special Aspect of Internal Moves. OR Spectrum , 15 (3), 167-172.Steenken, D., Voss, S., & Stahlbock, R. (2004). Container terminal operation and operations research - a classification and literature review. OR Specturm , 26 (1), 3-49.Taleb-Ibrahimi, M., De Castilho, B., & Daganzo, C. (1993). Storage space vs handling work in container terminals. Transportation Research Part B: Methodological , 27, 13-32.Taniguchi, E., Thompson, R., Yamada, T., & Duin, R. (2001). City Logistics: Network Modelling and Intelligent Transport Systems. Oxford, UK: Pergamon, Elsevier Science Ltd.Van Hee, K., & Wijbrands, R. (1988). Decision Support System for Container Terminal Planning. European Journal of Operational Research , 34 (3), 262-272.Van Horssen, W. (1996). The trouble with growth. Cargo Systems , 51-52.Vis, I. A., & De Koster, R. (2003). Transshipment of Containers at a Container Terminal: an Overview. European Journal of Operational Research , 147 (1), 1-16.Vis, I., De Koster, R., Roodbergen, K., & Peeters, L. (2001). Determination of the Number of Automated Guided Vehicles Required at a Semi-Automated Container Terminal. Journal of the Operational Research Society , 52 (4), 409-417.Vos, R. (2008, October 22-24). LINK Global Economic Outlook. Retrieved November 08, 2008, from United Nations ,Department of Economic and Social Affairs, Expert Group Meeting on the World Economy (Project LINK): , I. D., & Roach, P. A. (2000). Container Stowage Planning: A Methodology for Generating Computerised Solutions. Journal of the Operational Research Society , 51 (11), 1248-1255.World Bank. (2007). World Development Indicators. Washinton: World Bank.Yearbook. (2005). Containerisation International Yearbook 2005. London: Informa UK Ltd.Yun, W., & Choi, Y. (1999). A Simulation Model for Container-Terminal Operation Analysis using an Object-Oriented Approach. International Journal of Production Economics , 59 (1-3), 221-230.Zeng, Q., & Yang, Z. (2009). Integrating simulation and optimization to schedule loading operations in container terminals. Computers and Operations Research , 36 (6), 1935-1944.Zhang, L. W., Ye, R., & Huang, S.-Y. (2005). Mixed Integer Programming Models for Dispatching Vehicles at a Container Terminal. Journal of Applied Mathematics and Computing , 17 (1-2), 145-170.ZMPC. (2007c). Product Introduction–Quayside Container Cranes–Twin 40ft Double Trolley Quayside Container Crane. Retrieved December 23, 2007, from Shanghai Zhenhua Port Machinery Co. Ltd: . (2007b). Product Introduction–Quayside Container Cranes–Twin 40’ Quayside Container Crane. Retrieved December 23, 2007, from Shanghai Zhenhua Port Machinary Co.Ltd: . (2006). Shanghai Zhenhua Heavy Industry Co .Ltd.,. Retrieved May 22, 2006, from Port and services: . (2007a). Product introduction–quayside container cranes–double trolley quayside container crane. Retrieved December 23, 2007, from Shanghai Zhenhua Port Machinery Co.Ltd: AGlossary of container terminal terms used in this thesisAdaptability: capacity of CT operators to implement solutions, i.e., changes to shipping line schedules and fulfil other customer requirements.Automated Guided Vehicle (AGV): is a mobile robot used highly in industrial applications, such as container terminal to move containers from point to point.Berth: location in which ship is docked alongside a Quay to be loaded o unloaded at a Container Terminal. Berth Assignment or Berth Assignment Plan: a document describing which Berth and machines are to be assigned to a specific Ship. This decision is based on Ship line schedule (Ship Data), Bay plan (no. of Containers to be loaded/unloaded), Contracts, Berth Availability and Resource Availability.Bulk Cargo: is homogeneous unpacked cargo such as grain, coal or sugar.Chassis: A frame with wheels and container locking devices to secure the container for movement.Container Capacity: is used to determine the number of containers that can be handled with the current resources for the year (for a Port or Terminal).Container freight station (CFS) A dedicated port or container terminal area, usually consisting of one or more sheds or warehouses and uncovered storage areas where cargo is loaded (“stuffed”) into or unloaded(“stripped”) from containers and may be temporarily stored in the sheds or warehouses.Containerisation International (CI) magazine: is the premier source of high-level industry intelligence for the container industry.Customhouse: A government office where duties are paid, documents filed, and so forth, on foreign shipments.Demurrage: A penalty charge against shippers or consignees for delaying the carrier’s equipment beyond the allowed free time.Dispatching: A method of generating scheduling in job shops whereby the decision about which job to progress next is made using simple priority rules whenever the workstation becomes available for further processing Dry Port: a facility located in the hinterland or away from a body of water and operates many of the activities associated with a traditional port or terminal, such as: stripping and stuffing containers; receiving and dispatching goods and containers, temporary storage for an arriving ship, etc.Dwell Time: time that a container waits in a terminal to be loaded or unloaded onto another mode of transport. Gantry crane :A crane fixed on a frame or structure spanning an intervening space typically designed to traverse fixed structures such as cargo (container) storage areas or quays and which is used to hoist containers or other cargo in and out of vessels and place or lift from a vessel, barge, trucks, chassis, or train.Heavy lift charge: A charge typically imposed when special lifting gear is required to handle a given piece of cargo, which may be of either heavy weight or of large dimensions (often referred to as “out of gauge” when dealing with container vessels).Inland Container Depot is an organisation offering a total package of activities to handle and control container and general cargo flows between road, rail and waterways, and vice versa, resulting in maximum service for inland transportation at minimum costs.Inland Container Depots: are interfaces between connecting modes of transportation. Intermodal container terminal is a terminal where containers enter and leave by multiple means of transport, as trucks, trains, air cargoes and vessels (I/O transport means).Operating Cost: Cost per time period for operating a piece of equipment, such as a Quay Crane, a ship, Straddle Carrier, Yard Crane, etc.Pallet :A flat tray, generally made of wood, but occasionally steel or other materials, on which goods can be stacked. There are two principal sizes: the ISO pallet, which measures 1 x 1.2 meters, and the euro pallet at 0.8 x 1.2 meters.Priority sequencing rules: the rules that specify the job processing sequence when several jobs are waiting in line at workstationRail-mounted gantry (RMG): Rail-mounted gantry crane used for container acceptance, delivery, and stacking operations in a container yard.Service Time: time that ship is served may include down (time that is non productive stop time for lunch, maintenance, etc.Spreader: A piece of equipment designed to lift containers by their corner castings.Stack: physical arrangement of containers assigned according to yard layout.Stevedoring charges: Fees for loading and stowing or unloading a ship.Stowage: The method of placing cargo into a single hold or compartment of a ship to prevent damage, shifting, etcStraddle carrier: Type of equipment that picks up and transports containers between its legs for movement within a container terminal.Terminal handling charge (THC): A charge made for a service performed in a terminal area typically referring to handling associated with receipt, delivery, or inspection of cargo via land-based operations.Terminal productivity : deals with the efficient use of labour, equipment and land. A means of quantifying the efficiency of the use of these resources. Limits on the productivity of a container terminal may be imposed by either physical or institutional factors or a combination of both. Twenty-foot Equivalent Unit (TEU) container size standard of twenty feet. Two twenty-foot containers (TEUs) equals one FEU. Container capacity is often measured based on TEU as well as container port or terminal throughput capacity.Tired mounted gantry (RTG) :Gantry crane on rubber tires typically used for acceptance, delivery, and container stacking at a container yard.Turnaround time: the time it takes between the arrival of the vessel or train and its departure.Yard Location: a cell in a container stack according to Container Characteristics. There are several types of Stacks, for example a hazardous stack or reefer stack, etc.Note: Compiled from various sources: UNCTAD, Interviews, Webster’s Dictionary, Chapman’s Seaman’s dictionary, various trade and industry brochures and BTable B1 - Technical information of TMGC used in CONCORProject No :K100-K1031-General Crane Specifications Rated load40 tonnesWidth(mm)7+1 containers (27000 mm)Height (mm)4+1 Containers (15240 mm)Container Range20’ & 40’ retractable flipper2-Speed Main Hoist20 m/min (40 Ton)40 m/min (empty spreader)Trolley75 m/minGantry90 m/min3-Electrical Equipment Control Voltage220 VACMain Voltage415 VAC, 50 HzTable B2 - Technical Information of RMGC used at CONCORProject NO: K 063 FELS1-Lifting capacity Rated load under spreader40 tonnesLift height9.5 mSpan22.5 mOutreach from Rails (both sides)72-Speed Main Hoist20 m/min (40 Ton)40 m/min (empty spreader)Trolley75 m/minGantry90 m/min with empty spreader25 m/min with rated load3-Electrical Equipment Control Voltage230 VACMain Voltage480 VAC, 50 HzBoard Particulars of Bogie Container Flat WagonThe design of the wagon has been optimised to achieve lower tare weight, thereby having a higher payload.The wagon has been designed for transportation of 2896mm(9’-6”) high series I ISD containers at operating speed of 100 kmph.The wagon is provided with single pipe gradable release Airbrake System with two stage automatic load sensing advice and wheel type hand brake.The wagon loaded with 2896mm (9’-6”) high ISO Containers when standing on straight and level track is within the maximum moving dimensions of standard class locomotives. Table B3 - Examples of CT operating systems and land used per annumOperating 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 –manufacturing steel boom with high intensityTerminal retaining the equipmentCONCOR-TKDNew DelhiECT/DSL,Thames portHHLASingapore (PPT)Appendix C Code for Mathematical Model using AMPL softwareparam 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 DCode for Greedy Algorithm Based Model/***************************************************************//* Final Code for Greedy Algorithm as on May 2007*/#include <stdio.h>#include <stdlib.h>#include <math.h>#include <string.h>#include <iostream.h>include <CONIO.h>#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 linkbetween 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]<a) {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 herefor(jj = (Ntrucks + 1); jj <= Njobs; jj++) {CurMin=x[1];//previous minimum arrival timeCurMin = x[1];truckAvail[jj] = y[1];PreMin=0;//previous maximum departure time for(int kk=1 ;kk<jj;kk++){//printf("\ntruck[%d]=%d \n",kk,truckAvail[kk]); if (PreMin<Tdep[kk][truckAvail[kk]]) PreMin=Tdep[kk][truckAvail[kk]];}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 resultsprintf("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 <stdio.h>#include <stdlib.h>#include <math.h>#include <string.h>#include <iostream.h>#include "rvector.cpp"const unsigned STR_SIZE = 25;//no. of characters in filenamesconst unsigned ARRAY_SIZE = 10; //depends upon number of filesvoid 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]<a) {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 costfloat truckCost2 = 4; //per truck costfloat 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 orderjj=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 indexii=Njobs+1;for(jj = 1; jj <= Njobs; jj++) {ii=ii-1;revindex[ii]=jj;}printf("After reversing \n");printf("jobs truck availableArrival time Departure time\n");for(ii = 1; ii <= Njobs; ii++) {kk = revindex[ii];}// calculate number of trips for each truckjobByTruck = 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 jobArrival 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 timespiksr2(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 algorithmtt=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("JobArrTime 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 algorithmGreedy Algorithm: first loop (i=1 to Ntrucks) complexity=NtrucksSecond 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 functionComplexity is the same for reverse greedy StartInput Njobs, Ntrucks, si ,diAssign job i to available truck ii<=Ntrucksi=1Ouput resultsCalculate Tdi,Tai, Wii=Ntrucks+1i<=Njobsk<=iAssign job i to available truckavial Calculate Tdi,Tai, WiEndCalculate truckavial k=1Appendix EList of publications1. 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, 20052. 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 – 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. ................
................

In order to avoid copyright disputes, this page is only a partial summary.

Google Online Preview   Download