Assigning licenced technicians to maintenance tasks at aircraft maintenance base: a bi-objective approach and a Chinese airline application

Assigning technicians to maintenance tasks at an aircraft maintenance base is challenging and needs to consider technician licences, fairness and such operational constraints as hangar capacity and work shifts. We formulate the problem as a bi-objective optimisation model, which minimises total cost while simultaneously achieving fairness in workload allocation among different technicians. A tabu-based heuristic algorithm is developed to obtain Pareto efficient solutions. The algorithm is shown to be effective through comparison with CPLEX. A case study from a major Chinese airline demonstrates that our optimisation-based approach is applicable and beneficial to the practice. Managerial issues on maintenance workforce management are examined as well. The results show that training technicians and upgrading their licences may not be better off, and increasing the number of technicians has both favourable and unfavourable effects.     

A new medical staff allocation via simulation optimisation for an emergency department in Hong Kong

Whether triage targets can be achieved has been an imperative assessment of service qualities for an emergency department in healthcare management. In this research, we focus on triage targets and try to fully meet the target of fast emergency response for critical patients subject to triage requirements for other category patients by optimising the medical staff allocation in the emergency department. Main challenges stem from multiple stochastic constraints and the time-consuming simulation. To solve the stochastically constrained discrete optimisation via simulation problem, we develop a discrete-event simulation model and propose a simulated-annealing-based algorithm called ConSA that adopts a special searching mechanism and an efficient simulation budget allocation rule to find a high-quality configuration of medical staff. A case study based on the data from a public hospital in Hong Kong is carried out. Numerical experiments demonstrate that our algorithm leads to a 38.28% improvement in the main performance compared to the current staff allocation and dominates other algorithms in terms of computational efficiency and output accuracy. It indicates that our method is a good decision tool for hospital managers.     

A bi-objective robust model for emergency resource allocation under uncertainty

Emergency resource allocation constitutes one of the most critical elements of response operations in the field of emergency management. This paper addresses an emergency resource allocation problem which involves multiple competing affected areas and one relief resource centre under supply shortage and uncertainty in the post-disaster phase. In humanitarian situations, both the efficiency and fairness of an allocation policy have a considerable influence on the effectiveness of emergency response operations. Thus, we formulate a bi-objective robust emergency resource allocation (BRERA) model which tries to maximise efficiency as well as fairness under different sources of uncertainties. To obtain decision-makers’ most preferred allocation policy, we propose a novel emergency resource allocation decision method which consists of three steps: (1) develop a bi-objective heuristic particle swarm optimisation algorithm to search the Pareto frontier of the BRERA model; (2) select a coefficient to measure fairness; and (3) establish a decision method based on decision-makers’ preference restricted by the fairness coefficient. Finally, a real case study taken from the 5 December 2008 Wenchuan Earthquake demonstrates the effectiveness of the proposed method through numerical results. The solution and model robustness are also analysed.     

An ant colony optimisation algorithm for scheduling in agile manufacturing

Producing customised products in a short time at low cost is one of the goals of agile manufacturing. To achieve this goal an assembly-driven differentiation strategy has been proposed in the agile manufacturing literature. In this paper, we address a manufacturing system that applies the assembly-driven differentiation strategy. The system consists of machining and assembly stages, where there is a single machine at the machining stage and multiple identical assembly stations at the assembly stage. An ant colony optimisation (ACO) algorithm is developed for solving the scheduling problem of determining the sequence of parts to be produced in the system so as to minimise the maximum completion time (or makespan). The ACO algorithm uses a new dispatching rule as the heuristic desirability and variable neighbourhood search as the local search to make it more efficient and effective. To evaluate the performance of heuristic algorithms, a branch-and-bound procedure is proposed for deriving the optimal solution to the problem. Computational results show that the proposed ACO algorithm is superior to the existing algorithm, not only improving the performance but also decreasing the computation time.     

Backorder minimization in multiproduct assemble-to-order systems

We consider a multiproduct assemble-to-order system. Components are built to stock with inventory controlled by base-stock rules, but the final products are assembled to order. Customer orders of each product follow a batch Poisson process. The leadtimes for replenishing component inventory are stochastic. We study the optimal allocation of a given budget among component inventories so as to minimize a weighted average of backorders over product types. We derive easy-to-compute bounds and approximations for the expected number of backorders and use them to formulate surrogate optimization problems. Efficient algorithms are developed to solve these problems, and numerical examples illustrate the effectiveness of the bounds and approximations.     

Managing two-stage serial inventory systems under demand and supply uncertainty and customer service level requirements

We consider a two-echelon serial inventory system with demand and supply uncertainty, non-zero lead times for component procurement and end-product assembly, and a minimum customer service level requirement. We present two supply models which incorporate both quantity and timing uncertainty; these models correspond to current and proposed supply environments. Assuming that installation base-stock ordering policies are followed and that the demand distribution is quasi-concave, we show that the chance-constrained problem of determining optimal base-stock levels which minimize the total inventory investment (cost-weighted stock levels) subject to a service constraint is a convex programming problem. We characterize the relation between the optimal base-stock levels of the component and the end-product. We also illustrate how an optimal internal (component) service level can be computed, which permits decomposition of the two-stage serial system into two coordinated single-echelon systems. Computational experiments illustrate insights on the effects of supply uncertainty and other problem parameters on stock-positioning in a two-echelon serial system. In particular, we evaluate the benefits of switching from one supply environment to another.     

Capacitated disassembly scheduling with random demand

This paper considers disassembly scheduling, which is the problem of determining the quantity and timing of the end-of-use/life products to be disassembled while satisfying the demand for their parts obtained from disassembling the products over a planning horizon. This paper focuses on the problem with stochastic demand of parts/modules, capacity restrictions on disassembly resources, and multiple product types with a two-level product structure. The two-level product structure implies that an end-of-use/life product is hierarchically decomposed into two levels where the first level corresponds to the parts/modules and the second level corresponds to the product. We formulate the problem as a stochastic inventory model and to solve the problem we propose a Lagrangian heuristic algorithm as well as an optimisation algorithm for the sub-problems obtained from Lagrangian decomposition. The test results on randomly generated problems show that the Lagrangian heuristic algorithm demonstrates good performance in terms of solution quality and time.     

The integration of resource allocation and time buffering for bi-objective robust project scheduling

In the recent decades, the recognition that uncertainty lies at the heart of modern project management has induced considerable research efforts on robust project scheduling for dealing with uncertainty in a scheduling environment. The literature generally provides two main strategies for the development of a robust predictive project schedule, namely robust resource allocation and time buffering. Yet, the previous studies seem to have neglected the potential benefits of an integration between the two. Besides, few efforts have been made to protect simultaneously the project due date and the activity start times against disruptions during execution, which is desperately demanded in practice. In this paper, we aim at constructing a proactive schedule that is not only short in time but also less vulnerable to disruptions. Firstly, a bi-objective optimisation model with a proper normalisation of the two components is proposed in the presence of activity duration variability. Then a two-stage heuristic algorithm is developed which deals with a robust resource allocation problem in the first stage and optimally determines the position and the size of time buffers using a simulated annealing algorithm in the second stage. Finally, an extensive computational experiment on the PSPLIB network instances demonstrates the superiority of the combination between resource allocation and time buffering as well as the effectiveness of the proposed two-stage algorithm for generating proactive project schedules with composite robustness.     

An MILP model and a hybrid evolutionary algorithm for integrated operation optimisation of multi-head surface mounting machines in PCB assembly

This paper focuses on an operation optimisation problem for a class of multi-head surface mounting machines in printed circuit board assembly lines. The problem involves five interrelated sub-problems: assigning nozzle types as well as components to heads, assigning feeders to slots and determining component pickup and placement sequences. According to the depth of making decisions, the sub-problems are first classified into two layers. Based on the classification, a two-stage mixed-integer linear programming (MILP) is developed to describe it and a two-stage problem-solving frame with a hybrid evolutionary algorithm (HEA) is proposed. In the first stage, a constructive heuristic is developed to determine the set of nozzle types assigned to each head and the total number of assembly cycles; in the second stage, constructive heuristics, an evolutionary algorithm with two evolutionary operators and a tabu search (TS) with multiple neighbourhoods are combined to solve all the sub-problems simultaneously, where the results obtained in the first stage are taken as constraints. Computational experiments show that the HEA can obtain good near-optimal solutions for small size instances when compared with an optimal solver, Cplex, and can provide better results when compared with a TS and an EA for actual instances.     

Dynamic scheduling of oil tankers with splitting of cargo at pickup and delivery locations: a Multi-objective Ant Colony-based approach

Maritime crude oil transportation problem have been drawing the attention of researchers for quite a long time. The cost incurred in the supply chain for the oil products is one of the biggest driving factors for these researchers. In the present paper, we have addressed the problem faced by the logistics section of the petroleum downstream industry. This industry mainly deals with the transportation of finished oil products like fuel oil, high speed diesel, etc. from refineries to the demand points. For this purpose, we have developed a mathematical model to represent the problem appropriately, aiming at total cost minimisation as well as service-level maximisation. The problem in hand is then tackled with a modified Multi-objective Ant Colony optimisation algorithm which besides considering more than one pheromone structure also involves non-dominated sorting of the results to give us the best-performing solution fronts. For the purpose of dealing with the uncertainties causing docking problems at a port, we have incorporated a second stage of route allocation for the vessels. Towards the end, we have carried out a sensitivity analysis for the parameters of the ant colony algorithm to get the combination of parameters for which this new type of algorithm performs best. The comparison of obtained results with one of the other contemporary algorithms also establishes the superiority of our heuristic.     

Clamping-sequence optimisation based on heuristic algorithm for sheet-metal components

The traditional clamping-sequence optimisation of sheet-metal parts requires many complicated finite element analyses, and clamping-sequence planning does not account for the springback from clamp-release. Therefore, this paper proposes a new optimisation method based on a heuristic algorithm. We first propose a new contact model of parts, clamps and supporting locators to analyse assembly deformation. Then, we use the distance between the actual and nominal positions to evaluate the clamp layout. Finally, we apply the heuristic algorithm to optimise the clamping sequence. We illustrate the proposed method with a case study of a taillight bracket, whose results show that the method of clamping-sequence optimisation can effectively decrease the deformation of sheet metal from clamping.     

Optimal vehicle allocation for an Automated Materials Handling System using simulation optimisation

The Automated Materials Handling System (AMHS) in the semiconductor industry plays a vital role in reducing wafer cycle times and enhancing fabrication facility (fab) productivity. Due to the complexity of the manufacturing process and the stochasticity introduced by the inherent variability of processing times, the vehicle allocation for the AMHS is a challenging task, especially in 300?mm?wafer fabs where the AMHS comprises both the interbay and intrabay systems to perform the timely deliveries. This paper studied the vehicle allocation problem in a typical 300?mm?wafer fab. We formulated it as a simulation optimisation problem and proposed a conceptual framework to handle the problem. A discrete event simulation model was developed to characterise the AMHS, and the technique of simulation optimisation was applied to obtain the optimal vehicle allocation for both the interbay and intrabay systems. To demonstrate the feasibility and advantages of the simulation optimisation approach, a photobay example was used to compare the solution derived from the analytical model and simulation optimisation model. Finally, an empirical problem based on real data was conducted to show the viability of the proposed framework in practice.     

Biogeography-based optimisation for flexible manufacturing system scheduling problem

Biogeography-based optimisation (BBO) algorithm is a new evolutionary optimisation algorithm based on geographic distribution of biological organisms. With probabilistic operators, this algorithm is able to share more information from good solutions to poor ones. BBO prevents the good solutions to be demolished during the evolution. This feature leads to find the better solutions in a short time rather than other metaheuristics. This paper provides a mathematical model which integrates machine loading, part routing, sequencing and scheduling decision in flexible manufacturing systems (FMS). Moreover, it tackles the scheduling problem when various constraints are imposed on the system. Since this problem is considered to be NP-hard, BBO algorithm is developed to find the optimum /near optimum solution based on various constraints. In the proposed algorithm, different types of mutation operators are employed to enhance the diversity among the population. The proposed BBO has been applied to the instances with different size and degrees of complexity of problem adopted from the FMS literature. The experimental results demonstrate the effectiveness of the proposed algorithm to find optimum /near optimum solutions within reasonable time. Therefore, BBO algorithm can be used as a useful solution for optimisation in various industrial applications within a reasonable computation time.     

Optimisation of beam directions in intensity modulated radiation therapy planning

Abstract. In this paper we consider the problem of selecting optimal beam directions as well as optimal intensity profiles for radiation therapy. Our multiobjective mixed integer programming problem is based on and extends a multiobjective LP formulation for intensity optimisation by Hamacher and Küfer. We use a weighted sum scalarisation to explore the benefits of beam direction optimisation. We propose exact and heuristic methods for solving the problem and present some numerical results. Correspondence to: M. Ehrgott     

Soft constraint handling for a real-world multiobjective energy distribution problem

Real-world optimisation problems usually involve some conflicting objectives and a number of constraints. In such cases, finding a feasible, Pareto-optimal solution poses a demanding challenge. In reality, constraints bear different importance levels to these conflicting objectives. If some constraints are relaxed within an acceptable degree, quality infeasible solutions could be found on the boundary from the infeasible side of the searching region. This paper formulates an energy distribution problem arising from a real-world iron and steel production as a multiobjective optimisation problem. During the course of the optimisation search, this paper attempts to handle certain constraints in a soft manner to find solutions with good balance among objective and constraints violation. Based on the analysis of constraints from the real-world perspective, different tolerance values are defined. The proposed constraint violation degree-based soft handling approach is incorporated into the advanced version of non-dominated sorting genetic algorithm framework, as a case study, to examine the efficiency of the proposed soft constraint handling approach for a real-world energy distribution problem. The proposed approach is also implemented in different ways of constraint handling and tested on some benchmark functions to further demonstrate the performance of soft constraint handling for multiobjective optimisation problems.     

Lot size optimisation under pooled and unpooled scenarios in batch production system

The lot-sizing problem in batch manufacturing systems with capacity constraints is studied using queueing relationships and optimisation techniques. In this research, the effect of lot sizes when there are parallel machines and multiple part types is considered. Furthermore, the issue of whether or not to use pooled queues, based on part types, to feed the machines is examined. Different scenarios are evaluated using GI/G/n queueing approximations to predict performance and optimise lot sizes. Optimisation is based on minimising the mean flowtimes, which include queue and lot service times. The results show that if part types are very different, there are situations in which pooling is not advantageous.     

Many-objective harmony search for integrated order planning in steelmaking-continuous casting-hot rolling production of multi-plants

This paper investigates a challenging problem of integrated order planning (IOP) in steelmaking-continuous casting-hot rolling production of multiple plants with consideration of four conflicting objectives. The objective functions refer to the earliness/tardiness ratio, the non-hot charge ratio and the imbalance ratio of production capacity utilisation corresponding to SCC plants and HR Plants. The IOP guided by the integration strategy, which includes the vertical integration of production stages and the horizontal integration of steel plants, is regarded as a large-scale many-objective optimisation problem. To deal with the difficulty of large-scale decision variables, we introduce a new concept named ‘order-set’ for modelling. In addition, a novel knee point-driven many-objective global-best harmony search (KGHS) algorithm, mainly integrating a KGHS process and a new knee point-driven Pareto optimisation, is developed to tackle this many-objective problem. The proposed model and algorithm were tested with benchmarks and real production data. Experiments demonstrate that the proposed approach generates effective solutions superior to those generated by the other popular many-objective optimisation methods.     

An MILP model and clustering heuristics for LED assembly optimisation on high-speed hybrid pick-and-place machines

This paper deals with a scheduling optimisation problem arising in printed circuit board (PCB) assembly. In one class of PCB assembly, light-emitting diodes are to be assembled into the placement locations on PCBs by a machine with multiple pick-and-place heads. The scheduling optimisation problem is to determine the assembly sequence of placement locations and the assignment of pick-and-place heads for locations so as to minimise the assembly time. We formulate it as a mixed integer linear programming model. To solve the problem efficiently, we classify the PCBs into two types. For the first type of PCBs, on which the locations are linearly arranged, a constructive heuristic is proposed based on the analysis of the best next location after a location is assembled. For the second type of PCBs, on which the locations are circularly arranged, a heuristic based on clustering strategy and path relinking method is proposed. Computational experiments show that the solutions obtained by the two heuristics make 2.32 and 6.82% improvements averagely for the PCBs with linearly and circularly arranged locations, respectively, as compared to the solutions used in real production, and they are also better than those obtained by a hybrid genetic algorithm.     

A general corridor method-based approach for capacitated facility location

The Capacitated Facility Location Problem (CFLP) is a well-known optimisation problem with applications in a number of fields, such as distribution system planning, telecommunication network design, and supply chain design. The goal of this paper is to present a matheuristic algorithm based on the corridor method, to develop a general algorithm for a number of variants of the CFLP. The algorithm exploits solutions obtained via Lagrangean relaxation and builds corridors around such solutions via the introduction of constraints around the incumbent solution, used to limit the size of the solution space explored at each iteration. A thorough exploration of the neighbourhoods induced by the corridors is carried out using a mixed integer programming (MIP) solver. More precisely, we solve to (near) optimality over 500 benchmark instances, using the single-source as well as the multi-source formulations, both in the nominal variant, i.e. the deterministic version of the problem, and the robust variant, i.e. the version obtained when using robust optimisation to model the uncertainty of the problem parameters. The performance of the algorithm is highly competitive when compared with the best approaches proposed in the literature for each variant of the CFLP, especially considering that the algorithm has not been designed with a specific CFLP formulation in mind.     

Solving coupled task assignment and capacity planning problems for a job shop by using a concurrent genetic algorithm

The problems of task assignment and capacity planning of manufacturing systems have been researched for many years. However, in the existing literature, these two types of problems are researched independently. Namely, when solving the task assignment problem, it is usually assumed that the production capacity of the manufacturing systems has been determined. On the other hand, when solving the capacity planning problem, the production tasks assigned to the workstations in the manufacturing system have also been determined. Actually, the task assignment problem and the capacity planning problem are coupled with each other. When we assign production tasks to workstations, production capacities of these workstations should be regulated so that they are enough for completing the tasks. At the same time, when planning the production capacity, we must know what production tasks are assigned to what workstations. This research focuses on the coupling relations between the two problems for a closed job shop, in which the total work-in-process (WIP) is assumed to be constant. The objective of the task assignment problem is to balance the workloads of the workstations and the objectives of the capacity planning problem are maximising the throughput and minimising total costs of machine purchasing and WIP inventory. We construct the fundamental system architecture for controlling the two coupled optimisation processes, and propose a concurrent genetic algorithm (CGA) to solve the two coupled optimisation problems. The influences of the decision variables of one problem on the objective function of the other problem are taken into consideration when the fitness functions of the CGA are constructed. Numerical experiments are done to verify the effectiveness of the algorithm.