Ant colony optimisation with elitist ant for sequencing problem in a mixed model assembly line

Optimised sequencing in the Mixed Model Assembly Line (MMAL) is a major factor to effectively balance the rate at which raw materials are used for production. In this paper we present an Ant Colony Optimisation with Elitist Ant (ACOEA) algorithm on the basis of the basic Ant Colony Optimisation (ACO) algorithm. An ACOEA algorithm with the taboo search and elitist strategy is proposed to form an optimal sequence of multi-product models which can minimise deviation between the ideal material usage rate and the practical material usage rate. In this paper we compare applications of the ACOEA, ACO, and two other commonly applied algorithms (Genetic Algorithm and Goal Chasing Algorithm) to benchmark, stochastic problems and practical problems, and demonstrate that the use of the ACOEA algorithm minimised the deviation between the ideal material consumption rate and the practical material consumption rate under various critical parameters about multi-product models. We also demonstrate that the convergence rate for the ACOEA algorithm is significantly more than that for all the others considered.     

Ant colony optimisation with parameterised search space for the job shop scheduling problem

The job-shop scheduling problem (JSSP) is known to be NP-hard. Due to its complexity, many metaheuristic algorithm approaches have arisen. Ant colony metaheuristic algorithm, lately proposed, has successful application to various combinatorial optimisation problems. In this study, an ant colony optimisation algorithm with parameterised search space is developed for JSSP with an objective of minimising makespan. The problem is modelled as a disjunctive graph where arcs connect only pairs of operations related rather than all operations are connected in pairs to mitigate the increase of the spatial complexity. The proposed algorithm is compared with a multiple colony ant algorithm using 20 benchmark problems. The results show that the proposed algorithm is very accurate by generating 12 optimal solutions out of 20 benchmark problems, and mean relative errors of the proposed and the multiple colony ant algorithms to the optimal solutions are 0.93% and 1.24%, respectively.     

Quantum-inspired ant colony optimisation algorithm for a two-stage permutation flow shop with batch processing machines

This paper studied two-stage permutation flow shop problems with batch processing machines, considering different job sizes and arbitrary arrival times, with the optimisation objective of minimising the makespan. The quantum-inspired ant colony optimisation (QIACO) algorithm was proposed to solve the problem. In the QIACO algorithm, the ants are divided into two groups: one group selects the largest job in terms of job size as the initial job for each batch and the other group selects the smallest job as the initial job for each batch. Each group of ants has its own pheromone matrix. In the computational experiment, our novel algorithm was compared with the hybrid discrete differential evolution (HDDE) algorithm and the batch-based hybrid ant colony optimisation (BHACO) algorithm. Although the HDDE algorithm has a shorter run time, the quality of the solution for large-scale jobs is not good, while the BHACO algorithm always obtains a better solution but requires a longer run time. The computational results show that the QIACO algorithm embedded in the quantum information has advantages in terms of both solution quality and running time.     

Ant colony optimisation with random selection for block transportation scheduling with heterogeneous transporters in a shipyard

This paper considers a scheduling problem of heterogeneous transporters for pickup and delivery blocks in a shipyard assuming a static environment where all transportation requirements for blocks are predetermined. In the block transportation scheduling problem, the important issue is to determine which transporter delivers the block from one plant to the other plant and when, in order to minimise total logistic times. Therefore, the objective of the problem is to simultaneously determine the allocation policy of blocks and the sequence policy of transporters to minimise the weighted sum of empty transporter travel times, delay times, and tardy times. A mathematical model for the optimal solution is derived and an ant colony optimisation algorithm with random selection (ACO_RS) is proposed. To demonstrate the performance of ACO_RS, computational experiments are implemented in comparing the solution with the optimal solutions obtained by CPLEX in small-sized problems and the solutions obtained by conventional ACO in large-sized problems.     

Ant colony optimisation algorithms for two-stage permutation flow shop with batch processing machines and nonidentical job sizes

This paper focuses on minimising the maximum completion time for the two-stage permutation flow shop scheduling problem with batch processing machines and nonidentical job sizes by considering blocking, arbitrary release times, and fixed setup and cleaning times. Two hybrid ant colony optimisation algorithms, one based on job sequencing (JHACO) and the other based on batch sequencing (BHACO), are proposed to solve this problem. First, max-min pheromone restriction rules and a local optimisation rule are embedded into JHACO and BHACO, respectively, to avoid trapping in local optima. Then, an effective lower bound is estimated to evaluate the performances of the different algorithms. Finally, the Taguchi method is adopted to investigate and optimise the parameters for JHACO and BHACO. The performances of the proposed algorithms are compared with that of CPLEX on small-scale instances and those of a hybrid genetic algorithm (HGA) and a hybrid discrete differential evolution (HDDE) algorithm on full-scale instances. The computational results demonstrate that BHACO outperforms JHACO, HDDE and HGA in terms of solution quality. Besides, JHACO strikes a balance between solution quality and run time.     

Solving a time constrained two-crane routing problem for material handling with an ant colony optimisation approach: an application in the roof-tile industry

This paper presents an ant colony optimisation (ACO)-based solution approach for a real-world two-crane routing problem, where a number of different load carriers must be moved within a given cycle time by two gantry cranes in a continuous production process for roof tiles. The cranes have to transport the roof-tile batches and to return the load carriers and intermediate pads for subsequent batches. A feasible solution has to observe workflow-, space-, collision-, and machine-cycle constraints. The objective is to find a feasible schedule that minimises the working time for both cranes. The authors compare different solution approaches in terms of learning – and visibility strategies based on ACO in extensive numerical studies. A visibility concept is used to both partition and balance workload between the cranes.     

A simulated annealing algorithm to the multi-period fixed charge distribution problem associated with backorder and inventory

This paper addresses a multi-period fixed charge distribution problem associated with backorder and inventory. The objective is to determine the size of the shipments, backorder and inventory at each period, so that the total cost incurred during the entire period towards transportation, backorder and inventory is minimised. A pure integer non-linear programming problem is formulated. A simulated annealing based heuristic is proposed to solve and is illustrated. The proposed methodology is evaluated by comparing its solutions with the lower bound and equivalent variable cost solutions. The comparisons reveal that the simulated annealing generates better solutions than the equivalent variable cost solutions and is capable of providing solutions closer to the lower bound solutions of the problems.     

Supply chain optimisation with both production and transportation integration: multiple vehicles for a single perishable product

This paper deals with an extension of the integrated production and transportation scheduling problem (PTSP) by considering multiple vehicles (PTSPm) for optimisation of supply chains. The problem reflects a real concern for industry since production and transportation subproblems are commonly addressed independently or sequentially, which leads to sub-optimal solutions. The problem includes specific capacity constraints, the short lifespan of products and the special case of the single vehicle that has already been studied in the literature. A greedy randomised adaptive search procedure (GRASP) with an evolutionary local search (ELS) is proposed to solve the instances with a single vehicle as a special case. The method has been proven to be more effective than those published and provides shorter computational times with new best solutions for the single vehicle case. A new set of instances with multiple vehicles is introduced to favour equitable future research. Our study extends previous research using an indirect resolution approach and provides an algorithm to solve a wide range of one-machine scheduling problems with the proper coordination of single or multiple vehicles.     

Performance of an ant colony optimisation algorithm in dynamic job shop scheduling problems

The goal of the current study is to identify appropriate application domains of Ant Colony Optimisation (ACO) in the area of dynamic job shop scheduling problem. The algorithm is tested in a shop floor scenario with three levels of machine utilisations, three different processing time distributions, and three different performance measures for intermediate scheduling problems. The steady-state performances of ACO in terms of mean flow time, mean tardiness, total throughput on different experimental environments are compared with those from dispatching rules including first-in-first-out, shortest processing time, and minimum slack time. Two series of experiments are carried out to identify the best ACO strategy and the best performing dispatching rule. Those two approaches are thereafter compared with different variations of processing times. The experimental results show that ACO outperforms other approaches when the machine utilisation or the variation of processing times is not high.     

A hybrid VNS-HS algorithm for a supply chain scheduling problem with deteriorating jobs

This paper investigates a coordinated scheduling problem in a two stage supply chain where parallel-batching machine, deteriorating jobs and transportation coordination are considered simultaneously. During the production stage, jobs are processed by suppliers and there exists one parallel-batching machine in each supplier. The actual processing time of a job depends on its starting time and normal processing time. The normal processing time of a batch is equal to the largest normal processing time among all jobs in its batch. During the transportation stage, the jobs are then delivered to the manufacturer. Since suppliers are distributed in different locations, the transportation time between each supplier and the manufacturer is different. Based on some structural properties of the studied problem, an optimal algorithm for minimising makespan on a single supplier is presented. This supply chain scheduling problem is proved to be NP-hard, and a hybrid VNS-HS algorithm combining variable neighbourhood search (VNS) with harmony search (HS) is proposed to find a good solution in reasonable time. Finally, some computational experiments are conducted and the results demonstrate the effectiveness and efficiency of the proposed VNS-HS.     

An integrated location-inventory problem in a closed-loop supply chain with third-party logistics

Third-party logistics (3PL) is a fast growing business. Many large organisations are using 3PL services to reduce operating costs, simplify business processes, and enhance operations and supply chain flexibility. In this paper, we study location-inventory decisions jointly in a closed-loop system with 3PL. First, a model formulation is proposed to develop mixed-integer non-linear programming (MINLP) models for the location-inventory problem under study. Then, a novel heuristics based on differential evolution and the genetic algorithm is designed to solve the MINLP models efficiently. Last, numerical study is presented to illustrate and validate the solution approach.     

Dynamic optimisation for highly agile supply chains in e-procurement context

In the conditions of an increased worldwide competition, supply chains are struggling to respond to an increasingly volatile and complex environment. With technological advances, current practices to build efficient supply chains have changed. Companies are seeking to use internet in order to cope with the flexible and dynamic nature of logistics networks. The purpose of this article is to address the flexible dynamic e-procurement context under asynchronous and repetitive variations over time. The supply chain considered is composed of two levels (buyer–suppliers) operating in highly agile environment. The questions facing the buyer is how many units of product should be purchased and from which supplier in response to variation in term of price and capacity. Because of this highly changing environment characterised by frequent changes in a short time, most of the classical optimisation approaches seem inadequate to address these problems. Recently, dynamic optimisation has been proposed to deal with such problems. However, we have no knowledge of its application in a supply chain context. We suggest a dynamic genetic approach which is applied to an e-procurement context in aim to optimise the procurement process during time.     

Scheduling job shop associated with multiple routings with genetic and ant colony heuristics

The general job shop problem is one of the well known machine scheduling problems, in which the operation sequence of jobs are fixed that correspond to their optimal process plans and/or resource availability. Scheduling and sequencing problems, in general, are very difficult to solve to optimality and are well known as combinatorial optimisation problems. The existence of multiple job routings makes such problems more cumbersome and complicated. This paper addresses a job shop scheduling problem associated with multiple job routings, which belongs to the class of NP hard problems. To solve such NP-hard problems, metaheuristics have emerged as a promising alternative to the traditional mathematical approaches. Two metaheuristic approaches, a genetic algorithm and an ant colony algorithm are proposed for the optimal allocation of operations to the machines for minimum makespan time criterion. ILOG Solver, a scheduler package, is used to evaluate the performance of the proposed algorithms. The comparison reveals that both the algorithms are capable of providing solutions better than the solution obtained with ILOG Solver.     

Aggregate procurement,production, and shipment planning decision problem for a three-echelon supply chain using swarm-based heuristics

Supplier selection is deemed as a crucial strategic decision-making activity in building a competitive edge. Firms prefer to operate with a few trusted suppliers, selected from a bigger pool of vendors. The chosen suppliers are the ones whose commitments are best oriented in realising the business goals of the company. At the same time enterprise targets cannot be achieved in the absence of cost-effective inventory management policies. This has created the inevitable need for aggregate production and distribution planning. Even more competitive strategy would be integrating procurement planning with production-distribution scheduling. We address the problem of integrated procurement, production and shipment planning for a supply chain, spanning over three echelons. Supplier order scheduling is combined with a production-shipment planning process to realise a minimum cost operations policy. Two recently developed swarm heuristics are employed to search for the near optimal solution of the mathematical model, which is developed to capture the aggregate planning problem.     

Multi-objective resource assignment problem in a product-driven supply chain using a Taguchi-based DNA algorithm

This paper conceptualises the integration of tangible and intangible factors into the design consideration of a resource assignment problem for a product-driven supply chain. The problem is formulated mathematically as a multi-objective optimisation model to maximise the broad objectives of profit, ahead of time of delivery, quality, and volume flexibility. Product characteristics are associated with the design requirements of a supply chain. Different types of resources are considered, each differing in its characteristics, thereby providing various alternatives during the design process. The aim is to design integrated supply chains that maximise the weighted sum of the objectives, the weights being decided by the desired product characteristics. The problem is solved through the proposed Taguchi-based DNA algorithm that draws its traits from random search optimisation and the statistical design of experiments. In order to minimise the effect of the causes of variations, the fundamental Taguchi method is integrated with the DNA-metaheuristic. The suggested methodology exhibits the global exploration capability to exploit the optimal or near-optimal DNA strands with a faster convergence rate. In order to authenticate the performance of the proposed solution methodology, a set of ten problem instances are considered and the results obtained are compared with that of the basic DNA, particle swarm optimisation (PSO) and its variant (PSO — time varying acceleration coefficients). The results demonstrate the benefits of the proposed algorithm for solving this type of problem.     

改进蚁群算法在物流配送路径中的应用

针对物流配送路径优化问题的特点,分析了基本蚁群算法的不足之处,并对原有蚁群算法进行改进.同时引入"扰动因子"和"奖惩"机制,建立数学模型,进而对物流配送车辆路径问题进行了实验仿真.结果表明,改进后的蚁群算法提高了全局寻优能力与收敛速度,取得了较好的效果.     

The coordinated production and transportation scheduling problem with a time-sensitive product: a branch-and-cut algorithm

In many supply chain scenarios in which short lifespan products are considered, production and transportation decisions must be made in a coordinated manner with no inventory stage. Hence, a solution to this problem conveys information about production starting times of each product lot at facility and delivery times of the lots to various customer-sites located in different geographic regions. In this paper, we study a variant of the problem that single product with limited shelf life is produced at single facility. Once produced, production lot is directly distributed to the customers with non-ignorable transportation time by single vehicle having limited capacity before the lifespan. Objective is to determine the minimum time required to produce and deliver all customer demands. To this end, we develop a branch-and-cut (B&C) algorithm using several valid inequalities adopted from the existing literature to improve lower bounds and applying a local search based on simulated annealing approach to improve upper bounds. On test problems available in the literature, we evaluate the performance of the B&C algorithm. Results show the promising performance of the B&C algorithm.     

Modelling of sustainable food grain supply chain distribution system: a bi-objective approach

Growing food demand, environmental degradation, post-harvest losses and the dearth of resources encourage the decision makers from developing nations to integrate the economic and environmental aspects in food supply chain network design. This paper aims to develop a bi-objective decision support model for sustainable food grain supply chain considering an entire network of procurement centres, central, state and district level warehouses, and fair price shops. The model seeks to minimise the cost and carbon dioxide emission simultaneously. The model covers several problem peculiarities such as multi-echelon, multi-period, multi-modal transportation, multiple sourcing and distribution, emission caused due to various motives, heterogeneous capacitated vehicles and limited availability, and capacitated warehouses. Multiple realistic problem instances are solved using the two Pareto based multi-objective algorithms. Sensitivity analysis results imply that the decision makers should establish a sufficient number of warehouses in each producing and consuming states by maintaining the suitable balance between the two objectives. Various policymakers like Food Corporation of India, logistics providers and state government agencies will be benefited from this research study.