A multi-point simulated annealing heuristic for solving multiple objective unrelated parallel machine scheduling problems

This study considers the problem of job scheduling on unrelated parallel machines. A multi-objective multi-point simulated annealing (MOMSA) algorithm was proposed for solving this problem by simultaneously minimising makespan, total weighted completion time and total weighted tardiness. To assess the performance of the proposed heuristic and compare it with that of several benchmark heuristics, the obtained sets of non-dominated solutions were assessed using four multi-objective performance indicators. The computational results demonstrated that the proposed heuristic markedly outperformed the benchmark heuristics in terms of the four performance indicators. The proposed MOMSA algorithm can provide a new benchmark for future research related to the unrelated parallel machine scheduling problem addressed in this study.     

Hybrid simulated annealing and reduced variable neighbourhood search for an aircraft scheduling and parking problem

Aircraft stands and runways at airports are critical airport resources for aircraft scheduling and parking. Making use of limited apron and runway resources to improve airport efficiency is becoming increasingly important. In this paper, we study a realistic Aircraft Scheduling and Parking Problem (ASPP) with the goal of simultaneously determining the takeoff and landing time of each aircraft with consideration for wake vortex effect constraints and parking positions in the limited parking apron at a target airport. The objective of the ASPP is to minimise the total service time for aircraft. We developed a mixed-integer linear programme formulation for the ASPP. A novel improved bottom-left/right strategy is applied to construct solutions and a Hybrid Simulated Annealing and Reduced Variable Neighborhood Search (HSARVNS) is proposed to identify near-optimal solutions. Numerical experiments on randomly generated ASPP instances and on a large set of benchmarks for a reduced version of the ASPP (i.e. the classical Two-Dimensional Strip-Packing Problem (2D-SPP)) demonstrate the effectiveness and efficiency of the proposed approach. For the ASPP, HSARVNS can find optimal solutions for small instances in a fraction of a second and can find high-quality solutions for instances with up to 250 aircraft within a reasonable timeframe. For the 2D-SPP, the HSARVNS can find optimal solutions for 32 of 38 tested benchmarks within 90 s on average.     

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.     

Comparing four metaheuristics for solving a constraint satisfaction problem for ship outfitting scheduling

This study compares the performance of four different metaheuristics for solving a constraint satisfaction scheduling problem of the outfitting process of shipbuilding. The ship outfitting process is often unorganised and chaotic due to the complex interactions between the stakeholders and the overall lack of sufficiently detailed planning. The examined methods are genetic algorithms (GA), simulated annealing (SA), genetic simulated annealing (GSA) and discrete particle swarm optimisation (PSO). Each of these methods relies on a list scheduling heuristic to transform the solution space into feasible schedules. Although the SA had the best performance for a medium-sized superstructure section, the GSA created the best schedules for engine room double-bottom sections, the most complex sections in terms of outfitting. The GA provided the best scalability in terms of computational time while only marginally sacrificing solution quality. The solution quality of the PSO was very poor in comparison with the other methods. All methods generated schedules with sufficiently high resource utilisation, approximately 95%. The findings from this work will be incorporated into a larger project with the aim of creating a tool which can automatically generate an outfitting planning for a vessel.     

Solving a stochastic berth allocation problem using a hybrid sequence pair-based simulated annealing algorithm

In this article, a continuous berth allocation problem is studied with stochastic ship arrival and handling times. The objective is to minimize a weighted sum of the expected waiting costs, berthing deviation costs and expected overtime costs. The sequence pair representation is utilized to project the solution space of the problem into two permutations. Then, a scenario-based method is used to capture the uncertainty. To effectively solve the problem over the sequence pair solution space, a simulated annealing is combined with two algorithms. One of the algorithms is used to determine the berthing positions and the other one is used to determine the berthing times. Computational experiments are conducted to evaluate the performance of the solution method and to verify the advantages of the proposed stochastic approach. The results indicate that the proposed methodology is both efficient and effective.     

A multi-objective optimisation model to integrating flexible process planning and scheduling based on hybrid multi-objective simulated annealing

Process planning and production scheduling play important roles in manufacturing systems. In this paper we present a mixed integer linear programming (MILP) scheduling model, that is to say a slot-based multi-objective multi-product, that readily accounts for sequence-dependent preparation times (transition and set up times or machine changeover time). The proposed scheduling model becomes computationally expensive to solve for long time horizons. The aim is to find a set of high-quality trade-off solutions. This is a combinatorial optimisation problem with substantially large solution space, suggesting that it is highly difficult to find the best solutions with the exact search method. To account for this, the hybrid multi-objective simulated annealing algorithm (MOHSA) is proposed by fully utilising the capability of the exploration search and fast convergence. Two numerical experiments have been performed to demonstrate the effectiveness and robustness of the proposed algorithm.     

Solving the dynamic berth allocation problem by simulated annealing

Berth allocation, the first operation when vessels arrive at a port, is one of the major container port optimization problems. From both the port operator's and the ocean carriers’ perspective, minimization of the time a ship spends at berth is a key goal of port operations. This article focuses on two versions of the dynamic berth allocation problem (DBAP): discrete and continuous cases. The first case assigns ships to a given set of berth positions; the second one permits them to be moored anywhere along the berth. Simulated annealing (SA) approaches are proposed to solve the DBAP. The proposed SAs are tested with numerical instances for different sizes from the literature. Experimental results show that the proposed SA can obtain the optimal solutions in all instances of discrete cases and update 27 best known solutions in the continuous case.     

Multi-objective optimization for the multi-mode finance-based project scheduling problem

The finance-based scheduling problem (FBSP) is about scheduling project activities without exceeding a credit line financing limit. The FBSP is extended to consider different execution modes that result in the multi-mode FBSP (MMFBSP). Unfortunately, researchers have abandoned the development of exact models to solve the FBSP and its extensions. Instead, researchers have heavily relied on the use of heuristics and meta-heuristics, which do not guarantee solution optimality. No exact models are available for contractors who look for optimal solutions to the multi-objective MMFBSP. CPLEX, which is an exact solver, has witnessed a significant decrease in its computation time. Moreover, its current version, CPLEX 12.9, solves multi-objective optimization problems. This study presents a mixed-integer linear programming model for the multi-objective MMFBSP. Using CPLEX 12.9, we discuss several techniques that researchers can use to optimize a multi-objective MMFBSP. We test our model by solving several problems from the literature. We also show how to solve multi-objective optimization problems by using CPLEX 12.9 and how computation time increases as problem size increases. The small increase in computation time compared with possible cost savings make exact models a must for practitioners. Moreover, the linear programming-relaxation of the model, which takes seconds, can provide an excellent lower bound.     

A new multi-objective optimization model for preventive maintenance and replacement scheduling of multi-component systems

In this article, a new multi-objective optimization model is developed to determine the optimal preventive maintenance and replacement schedules in a repairable and maintainable multi-component system. In this model, the planning horizon is divided into discrete and equally-sized periods in which three possible actions must be planned for each component, namely maintenance, replacement, or do nothing. The objective is to determine a plan of actions for each component in the system while minimizing the total cost and maximizing overall system reliability simultaneously over the planning horizon. Because of the complexity, combinatorial and highly nonlinear structure of the mathematical model, two metaheuristic solution methods, generational genetic algorithm, and a simulated annealing are applied to tackle the problem. The Pareto optimal solutions that provide good tradeoffs between the total cost and the overall reliability of the system can be obtained by the solution approach. Such a modeling approach should be useful for maintenance planners and engineers tasked with the problem of developing recommended maintenance plans for complex systems of components.     

Selective maintenance scheduling under stochastic maintenance quality with multiple maintenance actions

Many systems are required to perform a series of missions with finite breaks between any two consecutive missions. To improve the probability of system successfully completing the next mission, maintenance action is carried out on components during the breaks. In this work, a selective maintenance model with stochastic maintenance quality for multi-component systems is investigated. At each scheduled break, a set of maintenance actions with different degrees of impact are available for each component. The impact of a maintenance action is assumed to be random and follow an identified probability distribution. The corresponding maintenance cost and time are modelled based on the expected impact of the maintenance action. The objective of selective maintenance scheduling is to find the cost-optimal maintenance action for each component at every scheduled break subject to reliability and duration constraints. A simulated annealing algorithm is used to solve the complicated optimisation problem where both multiple maintenance actions and stochastic quality model are taken into account. Two illustrative numerical examples and a real case study have been solved to demonstrate the performance of the proposed approach. A comparison with deterministic maintenance shows the importance of considering the proposed stochastic quality in selective maintenance scheduling.     

Modelling and optimization of a bi-objective flow shop scheduling with diverse maintenance requirements

In real-world problems, machines cannot continuously operate and have to stop for maintenance before they fail. Lack of maintenance can also affect the performance of machines in processing jobs. In this paper, a permutation flow shop scheduling problem with multiple age-based maintenance requirements is modelled as a novel mixed-integer linear program in which the objectives are conflicting. In modelling the problem, we assume that infrequent maintenance can prolong job processing times. One of the objectives is to minimise the total maintenance cost by planning as few maintenance activities as possible to only meet the minimum requirements, and the other objective tries to minimise the total tardiness by sequencing the jobs and planning the maintenance activities in such a way that the processing times are not prolonged and unnecessary maintenance times are avoided. Because of this conflict, an interactive fuzzy, bi-objective model is introduced. Application of the model is illustrated through a case study for operations and maintenance scheduling of heavy construction machinery. An effective and efficient solution methodology is developed based on the structure of the problem and tested against commercial solvers and a standard GA. Computational results have verified the efficiency of the proposed solution methodology and show that unlike the proposed method, a generic metaheuristic that does not consider the unique structure of the problem can become ineffective for real-world problem sizes.     

Reliability-based maintenance and job scheduling for identical parallel machines

Quality has an important role in manufacturing, and on the other hand, machine condition has a significant effect on quality. Based on this fact, all manufacturers integrate the production scheduling with maintenance activities to keep the machines in perfect conditions. In this paper, we propose a mixed integer nonlinear model to optimise the quality cost, maintenance cost, earliness–tardiness cost and interruption cost simultaneously. We assume that if machines work in undesirable conditions, their quality is reduced, resulting in quality cost. On the other hand, if the machines are repaired to decrease the quality cost, maintenance cost and other cost such as earliness–tardiness cost and interruption cost are imposed to the manufacturer. Several numerical instances are implemented by the proposed model to show the model effectiveness to obtain the best maintenance and production scheduling with minimum quality cost.     

Applying a hybrid simulated annealing and tabu search approach to non-permutation flowshop scheduling problems

Researchers have indicated that a permutation schedule can be improved by a non-permutation schedule in a flowshop with completion time-based criteria, such as makespan and total completion time. This study proposes a hybrid approach which draws on the advantages of simulated annealing and tabu search for the non-permutation flowshop scheduling problem, in which the objective function is the makespan of the schedule. To verify the effectiveness of the proposed hybrid approach, computational experiments are performed on a set of well-known non-permutation flowshop scheduling benchmark problems. The result shows that the performance of the hybrid approach is better than that of other approaches, including ant colony optimisation, simulated annealing, and tabu search. Further, the proposed approach found new upper bound values for all benchmark problems within a reasonable computational time.     

The influence of condition-based maintenance on workforce planning and maintenance scheduling

Condition-based maintenance (CBM) is generally considered an attractive maintenance policy for a single component: it uses the operating condition of the component to predict a failure event and therefore tries to avoid any unplanned downtime and unnecessary maintenance activities. However, operations managers tend to be much more interested in optimising the performance of the entire asset-system, where the grouping of maintenance activities and the availability of maintenance workers may play a role. Therefore, this paper focuses on the impact of using either CBM or age-based replacement (ABR) in serial and parallel multi-component systems (1) without worker constraints, (2) with a single internal maintenance worker, and (3) with external maintenance workers with a significant response time. With an internal maintenance worker, the sequential execution of maintenance activities prevents efficiency gains in the serial configuration and here CBM performs better. Also in the parallel configurations, the efficiency under CBM is generally better than under ABR. However, with external maintenance workers, CBM is not able to group maintenance activities as well as ABR, which results in a lower efficiency in the serial configuration. CBM performs better than ABR with respect to total maintenance costs, while ABR results in a smoother maintenance plan.     

Application of chance-constrained programming based on multi-objective simulated annealing to solve a mineral blending problem

This paper addresses the optimal blending of different available ores in such a way that the total expected cost of buying ore is minimized while satisfying the quality specifications. The risk limitation criterion used consists of the simultaneous minimization of the variance of the total cost. The problem is solved by Chance-Constrained Programming (CCP) based on multi-objective simulated annealing. The technique is able to deal with the stochastic nature of the variables in the blending problem. In generic form the objectives are to minimize expected value and standard deviation of cost in such a way as to meet the blend requirements within the specified reliability level. The variability of each variable in each flow is quantified by semi-variograms. Each flow is simulated to reproduce the characteristics, or behaviour, of the phenomenon as observed in the available data. The expected value of each variable in each flow is calculated by averaging of the simulated values. The problem expressed in terms of CCP is transformed into an appropriate deterministic equivalent, which is a non-linear optimization problem. The new form of the problem is solved by multi-objective simulated annealing. A case study is carried out to demonstrate the technique. The problem is formulated in terms of iron, silica and alumina grades with four ore sources. Pros and cons of the technique are discussed.     

Multi-objective evolutionary simulated annealing optimisation for mixed-model multi-robotic disassembly line balancing with interval processing time

This paper considers the design and balancing of mixed-model disassembly lines with multi-robotic workstations under uncertainty. Tasks of different models are performed simultaneously by the robots which have different capacities for disassembly. The robots have unidentical task times and energy consumption respectively. Task precedence diagrams are used to model the precedence relations among tasks. Considering uncertainties in disassembly process, the task processing times are assumed to be interval numbers. A mixed-integer mathematical programming model is proposed to minimise the cycle time, peak workstation energy consumption, and total energy consumption. This model has a significant managerial implication in real-life disassembly line systems. Since the studied problem is known as NP-hard, a metaheuristic approach based on an evolutionary simulated annealing algorithm is developed. Computational experiments are conducted and the results demonstrate the proposed algorithm outperforms other multi-objective algorithms on optimisation quality and computational efficiency.     

A bi-objective parallel machine problem with eligibility,release dates and delivery times of the jobs

The scheduling of parallel machines is a well-known problem in many companies. Nevertheless, not always all the jobs can be manufactured in any machine and the eligibility appears. Based on a real-life problem, we present a model which has m parallel machines with different level of quality from the highest level for the first machine till the lowest level for the last machine. The set of jobs to be scheduled on these m parallel machines are also distributed among these m levels: one job from a level can be manufactured in a machine of the same or higher level but a penalty, depending on the level, appears when a job is manufactured in a machine different from the highest level i.e. different from the first machine. Besides, there are release dates and delivery times associated to each job. The tackled problem is bi-objective with the criteria: minimisation of the final date – i.e. the maximum for all the jobs of their completion time plus the delivery time – and the minimisation of the total penalty generated by the jobs. In a first step, we analyse the sub-problem of minimisation of the final date on a single machine for jobs with release dates and delivery times. Four heuristics and an improvement algorithm are proposed and compared on didactic examples and on a large set of instances. In a second step an algorithm is proposed to approximate the set of efficient solutions and the Pareto front of the bi-objective problem. This algorithm contains two phases: the first is a depth search phase and the second is a backtracking phase. The procedure is illustrated in detail on an instance with 20 jobs and 3 machines. Then extensive numerical experiments are realised on two different sets of instances, with 20, 30 and 50 jobs, 3 or 4 machines and various values of penalties. Except for the case of 50 jobs, the results are compared with the exact Pareto front.     

Multi-objective flow-shop scheduling with parallel machines

In this paper, multi-objective flow-shop scheduling with parallel machines is considered, and an algorithm for production-scheduling optimisation is proposed. The objective is to design an algorithm to optimise production scheduling, taking into consideration customer changes to delivery dates and quantities, materials requisitioned from the supplier and inventory management. Manufacturing lead time for the production order is minimised, and, finally, resource use is considered as an auxiliary criterion. Numerical examples, modelled with data from a Mexican enterprise, and computational results are reported. The paper indicates that the mathematical model, as well as the program that solves it, provides flexibility with minimum modifications. Thus it can provide useful information for multiple decision processes.     

A multi-objective simulated annealing approach to reactive power compensation

Reactive power compensation is an important problem in electrical distribution systems, involving the sizing and location of capacitors (sources of reactive power). The installation of capacitors also contributes to releasing system capacity and improving voltage level. A multi-objective simulated annealing approach to provide decision support in this problem is presented. This approach is able to compute a set of well-distributed and diversified solutions underlying distinct trade-offs, even for a challenging network. The characterization of the non-dominated front is relevant information for aiding planning engineers to select satisfactory compromise solutions (compensation schemes) to improve the network operation conditions.     

The equipment maintenance scheduling problem in a coal production system

This paper addresses an equipment maintenance scheduling problem in a coal production system which includes three consecutive stages: the coal mining stage, the coal washing stage and the coal loading stage. Each stage is composed of different equipment that needs maintenance each day. There exists intermediate storage with finite capacities and the finished products are transported by train. Moreover, some equipment has a different preference for (aversion to) the start time of maintenance (STOM). The objective is to minimise the weighted sum of aversion about STOM, changeover times and train waiting time. We first formulate this problem into a mixed integer linear programming (MILP) model, then a hybrid genetic algorithm (HGA) is proposed to solve it. The proposed method has been tested on a practical coal enterprise in China and some randomly generated instances. Computational results indicate that our algorithm can produce near-optimal solutions efficiently.