A modified generalized extremal optimization algorithm for the quay crane scheduling problem with interference constraints

The quay crane scheduling problem (QCSP) determines the handling sequence of tasks at ship bays by a set of cranes assigned to a container vessel such that the vessel's service time is minimized. A number of heuristics or meta-heuristics have been proposed to obtain the near-optimal solutions to overcome the NP-hardness of the problem. In this article, the idea of generalized extremal optimization (GEO) is adapted to solve the QCSP with respect to various interference constraints. The resulting GEO is termed the modified GEO. A randomized searching method for neighbouring task-to-QC assignments to an incumbent task-to-QC assignment is developed in executing the modified GEO. In addition, a unidirectional search decoding scheme is employed to transform a task-to-QC assignment to an active quay crane schedule. The effectiveness of the developed GEO is tested on a suite of benchmark problems introduced by K.H. Kim and Y.M. Park in 2004 (European Journal of Operational Research, Vol. 156, No. 3). Compared with other well-known existing approaches, the experiment results show that the proposed modified GEO is capable of obtaining the optimal or near-optimal solution in a reasonable time, especially for large-sized problems.     

A note on: A modified generalized extremal optimization algorithm for the quay crane scheduling problem with interference constraints

In a recent article, Guo, Cheng and Wang proposed a randomized search algorithm, called modified generalized extremal optimization (MGEO), to solve the quay crane scheduling problem for container groups under the assumption that schedules are unidirectional. The authors claim that the proposed algorithm is capable of finding new best solutions with respect to a well-known set of benchmark instances taken from the literature. However, as shown in this note, there are some errors in their work that can be detected by analysing the Gantt charts of two solutions provided by MGEO. In addition, some comments on the method used to evaluate the schedule corresponding to a task-to-quay crane assignment and on the search scheme of the proposed algorithm are provided. Finally, to assess the effectiveness of the proposed algorithm, the computational experiments are repeated and additional computational experiments are provided.     

Disruption recovery model for berth and quay crane scheduling in container terminals

This article addresses the problem of recovering berth and quay crane (QC) schedules in container terminals when disruptions occur after a subset of operations has been processed. Firstly, models for simultaneous optimization of berth and QC schedules are developed. Then, two strategies, namely, QC rescheduling strategy and berth reallocation strategy are proposed to tackle disruptions and recover the berth and QC schedule, and models for the two strategies are developed respectively. To solve the disruption recovery models, algorithms based on local rescheduling and tabu search are designed. Finally, numerical experiments are provided to illustrate the validity of the proposed model and algorithms.     

A note on a model for quay crane scheduling with non-crossing constraints

This article studies the quay crane scheduling problem with non-crossing constraints, which is an operational problem that arises in container terminals. An enhancement to a mixed integer programming model for the problem is proposed and a new class of valid inequalities is introduced. Computational results show the effectiveness of these enhancements in solving the problem to optimality.     

Quay crane scheduling for an indented berth

This article explores the quay crane scheduling problem at an indented berth. The indented berth is known as an innovative implementation in the container terminals to tackle the challenge from the emergence of more and more mega-containerships. A mixed integer programming model by considering the non-crossing and safety distance constraints is formulated. A Tabu search heuristic is developed to solve the proposed problem. The computational results from this research indicate that the designed Tabu search is an effective method to handle the quay crane scheduling problem at an indented berth.     

Quay crane scheduling with dual cycling

In this article, the dual cycling quay crane scheduling problem (D-QCSP) with hatches is addressed to minimize the operation cycles of quay cranes. The problem is decomposed into two sub-problems: the intra-group stage (sequencing stacks within each hatch) and the inter-group stage (scheduling all hatches). A new stack sequencing method is constructed for stacks of each hatch, which is modelled as a two-machine non-permutation flow shop scheduling problem. By removing inner gaps using left-shifting, the adapted hatch scheduling sub-problem is modelled as a two-machine grouped flow shop scheduling problem, which contains more precise processing times. A composite heuristic is proposed for the D-QCSP. 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 and dual cycling needs many fewer quay crane operating cycles than single cycling.     

Multiple yard cranes scheduling for loading operations in a container terminal

The efficiency of yard crane scheduling is critical in increasing the throughput of a maritime terminal. This article studies the problem of scheduling multiple yard cranes in loading operations. The movements of yard cranes among container blocks and the sequencing of yard cranes within each block are studied at the same time. Potential interferences between yard cranes are considered. A mixed integer programming model is developed to formulate the problem. A genetic algorithm and a tabu search algorithm are proposed to obtain near-optimal solutions. Experimental tests are conducted to evaluate the performance of the two algorithms based on various data settings.     

Integrated berth allocation and quay crane assignment with maintenance activities

With the rapid development of worldwide container trade, quay cranes and other resources in container terminals are suffering from increasing workloads. To reduce their failure probabilities, quay cranes usually require preventive maintenance. However, these important activities are often ignored during quay crane planning in literature. This work studies an integrated berth allocation, quay crane assignment and specific quay crane assignment problem where quay crane maintenance is involved, and establishes an integer linear programming with the objective of minimising the total turnaround time. Due to the NP-hardness of the problem, CPLEX only solves instances with up to 18 vessels. For solving larger instances, we propose Left-and-Right Vessel Move (LRVM) algorithm and improved Genetic Algorithm (GA). Experimental results reveal that GA slightly outperforms LRVM with respect to solution quality as the solution of LRVM serves as one of the initial chromosomes of GA. LRVM can output feasible solutions within seconds, even for instances with 50 vessels. We further present a sensitivity analysis of preferred berth segments, and make numerical comparison on algorithm performance for the relevant model without quay crane maintenance. Both the models and proposed heuristics in this work help in dealing with the operational management of container terminal resources in practice.     

Optimisation of the reverse scheduling problem by a modified genetic algorithm

Traditional scheduling methods can only arrange the operations on corresponding machines with appropriate sequences under pre-defined environments. This means that traditional scheduling methods require that all parameters to be determined before scheduling. However, real manufacturing systems often encounter many uncertain events. These will change the status of manufacturing systems. These may cause the original schedule to no longer be optimal or even to be infeasible. Traditional scheduling methods, however, cannot cope with these cases. New scheduling methods are needed. Among these new methods, one method ‘reverse scheduling’ has attracted more and more attentions. This paper focuses on the single-machine reverse scheduling problem and designs a modified genetic algorithm with a local search (MLGA) to solve it. To improve the performance of MLGA, efficient encoding, offspring update mechanism and a local search have been employed and developed. To verify the feasibility and effectiveness of the proposed MLGA, 27 instances have been conducted and results have been compared with existing methods. The results show that the MLGA has achieved satisfactory improvement. This approach also has been applied to solve a real-world scheduling problem from one shipbuilding industry. The results show that the MLGA can bring some benefits.     

Quay crane scheduling in container terminals

The problem of scheduling identical quay cranes moving along a common linear rail to handle containers for a ship is studied. The ship has a number of container-stacking compartments called bays, and only one quay crane can work on a bay at the same time. The objective of the scheduling problem is to find the work schedule for each quay crane which minimizes the ship’s stay time in port. Finding the optimal solution of the scheduling problem is computationally intractable and a heuristic is proposed to solve it. The heuristic first decomposes the difficult multi-crane scheduling problem into easier subproblems by partitioning the ship into a set of non-overlapping zones. The resulting subproblems for each possible partition are solved optimally by a simple rule. An effective algorithm for finding tight lower bounds is developed by modifying and enhancing an effective lower-bounding procedure proposed in the literature. Computational experiments were carried out to evaluate the performance of the heuristic on a set of test problems randomly generated based on typical terminal operations data. The computational results show that the heuristic can indeed find effective solutions for the scheduling problem, with the heuristic solutions on average 4.8% above their lower bounds.     

Research on job-shop scheduling problem based on genetic algorithm

With job-shop scheduling (JSS) it is usually difficult to achieve the optimal solution with classical methods due to a high computational complexity (NP-hard). According to the nature of JSS, an improved definition of the JSS problem is presented and a JSS model based on a novel algorithm is established through the analysis of working procedure, working data, precedence constraints, processing performance index, JSS algorithm and so on. A decode select string (DSS) decoding genetic algorithm based on operation coding modes, which includes assembly problems, is proposed. The designed DSS decoding genetic algorithm (GA) can avoid the appearance of infeasible solutions through comparing current genes with DSS in the decoding procedure to obtain working procedure which can be decoded. Finally, the effectiveness and superiority of the proposed method is clarified compared to the classical JSS methods through the simulation experiments and the benchmark problem.     

An effective heuristic for scheduling a yard crane to handle jobs with different ready times

In land-constrained port container terminals, yard cranes are commonly used for handling containers in a container yard to load containers onto or unload containers from trucks. However, yard cranes are bulky, slow and need to move frequently between their work locations. As it is common that the container flow in a terminal is bottlenecked by yard crane operations, effective work schedules of yard cranes are needed to increase the terminal’s throughput. This article studies the problem of scheduling a yard crane to perform a given set of container handling jobs with different ready times. The objective is to minimize the sum of job waiting times. It is noted that the scheduling problem is NP-complete. This research develops a heuristic to solve the scheduling problem and an algorithm to find lower bounds for benchmarking the schedules found by the heuristic. The performance of the heuristic is evaluated by a set of test problems generated on the basis of real-life terminal operations data. Indeed, the computational results show that the proposed heuristic can find effective solutions for the scheduling problem.     

A genetic algorithm approach for production scheduling with mould maintenance consideration

The traditional approach for maintenance scheduling concerns single-resource (machine) maintenance during production which may not be sufficient to improve production system reliability as a whole. Besides, in the literature many researchers schedule maintenance activities periodically with fixed maintenance duration. However, in a real manufacturing system maintenance activities can be executed earlier and the maintenance duration will become shorter since less time and effort are required. A practical example is that in a plastic production system, the proportion of machine-related downtime is even lower than mould-related downtime. The planned production operations are usually interrupted seriously because of the mismatch among the maintenance periods between injection machine and mould. In this connection, this paper proposes to jointly schedule production and maintenance tasks of multi-resources in order to improve production system reliability by reducing the mismatch among various processes. To integrate machine and mould maintenance tasks in production, this paper attempts to model the production scheduling with mould scheduling (PS-MS) problem with time-dependent deteriorating maintenance schemes. The objective of this paper is to propose a genetic algorithm approach to schedule maintenance tasks jointly with production jobs for the PS-MS problem, so as to minimise the makespan of production jobs.     

Hybrid genetic algorithm for test bed scheduling problems

In this paper, we address the scheduling problem for a heavy industry company which provides ship engines for shipbuilding companies. Before being delivered to customers, ship engines are assembled, tested and disassembled on the test beds. Because of limited test bed facilities, it is impossible for the ship engine company to satisfy all customers’ orders. Therefore, they must select the orders that can be feasibly scheduled to maximise profit. An integer programming model is developed for order selection and test bed scheduling but it cannot handle large problems in a reasonable amount of time. Consequently, a hybrid genetic algorithm (GA) is suggested to solve the developed model. Several experiments have been carried out to demonstrate the performance of the proposed hybrid GA in scheduling test beds. The results show that the hybrid GA performs with an outstanding run-time and small errors in comparison with the integer programming model.     

U-shaped assembly line balancing problem with genetic algorithm

This paper presents a multi-objective genetic algorithm (moGA) to solve the U-shaped assembly line balancing problem (UALBP). As a consequence of introducing the just-in-time (JIT) production principle, it has been recognized that U-shaped assembly line systems offer several benefits over the traditional straight line systems. We consider both the traditional straight line system and the U-shaped assembly line system, thus as an unbiased examination of line efficiency. The performance criteria considered are the number of workstations (the line efficiency) and the variation of workload. The results of experiments show that the proposed model produced as good or even better line efficiency of workstation integration and improved the variation of workload.     

Hybrid genetic algorithm for group technology economic lot scheduling problem

The concept of group technology has been successfully applied to many production systems, including flexible manufacturing systems. In this paper we apply group technology principles to the economic lot scheduling problem, which has been studied for over 40 years. We develop a heuristic algorithm and a hybrid genetic algorithm for the group technology economic lot scheduling problem. Numerical experiments show that the developed algorithms outperform the existing heuristics.     

Scheduling operations of a rail crane and container deliveries between rail and port terminals

This article addresses the problem of scheduling container transfer operations in rail terminals. The overall problem can be divided into three smaller problems: constructing a dual-cycle delivery task by matching inbound and outbound containers; determining parking positions for trucks; and sequencing the delivery tasks for transfer by the rail crane. This article provides a mathematical model to obtain the optimal solutions to these problems, and suggests genetic and heuristic algorithms to reduce computational time when solving larger problems. Numerical experiments are conducted to validate the performance of the suggested heuristic algorithms.     

Integrated scheduling of a container handling system with simultaneous loading and discharging operations

The integrated scheduling of container handling systems aims to optimize the coordination and overall utilization of all handling equipment, so as to minimize the makespan of a given set of container tasks. A modified disjunctive graph is proposed and a mixed 0–1 programming model is formulated. A heuristic algorithm is presented, in which the original problem is divided into two subproblems. In the first subproblem, contiguous bay crane operations are applied to obtain a good quay crane schedule. In the second subproblem, proper internal truck and yard crane schedules are generated to match the given quay crane schedule. Furthermore, a genetic algorithm based on the heuristic algorithm is developed to search for better solutions. The computational results show that the proposed algorithm can efficiently find high-quality solutions. They also indicate the effectiveness of simultaneous loading and discharging operations compared with separate ones.     

Re-entrant flow shop scheduling problem with time windows using hybrid genetic algorithm based on auto-tuning strategy

The re-entrant flow shop scheduling problem considering time windows constraint is one of the most important problems in hard-disc drive (HDD) manufacturing systems. In order to maximise the system throughput, the problem of minimising the makespan with zero loss is considered. In this paper, evolutionary techniques are proposed to solve the complex re-entrant scheduling problem with time windows constraint in manufacturing HDD devices with lot size. This problem can be formulated as a deterministic Fm?|?fmls, rcrc, temp?|?C_max problem. A hybrid genetic algorithm was used for constructing chromosomes by checking and repairing time window constraints, and improving chromosomes by a left-shift heuristic as a local search algorithm. An adaptive hybrid genetic algorithm was eventually developed to solve this problem by using fuzzy logic control in order to enhance the search ability of the genetic algorithm. Finally, numerical experiments were carried out to demonstrate the efficiency of the developed approaches.