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.     

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

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

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.     

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.     

基于遗传退火算法的绿色作业车间调度

绿色制造和智能制造是工业发展的两大趋势,针对目前作业车间能耗大、设备利用率低,以及产品拖期严重等问题,以智能制造业环境中的作业车间为研究对象,建立了以车间总能耗和总拖期惩罚为优化目标的多目标调度模型,并通过设置权重系数来调节优化目标决策偏好;基于遗传算法收敛速度快、全局搜索能力强,以及模拟退火算法突跳性强的特点,设计一...     

Flow time analyses of a simulated flexible job shop by considering jockeying

It has been essential to include flexibility in manufacturing policy making since variability in demand and products are considerably increasing. However, it is important to know and to monitor the proper level and type of flexibility that is required to obtain full benefits from it. This paper analyses the effects of flexibility on flow time performance of a simulated job shop. For that purpose, several scenarios are developed under four flexibility levels with two different machine selection rule and three types of dispatching rules. Furthermore, effect of jockeying as a queuing policy on the flow time performance is also investigated through simulation modeling. Results indicated that full flexibility is a preferable state for most of the cases. However, in some cases, chain configurations perform similar results since it combines the benefits of pooling and specialization. In addition, it is observed that a queue control mechanism like jockeying is an effective way to improve performance even though it may increase complexity of controlling policy.     

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.     

Makespan minimization of a flowshop sequence-dependent group scheduling problem

The flowshop sequence dependent group scheduling problem with minimization of makespan as the objective (F _m |fmls, S _plk, prmu|C _max ) is considered in this paper. It is assumed that several groups with different number of jobs are assigned to a flow shop cell that has m machines. The goal is to find the best sequence of processing the jobs in each group and the groups themselves with minimization of makespan as the objective. A mathematical model for the research problem is developed in this paper. As the research problem is shown to be NP-hard, a hybrid ant colony optimization (HACO) algorithm is developed to solve the problem. A lower bounding technique based on relaxing a few constraints of the mathematical model developed for the original problem is proposed to evaluate the quality of the HACO algorithm. Three different problem structures, with two, three, and six machines, are used in the generation of the test problems to test the performance of the algorithm and the lower bounding technique developed. The results obtained from the HACO algorithm and those that have appeared in the published literature are also compared. The comparative results show that the HACO algorithm has a superior performance compared to the best available algorithm based on memetic algorithm with an average percentage deviation of around 1.0% from the lower bound.     

A modified shifting bottleneck heuristic for the reentrant job shop scheduling problem with makespan minimization

This paper proposes a modified shifting bottleneck heuristic (MSBH) for the reentrant job shop scheduling problem (RJSSP) with makespan minimization objective. Recently, the reentrant job shop has come into prominence as a new type of manufacturing shop. The principle characteristic of a reentrant job shop is that a job may visit certain machines more than once during the process flow, whereas in the classic job shop, each job visits a machine only once. The shifting bottleneck heuristic (SBH) is one of the most successful heuristic approaches for the classical job shop scheduling problem, which decomposes the problem into a number of single-machine subproblems. This paper adapts the SBH for the RJSSP and proposes a new sequencing heuristic for the single-machine maximum lateness subproblem considering the reentrant jobs in order to handle large-size RJSSPs. It also uses a subproblem criticality measure that further shortens the implementation time. The proposed MSBH is tested by using instances up to 20 machines and 100 jobs, and it is illustrated that good quality solutions can be obtained in reasonable computational times. A real-life application of the MSBH is also given as a case study to evaluate its performance.     

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 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.     

Parallel line job shop scheduling using genetic algorithm

Parallel line job shop scheduling involves the optimal allocation and scheduling of jobs in multiple processing lines. Each job is allocated to a particular line and is processed to completion in that line. Also, all jobs allocated to a line are processed in a particular order. The objective of this paper is to find the optimal allocation of jobs to lines and also the optimal order of jobs processed in each line based on individual processing times and set up times. The optimal schedule gives the minimum makespan for the completion of all jobs. The optimization technique used is genetic algorithm.     

Makespan minimization for m-machine permutation flowshop scheduling problem with learning considerations

Increased complexity of current manufacturing systems together with dynamic conditions and permanent demands for flexible and robust functionality makes their management and control very difficult and challenging. Workflow simulation is an effective approach to investigate dynamic workflow scheduling policies and evaluate the overall manufacturing system performance. The results attained in simulation model can give directions on how to maximize system output when selecting an appropriate scheduling practice for a real system. In this paper, we investigate the abilities of multi-agent systems in combination with dynamic dispatching rules and failure handling mechanisms to manage dynamic environment conditions (such as machine failures) for systems in the production automation domain. We measure system robustness by systematically assessing the total system performance (e.g., number of finished products) in a number of representative test cases. We use an agent-based simulation environment, MAST, which has been validated with real-world hardware to strengthen the external validity of the simulation results. We investigated the performance of a re-scheduling component which uses four different policies that define how to adjust the system schedule in case of machine disturbances/failures. In the context of the empirical study the Complete Rerouting re-scheduling policy outperformed all other policies.     

Cost based scheduling in a job shop environment

Scheduling is one of the most important issues in operations planning of a manufacturing system. In this paper a new scheduling strategy based on machine cost considerations has been proposed. A scheduling factor based on initial cost of a machine and its running cost has been developed. A scanning procedure has been implemented which prioritizes eligible workstations for each setup of a job based on the scheduling factor. Two measures of performance—idleness factor and idleness cost factor—have been developed. Computer simulation has been used to investigate the impact of various decision parameters on operating behavior of the system.     

Solving job shop scheduling problems using artificial immune system

The n-job, m-machine job shop scheduling (JSS) problem is one of the general production scheduling problems. Many existing heuristics give solutions for small size problems with near optimal solutions. This paper deals with the criterion of makespan minimization for the job shop scheduling of different size problems. The proposed computational method of artificial immune system algorithm (AIS) is used for finding optimal makespan values of different size problems. The artificial immune system algorithm is tested with 130 benchmark problems [10 (ORB1-ORB5 & ARZ5-ARZ9), 40 (LA01-LA40) and 80 (TA01-TA80)]. The results show that the AIS algorithm is an efficient and effective algorithm which gives better results than the Tabu search shifting bottleneck procedure (TSSB) as well as the best solution of shifting bottleneck procedure ( SB-GLS1 ) of Balas and Vazacopoulos.     

Reverse logistics network design using simulated annealing

Reverse logistics is becoming more important in overall industry area because of the environmental and business factors. Planning and implementing a suitable reverse logistics network could bring more profit, customer satisfaction, and a nice social picture for companies. But, most of logistics networks are not equipped to handle the return products in reverse channels. This paper proposes a mixed integer linear programming model to minimize the transportation and fixed opening costs in a multistage reverse logistics network. Since such network design problems belong to the class of NP-hard problems, we apply a simulated annealing (SA) algorithm with special neighborhood search mechanisms to find the near optimal solution. We also compare the associated numerical results through exact solutions in a set of problems to present the high-quality performance of the applied SA algorithm.     

Fixed-quantity dynamic lot sizing using simulated annealing

In this paper, simulated annealing (SA) is applied to the deterministic dynamic lot-sizing problem with batch ordering and backorders. Batch ordering requires orders that are integer multiples of a fixed quantity that is larger than 1. The performance of the developed SA heuristic is compared to that of a genetic algorithm (GA) and a modified silver-meal (MSM) heuristic developed in the literature, based on the frequency of obtaining the optimum solution and the percentage average deviation from the optimum solution. In addition, the effects of three factors on the performance of the SA, GA, and the MSM are investigated in a 2³ factorial experiment. The investigated factors are the demand pattern, the batch size, and the length of the planning horizon. Results indicate that the SA heuristic has the best performance, followed by GA, in terms of the frequency of obtaining the optimum solution and the average deviation from the optimum solution. SA is also the most robust of the investigated heuristics as its performance is only affected by the length of the planning horizon.     

A simulated annealing algorithm for integration of shop floor control strategies in semiconductor wafer fabrication

The semiconductor manufacturing industry is one of the most important industries in Taiwan. Wafer fabrication is an essential process in semiconductor manufacturing. However, controlling the production system on the shop floor is extremely difficult owing to the complicated manufacturing process and reentrant characteristics. In this paper, the shop floor control (SFC) integration strategies (order review/release, dispatching, and rework strategies) in wafer fabrication are considered with using several performances. We reviewed the literature on SFC strategies in wafer fabrication. The proposed combination simulation and simulated annealing (SA) algorithm is presented for SFC strategies in wafer fabrication. The objective was to seek the near global optimum solution for the combination of SFC strategies for a specific performance indicator. From the results, the proposed methodology was found to perform well for combinations of SFC strategies using different performance indicators in wafer fabrication. However, no single combination of SFC strategies could satisfy all performance indicators. Hence, considering the trade-off among these production control strategies, a suitable strategy should be chosen based on the system control tactics. Considerable computational time was saved in this research.     

Makespan minimization for two parallel machines with an unavailable period on each machine

In this paper, we consider a two parallel machine problem where each machine has a fixed and known unavailable period. The objective is to minimize the makespan. In the literature, the problem has been considered for the case in which there is only one unavailable period on either one of the machines. This paper extends the results to two unavailable periods, one for each machine. For each of the different cases of the problem, an algorithm is developed to find the optimal solution. Although all the proposed algorithms have exponential time complexities, they are quite efficient in solving large problems. Computational results for problems with up to 1000 jobs are reported.