Problems And Algorithms For Booking Air Cargo Terminal Handling Platform

This paper studies the real problems in modern service industry of booking system. The on-line scheduling problem of jobs with order arrival time is based on the handing platform of air cargo terminal. Firstly,we consider the on-line booking problems of single task on handing platform and a special situation of this problem. Secondly, we consider the on-line booking problems of multi-tasks on handing platform that both of flow shop and open shop. We put forward the greedy algorithm for above three problems. The idea of the greedy algorithm is that the next order will be received after the time that the task is arranged processing immediately when the order contains task information arrives the system. We analyze the performance of the greedy algorithm for these three problems, and we get the following conclusions:(1) The on-line booking problems of single task on handing platform are modeled as the on-line one-machine scheduling problems of independent jobs with arbitrary order arrival time and job release time to minimize makespan. The competitive ratio for the greedy algorithm for the above problems is 2, and it can be reduced to 3/2 if every job has same processing time.(2) The on-line booking problems of flow shop task are modeled as the on-line two-machine flow shop scheduling problems of independent jobs with arbitrary order arrival time and job release time to minimize makespan.The competitive ratio for the greedy algorithm for the above problems is 2.(3) The on-line booking problems of open shop task are modeled as the on-line two-machine open shop scheduling problems of independent jobs with arbitrary order arrival time and job release times to minimize makespan. According to analyzing the case of the processing job on two machines, we can get some properties of idle processing intervals on two machines. As this point, we classify three cases to prove that the competitive ratio for the greedy algorithm for the on-line two-machine open shop scheduling problems of independent jobs with arbitrary order arrival time and job release time to minimize makespan is 2.Lastly, we analyze the practical application of the on-line greedy algorithm through two examples.The algorithm of this paper can get the actual delivery time of every shipping agent. It not only helps the shipping agent to reduce the waiting time, but also adjusts busy degree of air cargo terminal effectively.