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.     

A batching-move iterated local search algorithm for the bin packing problem with generalized precedence constraints

In this paper, we propose a generalisation of the bin packing problem, obtained by adding precedences between items that can assume heterogeneous non-negative integer values. Such generalisation also models the well-known Simple Assembly Line Balancing Problem of type I. To solve the problem, we propose a simple and effective iterated local search algorithm that integrates in an innovative way of constructive procedures and neighbourhood structures to guide the search to local optimal solutions. Moreover, we apply some preprocessing procedures and adapt classical lower bounds from the literature. Extensive computational experiments on benchmark instances suggest that the developed algorithm is able to generate good quality solutions in a reasonable computational time.     

A cross-entropy approach to the single row facility layout problem

The single row facility layout problem is to arrange a given number of facilities along a straight line so as to minimise the total cost associated with the interactions between the facilities. In this paper, a metaheuristic algorithm based on the cross-entropy method, incorporating a local search procedure and symmetry-breaking techniques, is developed to solve this problem. The proposed algorithm has been tested on some widely used benchmark instances. The computational results show that the proposed algorithm has found the optimal or the best solutions known so far for the instances of size with up to 100 facilities and is competitive with some existing algorithms.     

A workload balancing genetic algorithm for the quay crane scheduling problem

This paper proposes a novel genetic algorithm to deal with the quay crane scheduling problem (QCSP), which is known to be one of the most critical tasks in terminal operations because its efficiency and the quality of the schedule directly influence the productivity of the terminal. QCSP has been studied intensively in recent years. Algorithms in this field are concerned in the solution quality obtained and the required computational time. As QCSP is known to be NP-hard, heuristic approaches are widely adopted. The genetic algorithm proposed is constructed with a novel workload balancing heuristics, which is capable of considering the loading conditions of different quay cranes (QCs) during the reassignment of task-to-QC. The idea is modelled as a fuzzy logic controller to guide the mutation rate and mutation mechanism of the genetic algorithm. As a result, the proposed algorithm does not require any predefined mutation rate. Meanwhile, the genetic algorithm can more adequately reassign tasks to QCs according to the QCs’ loading condition throughout the evolution. The proposed algorithm has been tested with the well-known benchmark problem sets in this field and produces some new best solutions in a much shorter computational time.     

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.     

Scatter search heuristic for least-cost design of water distribution networks

The optimization problems of water distribution networks are complex, multi-modal and discrete-variable problems that cannot be easily solved with conventional optimization algorithms. Heuristic algorithms such as genetic algorithms, simulated annealing, tabu search and ant colony optimization have been extensively employed over the last decade. This article proposed an optimization procedure based on the scatter search (SS) framework, which is also a heuristic algorithm, to obtain the least-cost designs of three well-known looped water distribution networks (two-loop, Hanoi and New York networks). The computational results obtained with the three benchmark instances indicate that SS is able to find solutions comparable to those provided by some of the most competitive algorithms published in the literature.     

A local-best harmony search algorithm with dynamic subpopulations

This article presents a local-best harmony search algorithm with dynamic subpopulations (DLHS) for solving the bound-constrained continuous optimization problems. Unlike existing harmony search algorithms, the DLHS algorithm divides the whole harmony memory (HM) into many small-sized sub-HMs and the evolution is performed in each sub-HM independently. To maintain the diversity of the population and to improve the accuracy of the final solution, information exchange among the sub-HMs is achieved by using a periodic regrouping schedule. Furthermore, a novel harmony improvisation scheme is employed to benefit from good information captured in the local best harmony vector. In addition, an adaptive strategy is developed to adjust the parameters to suit the particular problems or the particular phases of search process. Extensive computational simulations and comparisons are carried out by employing a set of 16 benchmark problems from the literature. The computational results show that, overall, the proposed DLHS algorithm is more effective or at least competitive in finding near-optimal solutions compared with state-of-the-art harmony search variants.     

A tabu search algorithm with solution space partition and repairing procedure for cyclic robotic cell scheduling problem

This paper proposes a tabu search (TS) algorithm to solve an NP-hard cyclic robotic scheduling problem. The objective is to find a cyclic robot schedule that maximises the throughput. We first formulate the problem as a linear program, provided that the robot move sequence is given, and reduce the problem to searching for an optimal robot move sequence. We find that the solution space can be divided into some specific subspaces by the maximal number of works-in-process. Then, we propose a TS algorithm to synchronously perform local searches in each subspace. To speed up our algorithm, dominated subspaces are eliminated by lower and upper bounds of the cycle time during the iterations. In the TS, a constructive heuristic is developed to generate initial solutions for each subspace and a repairing procedure is proposed to maintain the feasibility of the solutions generated in the initialisation stage and the neighbours search process. Computational comparison both on benchmark instances and randomly generated instances indicates that our algorithm is efficient for the cyclic robotic scheduling problem.     

Multiple colony ant algorithm for job-shop scheduling problem

Ant colony optimization (ACO) is a metaheuristic that takes inspiration from the foraging behaviour of a real ant colony to solve the optimization problem. This paper presents a multiple colony ant algorithm to solve the Job-shop Scheduling Problem with the objective that minimizes the makespan. In a multiple colony ant algorithm, ants cooperate to find good solutions by exchanging information among colonies which are stored in a master pheromone matrix that serves the role of global memory. The exploration of the search space in each colony is guided by different heuristic information. Several specific features are introduced in the algorithm in order to improve the efficiency of the search. Among others is the local search method by which the ant can fine-tune their neighbourhood solutions. The proposed algorithm is tested over set of benchmark problems and the computational results demonstrate that the multiple colony ant algorithm performs well on the benchmark problems.     

A hybrid Tabu sample-sort simulated annealing approach for solving distributed scheduling problem

The distributed scheduling problem has been considered as the allocation of a task to various machines in such a way that these machines are situated in different factories and these factories are geographically distributed. Therefore distributed scheduling has fulfilled various objectives, such as allocation of task to the factories and machines in such a manner that it can utilise the maximum resources. The objective of this paper is to minimise the makespan in each factory by considering the transportation time between the factories. In this paper, to address such a problem of scheduling in distributed manufacturing environment, a novel algorithm has been developed. The proposed algorithm gleans the ideas both from Tabu search and sample sort simulated annealing. A new algorithm known as hybrid Tabu sample-sort simulated annealing (HTSSA) has been developed and it has been tested on the numerical example. To reveal the supremacy of the proposed algorithm over simple SSA and Tabu search, more computational experiments have also been performed on 10 randomly generated datasets.     

Scheduling TV commercials using genetic algorithms

In this paper, the problem of scheduling commercial messages during the peak of viewing time of a TV channel is formulated as a combinatorial auction-based mathematical programming model. Through this model, a profitable and efficient mechanism for allocating the advertising time to advertisers is developed by which the revenue of TV channels is maximised while the effectiveness of advertising is increased. We developed a steady-state genetic algorithm to find an optimal or a near optimal solution for the proposed problem. A computational experiment was conducted for evaluating the efficiency of the proposed algorithm. A set of test problems with different sizes were generated, using the pseudo-random generation mechanism, and solved by the proposed genetic algorithm. The optimal solutions of the linear programming relaxation of these test problems were also obtained and were used for evaluating the quality of solutions obtained by the developed algorithm. The results of this computational experiment revealed the robustness of the solutions and acceptably low computational time for obtaining these solutions. The computational results also demonstrated that the proposed genetic algorithm had an appropriate ability to preserve population diversity during the search and was capable of obtaining high-quality solutions for the proposed problem.     

A scatter search algorithm for stacking sequence optimisation of laminate composites

This paper explores the metaheuristic approach called scatter search for lay-up sequence optimisation of laminate composite panels. Scatter search is an evolutionary method that has recently been found to be promising for solving combinatorial optimisation problems. The scatter search framework is flexible and allows the development of alternative implementations with varying degree of sophistication. The main objective of this paper is to demonstrate the effectiveness of the proposed scatter search algorithm for the combinatorial problem like stacking sequence optimisation of laminate composite panels. Preliminary investigations have been carried out to compare the optimal stacking sequences obtained using scatter search algorithm for buckling load maximisation with the best known published results. Studies indicate that the optimal buckling load factors obtained using the proposed scatter search algorithm found to be either superior or comparable to the best known published results.

Later, two case studies have been considered in this paper. Thermal buckling optimisation of laminated composite plates subjected to temperature rise is considered as the first case study. The results obtained are compared with an exact enumerative study conducted on the problem to demonstrate the effectiveness and performance of the proposed scatter search algorithm. The second case study is optimisation of hybrid laminate composite panels for weight and cost with frequency and buckling constraints. The two objectives are considered individually and also collectively to solve as multi-objective optimisation problem. Finally the computational efficiency of the proposed scatter search algorithm has been investigated by comparing the results with various implementations of genetic algorithm customised for laminate composites. It was shown in this paper through numerical experiments that the scatter search is capable of finding practical solutions for optimal lay-up sequence optimisation of composite laminates and results are comparable and sometimes even superior to genetic algorithms.     

A discrete artificial bee colony algorithm for single machine scheduling problems

This paper presents a discrete artificial bee colony algorithm for a single machine earliness–tardiness scheduling problem. The objective of single machine earliness–tardiness scheduling problems is to find a job sequence that minimises the total sum of earliness–tardiness penalties. Artificial bee colony (ABC) algorithm is a swarm-based meta-heuristic, which mimics the foraging behaviour of honey bee swarms. In this study, several modifications to the original ABC algorithm are proposed for adapting the algorithm to efficiently solve combinatorial optimisation problems like single machine scheduling. In proposed study, instead of using a single search operator to generate neighbour solutions, random selection from an operator pool is employed. Moreover, novel crossover operators are presented and employed with several parent sets with different characteristics to enhance both exploration and exploitation behaviour of the proposed algorithm. The performance of the presented meta-heuristic is evaluated on several benchmark problems in detail and compared with the state-of-the-art algorithms. Computational results indicate that the algorithm can produce better solutions in terms of solution quality, robustness and computational time when compared to other algorithms.     

Balancing of U-type assembly systems using simulated annealing

The paper presents a new simulated annealing (SA)-based algorithm for the assembly line-balancing problem with a U-type configuration. The proposed algorithm employs an intelligent mechanism to search a large solution space. U-type assembly systems are becoming increasingly popular in today's modern production environments since they are more general than the traditional assembly systems. In these systems, tasks are to be allocated into stations by moving forward and backward through the precedence diagram in contrast to a typical forward move in the traditional assembly systems. The performance of the algorithm is measured by solving a large number of benchmark problems available in the literature. The results of the computational experiments indicate that the proposed SA-based algorithm performs quite effectively. It also yields the optimal solution for most problem instances. Future research directions and a comprehensive bibliography are also provided here.     

A hybrid evolutionary graph-based multi-objective algorithm for layout optimization of truss structures

In this paper a new graph-based evolutionary algorithm, gM-PAES, is proposed in order to solve the complex problem of truss layout multi-objective optimization. In this algorithm a graph-based genotype is employed as a modified version of Memetic Pareto Archive Evolution Strategy (M-PAES), a well-known hybrid multi-objective optimization algorithm, and consequently, new graph-based crossover and mutation operators perform as the solution generation tools in this algorithm. The genetic operators are designed in a way that helps the multi-objective optimizer to cover all parts of the true Pareto front in this specific problem. In the optimization process of the proposed algorithm, the local search part of gM-PAES is controlled adaptively in order to reduce the required computational effort and enhance its performance. In the last part of the paper, four numeric examples are presented to demonstrate the performance of the proposed algorithm. Results show that the proposed algorithm has great ability in producing a set of solutions which cover all parts of the true Pareto front.     

An effective shuffled frog-leaping algorithm for solving the hybrid flow-shop scheduling problem with identical parallel machines

In this article, an effective shuffled frog-leaping algorithm (SFLA) is proposed to solve the hybrid flow-shop scheduling problem with identical parallel machines (HFSP-IPM). First, some novel heuristic decoding rules for both job order decision and machine assignment are proposed. Then, three hybrid decoding schemes are designed to decode job order sequences to schedules. A special bi-level crossover and multiple local search operators are incorporated in the searching framework of the SFLA to enrich the memetic searching behaviour and to balance the exploration and exploitation capabilities. Meanwhile, some theoretical analysis for the local search operators is provided for guiding the local search. The parameter setting of the algorithm is also investigated based on the Taguchi method of design of experiments. Finally, numerical testing based on well-known benchmarks and comparisons with some existing algorithms are carried out to demonstrate the effectiveness of the proposed algorithm.     

Integrated process planning and scheduling for large-scale flexible job shops using metaheuristics

In this paper, we discuss an integrated process planning and scheduling problem in large-scale flexible job shops (FJSs). We assume that products can be manufactured in different ways, i.e. using different bills of materials (BOM) and routes for the same product. The total weighted tardiness is the performance measure of interest. A Mixed Integer Programming formulation is provided for the researched problem. Because of the NP-hardness of the investigated problem, an iterative scheme is designed that is based on variable neighbourhood search (VNS) on the process planning level. Appropriate neighbourhood structures for VNS are proposed. Because the evaluation of each move within VNS requires the solution of a large-scale FJS scheduling problem instance, efficient heuristics based on local search from previous research are considered on the scheduling level. Extensive computational experiments based on new randomly generated problem instances are conducted. In addition, a parallel version of the VNS is investigated within the computational experiments. The proposed iterative scheme is benchmarked against a genetic algorithm (GA) from the literature that simultaneously considers process planning and scheduling for the special case where a single BOM is available for each product. It turns out that the new iterative scheme outperforms the GA and a memetic algorithm based on the GA. It is able to solve even large-size problem instances in reasonable amount of time.     

A hybrid Pareto-based local search algorithm for multi-objective flexible job shop scheduling problems

This paper presents a hybrid Pareto-based local search (PLS) algorithm for solving the multi-objective flexible job shop scheduling problem. Three minimisation objectives are considered simultaneously, i.e. the maximum completion time (makespan), the total workload of all machines, and the workload of the critical machine. In this study, several well-designed neighbouring approaches are proposed, which consider the problem characteristics and thus can hold fast convergence ability while keep the population with a certain level of quality and diversity. Moreover, a variable neighbourhood search (VNS) based self-adaptive strategy is embedded in the hybrid algorithm to utilise the neighbouring approaches efficiently. Then, an external Pareto archive is developed to record the non-dominated solutions found so far. In addition, a speed-up method is devised to update the Pareto archive set. Experimental results on several well-known benchmarks show the efficiency of the proposed hybrid algorithm. It is concluded that the PLS algorithm is superior to the very recent algorithms, in term of both search quality and computational efficiency.     

A guided search genetic algorithm using mined rules for optimal affective product design

Affective design is an important aspect of new product development, especially for consumer products, to achieve a competitive edge in the marketplace. It can help companies to develop new products that can better satisfy the emotional needs of customers. However, product designers usually encounter difficulties in determining the optimal settings of the design attributes for affective design. In this article, a novel guided search genetic algorithm (GA) approach is proposed to determine the optimal design attribute settings for affective design. The optimization model formulated based on the proposed approach applied constraints and guided search operators, which were formulated based on mined rules, to guide the GA search and to achieve desirable solutions. A case study on the affective design of mobile phones was conducted to illustrate the proposed approach and validate its effectiveness. Validation tests were conducted, and the results show that the guided search GA approach outperforms the GA approach without the guided search strategy in terms of GA convergence and computational time. In addition, the guided search optimization model is capable of improving GA to generate good solutions for affective design.     

Simultaneous solving of balancing and sequencing problems in mixed-model assembly line systems

Recently, the mixed-model assembly line (MMAL) has been widely studied by many researchers. In fact, there are two basic problems, namely balancing and sequencing problems, which have been investigated in a lot of studies separately, but few researchers have solved both problems simultaneously. Regarding this, the best results in minimising total utility work have been gained by developing a co-evolutionary genetic algorithm (Co-GA) so far. This paper provides a mixed-integer linear programming (MILP) model to jointly solve the problems. Because of NP-hardness, an evolution strategies (ES) algorithm is presented and evaluated by the same test problems in the literature. Two main hypotheses, namely simultaneous search and feasible search, are tested in the proposed algorithm to improve the quality of solutions. To calibrate the algorithm, a Taguchi design of experiments is employed. The proposed ES is compared with the modified version of Co-GA and the MILP model results. According to numerical experiments and statistical proving, the proposed ES outperformed the modified Co-GA from two points of view: the objective function and the computational time. Additionally, the meta-heuristic algorithms are examined in terms of other well-known criteria in MMAL. Finally, the contribution of each hypothesis in accounting for this superiority is analysed.