Flow Shop Scheduling Optimization With Overlapping Operations For Quay Cranes In Container Terminals

Job overlapping is common in optimizing the flexibility of operations and the schedul-ing performance in practical flexible manufacturing industries and distributed computing sys-tems. Overlapping operations exert great influence on effectiveness and efficiency of flow shop scheduling optimizations in real applications, such as container terminals. Both the theoretical analysis and the methods are of significance.This dissertation focuses on the flow shop scheduling problem with overlapping opera-tions to minimize makespan. By analyzing the characteristics of overlapping operations, greedy heuristics are proposed to eliminate gaps for workload allocations. The theoretical work and methods on the considered problem could be applied to several background applications, such as the dual cycling quay crane scheduling problem and double girder bridge crane scheduling with dual cycling. The main contributions of this dissertation are summarized as follows.(1) The new flow shop scheduling problem with overlapping operations is proposed and re-garded as a new combinational optimization problem. Using mixed integer programming, a model with the objective to minimizing makespan is established. The makespan is calcu-lated by a generalized formulation, which could be extended to other problems with over-laps. The considered problem is solved in two phases:the workload allocation for over-lapping operations and the job sequencing. The workload allocation is the critical issue accounting for the NP-complete nature of this problem, and the complexity of workload allocation stems from the gaps between two machines. Greedy heuristics are developed to eliminate gaps for workload allocation, along which an optimal sequencing rule is pre-sented. Six Greedy Heuristics are proposed. Essentially, initial solutions are constructed by three strategies, followed by two improvement heuristics, and then tweaked by perturbation to restart searching. Experimental results illustrate that:(i) Overlaps greatly improve the effectiveness and efficiency of the flow shop schedule, (ii) Workload allocation for over-lapping operations adjusts the overlap for each job to improve the makespan. (iii) All six algorithms significantly outperform the existing scheduling methods.(2) The dual cycling quay crane scheduling problem is considered with hatches to minimize the operation cycles of quay cranes. According to the research on the flow shop scheduling with overlapping operations, this problem is decomposed into two subproblems:intra-group stage (sequencing stacks within each hatch) and inter-group stage (scheduling all hatches). A new stack sequencing method is constructed for stacks within each hatch, which is modeled as a two machine non-permutation flow shop scheduling problem. By removing inner gaps using left-shifting, the adapted hatch scheduling subproblem is modeled as a two machine grouped flow shop scheduling problem, which contains more precise processing times. A composite heuristic is proposed for dual cycling quay crane scheduling problem. Based on the derived lower bound, the heuristic is compared with the best existing heuristics on a large number of instances. Experimental results illustrate that the proposal outperforms the existing methods on all instances. It is also demonstrated that dual cycling needs much less quay crane operating cycles than single cycling.(3) A novel quay crane design, double girder bridge crane (DGBC) is introduced to improve the crane efficiency. Under the control of one driver, DGBC is capable of handling containers of two adjacent bays simultaneously, avoiding crane collisions, saving travelling and repo-sition cost, and eventually improving terminal efficiency. This problem is formulated as a resource-constrained project scheduling with objective to minimize the maximum comple-tion time, it equals to the maximum between the makespan of two bays. A two-stage heuris-tic algorithm is presented in which an operating sequence on each bay is obtained by dual cycling, and an integrated timetable is constructed for both bays. Three kinds of resource conflicts in the timetable are removed by the proposed minimum cost strategy. The effec-tiveness of dual cycling on DGBC is well examined. A case study is presented to illustrate how DGBC works with the proposed two-stage scheduling method. Three extreme cases with respective conflict types are investigated to develop the bounds for the performance of DGBC with dual cycling. The results show that DGBC greatly improves the terminal pro-ductivity, and outperforms the traditional single girder crane in both makespan and the lift operation percentage. In additions, the highest DGBC efficiency does not require the max-imum double cycles. The reason lies on the fact that the integrated timetable for two bays is the critical contribution to the DGBC performance and it yields the better cooperation between two spreaders and the driver.