Study Of Online Berth And Quay Crane Integrated Allocation In Container Terminals

In response to the decline punctuality rate of real-time ships in the container terminal, managers need to schedule and dispatch those real-time vessels, one of the key problems in improving service efficiency of terminal resources is to make and fulfill a flexible and reliable service schedule for arrive vessels. In view of the above situation of real-time ships in the container terminal, use competitive analysis to analyze the performance of online algorithms for the model of berth and quay crane integrated allocation in container terminals, and to construct the corresponding online scheduling model. This article broke the existing research which design of complex heuristics ideas of the current problem, and designs online scheduling strategy, and use the competitive ratio to measure the performance of its execution effect.We consider a hybrid berth which consists of three adjacent small berths, this paper has carried on the thorough analysis to the kinds of situations, which are both predictable and unpredictable. For the real-time requests are to be released over list at zero time which arriving one by one. On the release of each request, a scheduler has to decide immediately its service resource combination, the special berth allocation and QCs. The objective is to minimize the makespan or the completion time of the last completed request. The scheduling model is established by the different look-ahead ability for the subsequent requests. For some cases, the optimal online scheduling strategies are given; for the other situations, the online competitive strategy is also given, which are similar to the upper and lower bounds of the competitive ratios. The main work and innovative points are as follows:(1)In the first part, we study an online over-list model of berth and quay crane integrated allocation in container terminals without look-ahead, aiming at minimizing the maximum completion time of container vessel. We focus on the scenario with small numbers of berths and cranes. For the setting with three berths, we prove matching upper and lower bounds of 5/4, 4/3 and 3/2 for the cases with 4, 5 and 6 cranes, respectively. We can show that the algorithms we proposed are optimal in the sense that their competitive ratios match the lower bounds.(2)In the second part, we present an online over-list model of berth and quay crane integrated allocation in the scenario with a 1-lookahead ability. Given that an online algorithm can only foresee the next one vessel request on the release of each request, we propose three online algorithms which are optimally(√2+1)/2, 5/4 and 4/3-competitive for the three cases with 4, 5 and 6 cranes respectively.Combined with the corresponding conclusions without look-ahead, and thus reveal the positive effect of the look-ahead function.(3)In the last part, we study an online over-list model of berth and quay crane integrated allocation in the scenario with k-lookahead ability such that the next k ≥ 2 requests are foreseen on the release of any request. First,for the case of with k-lookahead ability, one main result is a lower bound is close to 1 of competitive ratio for deterministic online strategies with the increase of look-ahead ability for 4 cranes, we further give lower bounds of 25/21 and 9/7 respectively for 5 and 6 cranes. Second, We propose a 9/8,6/5 and 9/7-competitive algorithm for the case with 4,5 and 6 cranes with 2-lookahead ability, respectively. For the case with 6 cranes, the above results reveal that any larger look-ahead ability cannot further improve the competitive performance of online strategies.