An interactive approach to solve the operation sequencing problem using simulated annealing

The problem of operation sequencing is affected by geometrical parameters such as tool compatibility, feature symmetry, feature accessibility, feature orientation and non-geometrical parameters such as dimensional tolerance, geometric tolerance, location tolerance and surface finish. Operation sequences are determined after meeting the objective functions such as minimum setup changeover and tool changeover, maximum tool motion continuity and maximum loose precedence among features. Because of the conflicting nature of the objectives and constraints, it is a tedious task to formulate a single objective function that can meet the requirements of the problem. Thus in this paper, an attempt has been made to address this issue to an extent by developing operation sequencing rating index (OSRI) which is the weighted sum of four indices: setup changeover index, tool changeover index, motion continuity index and loose precedence index. Determination of setup changeover index involves datum selection and sequencing in addition to grouping features into setup. Owing to the combinatorial nature of the problem, the simulated annealing (SA) based algorithm has been employed to determine the optimal/near-optimal operation sequence by maximising OSRI. In the proposed methodology, a perturbation scheme named as modified shifting scheme (MSS) has been devised to generate a feasible neighbourhood sequence that minimizes the search space and helps the algorithm to escape from local optima. A new approach for temperature variation in the SA algorithm is also incorporated in which the temperature is assumed to be parabolic. The advantage and effectiveness of the proposed methodology in terms of its algorithmic implementation have been verified on four test parts.     

求解作业车间调度问题的并行模拟退火算法

针对作业车间调度问题,提出了一种并行模拟退火算法。该算法实行群体搜索策略,由此定义了邻域搜索规则来增强个体的搜索能力,并运用马尔科夫链分析了算法的全局收敛性。该算法在一些基准问题上得到了检验,通过与其他常规方法的比较,证明此算法可提高搜索效率,改进收敛性能。     

用于作业车间调度的模拟退火算法

作业车间调度问题（Job Shop Schedullng Problem，JSP）是一类NP完全问题，解决此类问题较常使用非数值算法，而模拟退火算法是其中较为突出的而且应用广泛的一种算法。本文结合车间调度问题的特点阐述了模拟退火算法在解决车间调度问题上的应用，提出了基于模拟退火算法的车间调度问题模型，并以Matlab为工具进行了仿真实验。     

Novel approach to solve the dynamical porous journal bearing problem

Analytical pressure solutions are a simple and robust way to model plain journal bearings in rotordynamics, but cannot be extended to porous journal bearings. Using the method of weighted residuals—viz. Galerkin's method with global shape functions—a novel and fast approach to solve the dynamical porous journal bearing problem is proposed. This approach allows for the influence of rough surfaces on the hydrodynamic pressure implemented through flow-factors, journal misalignment and calculation of stiffness and damping coefficients for finite bearings. The proposed method will be verified using analytical expressions and new results will be shown for porous journal bearings including the influence of rough surfaces.     

Fuzzy-based adaptive sample-sort simulated annealing for resource-constrained project scheduling

This paper deals with the resource-constrained project scheduling problems (RCPSP), where the activities of a project have to be scheduled with the objective of minimizing the makespan subject to both temporal and resource constraints. Being one of the most intractable problems in the operations research area, RCPSP has often been a target and test bed for establishing new optimization tools and techniques. In order to efficiently solve this computationally complex problem in real time, we propose a parallel intelligent search technique named the fuzzy-based adaptive sample-sort simulated annealing (FASSA) heuristic. The basic ingredients of the proposed heuristic are the serial schedule generation scheme (SGS), sample-sort simulated annealing (SSA), and the fuzzy logic controller (FLC). The serial SGS generates the initial schedules following both the precedence and resource constraints. SSA is basically a serial simulated annealing algorithm, artificially extended across an array of samplers operating at statistically monotonically increasing temperatures. The FLC makes the SSA adaptive in nature by regulating the swapping rate of an activity’s priority during an improved schedule generation process. The implementation results of the FASSA heuristic over extremely hard test bed, adopted from the Project Scheduling Problem Library (PSPLIB), reveal its superiority over most of the currently existing approaches.     

A novel hybrid genetic algorithm to solve the sequence-dependent permutation flow-shop scheduling problem

Flow-shop scheduling problem (FSP) deals with the scheduling of a set of jobs that visit a set of machines in the same order. The FSP is NP-hard, which means that there is no efficient algorithm to reach the optimal solution of the problem. To minimize the make-span of large permutation flow-shop scheduling problems in which there are sequence-dependent setup times on each machine, this paper develops one novel hybrid genetic algorithms (HGA). Proposed HGA apply a modified approach to generate the population of initial chromosomes and also use an improved heuristic called the iterated swap procedure to improve them. Also the author uses three genetic operators to make good new offspring. The results are compared to some recently developed heuristics and computational experimental results show that the proposed HGA performs very competitively with respect to accuracy and efficiency of the solutions.     

A heuristic algorithm for the just-in-time single machine scheduling problem with setups: a comparison with simulated annealing

This paper addresses the single machine early/tardy problem with unrestricted common due date and sequence-dependent setup times. Two algorithms are introduced to reach near-optimum solutions: the SAPT, a heuristic tailored for the problem, and a simulated annealing (SA) algorithm. It will be shown that SA provides solutions with slightly better quality; however, SAPT requires much less computational time. SAPT-SA is a hybrid heuristic that combines both approaches to obtain high quality solutions with low computational cost. Solutions provided by the three algorithms were compared to optimal solutions for problems with up to 25 jobs and to each other for larger problems.     

A robust simulated annealing heuristic for flow shop scheduling problems

The flow-shop scheduling problem is one of the most well-known problems in the area of scheduling. The objective of minimising the makespan is often employed as a criterion for flow shop scheduling since Johnson’s work on the subject. The problem is strongly NP-hard and therefore many approximation algorithms have been developed to provide a good solution in reasonable run times. In this research, a mechanism that records the good solution’s characteristics is designed and introduced into simulated annealing to make the searching procedure more robust. Computational experiments show that simulated annealing with a designed mechanism can make the solution quality more robust than it is without the mechanism. In addition, the proposed simulated annealing procedure is also compared with some previously published algorithms in regard to performance. Results show that the proposed simulated annealing procedure performs well with respect to solution and efficiency.     

基于GASA优化算法的不确定条件下Job-Shop调度问题研究

针对不确定因素和动态干扰事件下Job-Shop调度问题,基于模糊数理论和动态调度策略,综合考虑完工时间、机器加工成本和机器负荷,建立了作业车间多目标不确定性调度模型;为了求解该调度模型,结合遗传算法和模拟退火算法的特点,设计了遗传模拟退火混合算法,并针对作业车间的复杂性要求,对算法的编码解码、交叉变异算子以及保优策略等方面进行了改进;通过仿真,得到了初始调度方案,然后在此基础上,采用动态调度策略对紧急插单、机器故障、工件取消和交货期变更等不确定干扰事件进行了研究.通过对某电动产品生产公司车间进行的实证研究结果表明,根据上述研究得到的较好的调度方案,可以有效地提高机器利用率和客户满意度.该模型和算法能够较好地应用到企业实际生产中.     

Application of a hybrid simulated annealing-mutation operator to solve fuzzy capacitated location-routing problem

In the field of supply chain management and logistics, using vehicles to deliver products from depots to customers is one of the major operations. Before using vehicles, optimizing the location of depots is necessary in a location-routing problem (LRP). Also, before transportation products, optimizing the routing of vehicles is required so as to provide a low-cost and efficient service for customers. In this paper, the mathematical modelling of LRP is developed according to the existing condition and constraint in the real world. Maximum travelling time constraint is added, and we apply fuzzy numbers to determine customer demands, travelling time and drop time. The objective is to open a subset of depots to assign customers to these depots and to design vehicle routes, in order to minimize both the cost of open depots and the total cost of the routes. The proposed problem is modelled as a fuzzy linear programming (FLP), by applying the fuzzy ranking function method; the proposed FLP is converted to an exact linear programming (LP). A Lingo solver is used to solve this LP model in very small size. LRP is an non-deterministic polynomial-time hard (NP-Hard) problem, and because of the limitation of Lingo solver in solving medium, and large-size numerical examples, a hybrid algorithm including simulated annealing and mutation operator is proposed to solve these numerical examples. Also, a heuristic algorithm is proposed to find a suitable initial solution which is used in hybrid algorithm. At the end, a different analysis of the applied algorithm and a proposed model are introduced.     

Meta-heuristics to solve single-machine scheduling problem with sequence-dependent setup time and deteriorating jobs

This paper tackles the single-machine scheduling problem in which there are sequence-dependent setup times and deteriorating jobs. In this regard, a mathematical model has been formulated to minimize makespan (C _max). Afterwards, genetic and tabu search algorithms have been developed. Since the population diversity is a very important issue in preventing neighborhood search from trapping in a local optimum, some methods have been applied to genetic algorithm in order to maintain population diversity, and the final results show the effectiveness of these methods. The calibration of genetic algorithm parameters and operators is performed using design of experiments. Finally, several examples are produced to illustrate the proposed approach.     

A simulated annealing approach to makespan minimization on identical parallel machines

This paper addresses a makespan minimization scheduling problem on identical parallel machines. Several heuristic algorithms have been proposed to tackle the problem. In this paper, a very effective simulated annealing method is proposed to generate the near-optimal solution. Computational results demonstrate that the proposed heuristic is very accurate and that it outperforms the existing methods.     

A hybrid algorithm based on particle swarm optimization and simulated annealing for a periodic job shop scheduling problem

Generating schedules such that all operations are repeated every constant period of time is as important as generating schedules with minimum delays in all cases where a known discipline is desired or obligated by stakeholders. In this paper, a periodic job shop scheduling problem (PJSSP) based on the periodic event scheduling problem (PESP) is presented, which deviates from the cyclic scheduling. The PESP schedules a number of recurring events as such that each pair of event fulfills certain constraints during a given fixed time period. To solve such a hard PJSS problem, we propose a hybrid algorithm, namely PSO-SA, based on particle swarm optimization (PSO) and simulated annealing (SA) algorithms. To evaluate this proposed PSO-SA, we carry out some randomly constructed instances by which the related results are compared with the proposed SA and PSO algorithms as well as a branch-and-bound algorithm. In addition, we compare the results with a hybrid algorithm embedded with electromagnetic-like mechanism and SA. Moreover, three lower bounds (LBs) are studied, and the gap between the found LBs and the best found solutions are reported. The outcomes prove that the proposed hybrid algorithm is an efficient and effective tool to solve the PJSSP.     

柔性装配制造系统中生产优化的Petri网方法

本文在基本Ｐｅｔｒｉ网的基础上,给出了一种进行周期性生产的柔性装配制造系统的模型;同时,针对该系统,给出了一个求稳定需求下最佳生产指量的启发式调度方法。     

A simulated annealing for hybrid flow shop scheduling with multiprocessor tasks to minimize makespan

This paper studies a hybrid flow shop scheduling problem (hybrid FSSP) with multiprocessor tasks, in which a set of independent jobs with distinct processor requirements and processing times must be processed in a k-stage flow shop to minimize the makespan criterion. This problem is known to be strongly nondeterministic polynomial time (NP)-hard, thus providing a challenging area for meta-heuristic approaches. This paper develops a simulated annealing (SA) algorithm in which three decode methods (list scheduling, permutation scheduling, and first-fit method) are used to obtain the objective function value for the problem. Additionally, a new neighborhood mechanism is combined with the proposed SA for generating neighbor solutions. The proposed SA is tested on two benchmark problems from the literature. The results show that the proposed SA is an efficient approach in solving hybrid FSSP with multiprocessor tasks, especially for large problems.     

求解车间调度问题的一种新遗传退火混合策略

综合了遗传算法和模拟退火算法的优点,提出了一种新的遗传退火混合优化策略。该算法引入模拟退火算法作为遗传算法种群的变异算子,增强和补充了遗传算法的进化能力,同时将机器学习原理引入混合算法中,增加了种群的平均适值,有效地避免了最优解的丢失,加快了进化速度,使系统能够在很短的时间内得到最优解。针对车间调度的典型问题进行了仿真,结果证明了新算法的有效性。     

Pareto archived simulated annealing for job shop scheduling with multiple objectives

In this paper, the job shop scheduling problem is studied with the objectives of minimizing the makespan and the mean flow time of jobs. The simultaneous consideration of these objectives is the multi-objective optimization problem under study. A metaheuristic procedure based on the simulated annealing algorithm called Pareto archived simulated annealing (PASA) is proposed to discover non-dominated solution sets for the job shop scheduling problems. The seed solution is generated randomly. A new perturbation mechanism called segment-random insertion (SRI) scheme is used to generate a set of neighbourhood solutions to the current solution. The PASA searches for the non-dominated set of solutions based on the Pareto dominance or through the implementation of a simple probability function. The performance of the proposed algorithm is evaluated by solving benchmark job shop scheduling problem instances provided by the OR-library. The results obtained are evaluated in terms of the number of non-dominated schedules generated by the algorithm and the proximity of the obtained non-dominated front to the Pareto front.     

Determination of due dates in job shop scheduling by simulated annealing

The scheduling of n jobs to m machines in a job shop is considered. A predefined due date, a release time and the minimization of the maximal job's lateness is the objective assigned to each job. A search space consisting of triads (job, operation, machine) is formulated, and an iterrative improvement approach, the simulated annealing method, is then used to obtain feasible and global optimal solution. The simulated annealing method is applied to two alternative energy functions to model the maximum lateness. For calculation of the first energy function at each step, complete schedules are created and the lateness of each job is derived by abstracting the job's completion time from the corresponding due date. The second energy function is calculated on the basis of partial estimates often used by pairwise interchange techniques. The convergence of the algorithm in relation to the initial temperature, temperature iterrations and temperature cycles has been verified in various case studies. Specific characteristics of the scheduling, such as its dimensionality and the deviation of the total processing time from the due dates, were considered. Common characteristics derived were subsequently used for the definition of an efficient annealing schedule.     

求解带能力约束车辆路径优化问题的改进模拟退火算法

为高效求解带能力约束的车辆路径优化问题,提出一种带有回火操作的改进模拟退火算法.解析多约束条件下的路径优化特点,构建了结构简单且功能模块相对独立的模拟退火框架,以便相关约束及其算法的耦合嵌套.在此基础上,改变较优解在迭代过程中的接受规则,引入回火操作使全局搜索与局部搜索实现平衡;设计强制的随机邻域变换策略,以提高多约束...     

Psycho-clonal based approach to solve a TOC product mix decision problem

In recent years, theory of constraints (TOC) has emerged as an effective management philosophy that has successfully tackled the problems of profit maximization with known demonstrated bottleneck in traditional as well as modern manufacturing plants. One of the key components of TOC application is to enumerate quantity of the various products to be produced keeping in view the system constraints and this is termed as the TOC product mix decision problem. It is a well-known computationally complex problem and thus warrants the application of heuristics technique or AI based optimization tools to achieve near optimal solutions in real time. To accomplish this objective a new algorithm, Psycho-Clonal has been proposed that works on the principle of artificial immune system and behavioral theory, namely Maslow's need hierarchy theory. Intensive computational experiments have been carried out and superiority of proposed heuristic on a given dataset is established. It is observed that results obtained are better compared to what have been achieved by the TOC heuristic, revised theory of constraint heuristic (RTOC), integer linear programming (ILP), and tabu search based approaches.