A knowledgeable simulated annealing scheme for the early/tardy flow shop scheduling problem

The present paper reports on a new approach to applying simulated annealing to the flow shop scheduling problem with early/tardy costs. This approach incorporates the simulated annealing methodology with problem-specific knowledge, which is given in a table called the ‘Backward-Forward Exchange Priority Table’. Performance of the proposed method is tested on randomly generated problems and is compared to those of two formal simulated annealing schemes. Finally, it is shown that solutions obtained by the proposed method are superior to those of formal annealing schemes.     

Multi-threaded simulated annealing for a bi-objective maintenance scheduling problem

A parallel Simulated Annealing algorithm with multi-threaded architecture is proposed to solve a real bi-objective maintenance scheduling problem with conflicting objectives: the minimisation of the total equipment downtime caused by maintenance jobs and the minimisation of the multi-skilled workforce requirements over the given horizon. The maintenance jobs have different priorities with some precedence relations between different skills. The total weighted flow time is used as a scheduling criterion to measure the equipment availability. The multi-threaded architecture is used to speed up a multi-objective Simulated Annealing algorithm to solve the considered problem. Multi-threading is a form of parallelism based on shared memory architecture where multiple logical processing units, so-called threads, run concurrently and communicate via shared memory. The performance of the parallel method compared to the exact method is verified using a number of test problems. The obtained results imply the high efficiency and robustness of the proposed heuristic for both solution quality and computational effort.     

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.     

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.     

Resource-constrained project scheduling by simulated annealing

This paper presents a new adaptation of the simulated annealing algorithm for solving non-preemptive resource-constrained project scheduling problems in which resources are limited but renewable from period to period. This algorithm is able to handle single-mode and multi-mode problems and to optimize different objective functions. Statistical experiments show the efficiency of the proposed algorithm even in comparison to some Tabu search heuristics.     

A simulated annealing solution to the cell formation problem

This research develops a simulated annealing (SA) based heuristic for cell formation problems. We apply the SA based heuristic to many popular examples for cell formation problems. The computational results show that the SA based heuristic performs very well in all these examples, and the SA based heuristic has several advantages that most of the existing algorithms do not have.     

An improved approximation algorithm for the two-machine open shop scheduling problem with family setup times

We consider the problem of scheduling families of jobs in a two-machine open shop so as to minimize the makespan. The jobs of each family can be partitioned into batches and a family setup time on each machine is required before the first job is processed, and when a machine switches from processing a job of some family to a job of another family. For this NP-hard problem the literature contains (5/4)-approximation algorithms that cannot be improved on using the class of group technology algorithms in which each family is kept as a single batch. We demonstrate that there is no advantage in splitting a family more than once. We present an algorithm that splits one family at most once on a machine and delivers a worst-case performance ratio of 6/5.     

A study on open shop scheduling to minimise total tardiness

This paper deals with open shop scheduling to minimise total tardiness. Contrary to other scheduling problems (i.e., flow and job shops), the formulation of the open shop is given far less attention in the literature. Therefore, we intend to fulfil this gap by the presentation of four different mixed integer linear programming models. We compare the models on the basis of their complexity sizes. Furthermore, we propose two metaheuristics based on genetic algorithm and variable neighbourhood search. We exhaustively explore the effect of different operators and parameters on the performance of genetic algorithm by means of Taguchi method. Two computational experiments are conducted to evaluate the models and algorithms for performance. The first one includes small-sized instances by which the models and general performance of the algorithms are examined. The second one consists of three well-known benchmarks by which we further evaluate the algorithms. The results show the effectiveness of the proposed models and algorithms.     

Open shop scheduling problem to minimize total weighted completion time

A given number of jobs in an open shop scheduling environment must each be processed for given amounts of time on each of a given set of machines in an arbitrary sequence. This study aims to achieve a schedule that minimizes total weighted completion time. Owing to the strong NP-hardness of the problem, the weighted shortest processing time block (WSPTB) heuristic is presented to obtain approximate solutions for large-scale problems. Performance analysis proves the asymptotic optimality of the WSPTB heuristic in the sense of probability limits. The largest weight block rule is provided to seek optimal schedules in polynomial time for a special case. A hybrid discrete differential evolution algorithm is designed to obtain high-quality solutions for moderate-scale problems. Simulation experiments demonstrate the effectiveness of the proposed algorithms.     

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.     

Cultural algorithms,an alternative heuristic to solve the job shop scheduling problem

In this work, an approach for solving the job shop scheduling problem using a cultural algorithm is proposed. Cultural algorithms are evolutionary computation methods that extract domain knowledge during the evolutionary process. Additional to this extracted knowledge, the proposed approach also uses domain knowledge given a priori (based on specific domain knowledge available for the job shop scheduling problem). The proposed approach is compared with respect to a Greedy Randomized Adaptive Search Procedure (GRASP), a Parallel GRASP, a Genetic Algorithm, a Hybrid Genetic Algorithm, and a deterministic method called shifting bottleneck. The cultural algorithm proposed in this article is able to produce competitive results with respect to the two approaches previously indicated at a significantly lower computational cost than at least one of them and without using any sort of parallel processing.     

Applying tabu search and simulated annealing to the optimal design of sewer networks

Optimizations of sewer network designs create complicated and highly nonlinear problems wherein conventional optimization techniques often get easily bogged down in local optima and cannot successfully address such problems. In the past decades, heuristic algorithms possessing robust and efficient global search capabilities have helped to solve continuous and discrete optimization problems and have demonstrated considerable promise. This study applied tabu search (TS) and simulated annealing (SA) to the optimization of sewer network designs. For a case study, this article used the sewer network design of a central Taiwan township, which contains significantly varied elevations, and the optimal designs from TS and SA were compared with the original official design. The results show that, in contrast with the original design's failure to satisfy the minimum flow-velocity requirements, both TS and SA achieved least-cost solutions that also fulfilled all the constraints of the design criteria. According to the average performance of 200 trials, SA outperformed TS in both robustness and efficiency for solving sewer network optimization problems.     

作业车间调度问题中的协同优化算法

本文采用了多种优化算法 ,针对作业车间问题的特点设计一个比较有效的协同算法 ,解决了算法实现中的几个关键技术问题 ,为提高解决这一问题的效率提供了比较新颖的思路 ,并通过实际计算验证了该方法的可靠性和有效性 ,这一方法可以用于实际车间的调度安排 ,能够提高车间的生产效率。     

Sequence-dependent setup time flexible job shop scheduling problem to minimise total tardiness

This paper studies the problem of scheduling flexible job shops with setup times where the setups are sequence-dependent. The objective is to find the schedule with minimum total tardiness. First, the paper develops a mathematical model in the form of mixed integer linear programming and compares it with the available model in the literature. The proposed model outperforms the available model in terms of both size complexity and computational complexity. Then, an effective metaheuristic algorithm based on iterated local search is proposed and compared with a tabu search and variable neighbourhood search algorithms proposed previously for the same problem. A complete experiment is conducted to evaluate the algorithms for performance. All the results show the superiority of the proposed algorithm against the available ones.     

A two-machine permutation flow shop scheduling problem with buffers

Problems with blocking (limited intermediate storage space) are used frequently for modelling and scheduling just-in-time and flexible manufacturing systems. In this paper, an approximation algorithm is presented for the problem of finding the minimum makespan in a two-machine permutation flow-shop scheduling problem with the mediating buffer of finite capacity. The algorithm is based on the tabu search approach supported by the reduced neighborhood, search accelerator and technique of back jumps on the search trajectory. Due to some special properties, the proposed algorithm provides makespans very close to optimal in a short time. It has been shown that this algorithm outperforms all known approximation algorithms for the problem stated.     

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.     

Fuzzy-metaheuristic methods to solve a hybrid flow shop scheduling problem with pre-assignment

This paper deals with a particular version of the hybrid flow shop scheduling problem inspired from a real application in the automotive industry. Specific constraints such as pre-assigned jobs, non-identical parallel machines and non-compatibility between certain jobs and machines are considered in order to minimise the total tardiness time. A mixed-integer programming model that incorporates these aspects is developed and solved using ILOG Cplex software. Thus, because of the computation time constraint, we propose approximate resolution methods based on genetic and particle swarm optimisation algorithms coupled or not with fuzzy logic control. The effectiveness of these methods is investigated via computational experiments based on theoretical and real case instances. The obtained results show that fuzzy logic control improves the performances of both genetic and particle swarm optimisation algorithms significantly.     

An extension of Palmer's heuristic for the flow shop scheduling problem

We describe a simple modification of Palmer's heuristic for scheduling jobs in a flow shop. While the additional computation required is relatively small, the performance of the algorithm compares very well with that of the more sophisticated and better algorithm of Campbell, et al. (1970) at a fraction of the effort required by the latter.     

用模拟退火算法解旅行商问题

对解旅行商问题的模拟退火算法作了改进,增加了产生新解的函数,修改了原算法计算旅行回路总长度的代价函数,并用混沌随机序列替代不适宜的随机函数.从而用TurboC实现了改进算法.实验表明,改进算法对于解旅行商问题是实用的.     

Genetic algorithms and simulated annealing for scheduling in agile manufacturing

In this paper, genetic algorithms and simulated annealing are applied to scheduling in agile manufacturing. The system addressed consists of a single flexible machine followed by multiple identical assembly stations, and the scheduling objective is to minimize the makespan. Both genetic algorithms and simulated annealing are investigated based on random starting solutions and based on starting solutions obtained from existing heuristics in the literature. Overall, four new algorithms are developed and their performance is compared to the existing heuristics. A 2³ factorial experiment, replicated twice, is used to compare the performance of the various approaches, and identify the significant factors that affect the frequency of resulting in the best solution and the average percentage deviation from a lower bound. The results show that both genetic algorithms and simulated annealing outperform the existing heuristics in many instances. In addition, simulated annealing outperforms genetic algorithms with a more robust performance. In some instances, existing heuristics provide comparable results to those of genetic algorithms and simulated annealing with the added advantage of being simpler. Significant factors and interactions affecting the performance of the various approaches are also investigated.