A simulated annealing algorithm based approach for balancing and sequencing of mixed-model U-lines

It is known that two interrelated problems called as line balancing and model sequencing should be solved simultaneously for an efficient implementation of a mixed-model U-shape assembly line in a JIT (Just in Time) environment. On the other hand, three versions of assembly line balancing problem can be identified: Type I, Type II, and Type E. There are only two articles ( Kara, Ozcan, & Peker, 2007a and Hamzadayi & Yildiz, 2012) related to simultaneous balancing and sequencing of mixed-model U-lines for minimizing the number of stations (Type 1 problem) by ignoring the fixed model sequence in the current literature. In this paper, a simulated annealing algorithm is proposed for solving a problem of type 1 by ignoring the fixed model sequence. Accordingly, simulated annealing based fitness evaluation approach proposed by Hamzadayi and Yildiz (2012) is enhanced by adding the tabu list, and inserted into the proposed algorithm. Implementation difficulties experienced in meta-heuristics based on solution modification for solving these types of problems are demonstrated. ‘Absolute deviation of workloads’ (ADW) is quite frequently used as performance criteria in the literature. It is found that ADW is an insufficient performance criterion for evaluating the performance of the solutions, and this is showed by means of an illustrative example. The parameters of the proposed algorithm are reviewed for calibrating the algorithm by means of Taguchi design of experiments. Performance of the proposed approach is tested through a set of test problems. The results of computational experiments indicate that the proposed approach is an effective method in solving simultaneous line balancing/model sequencing problems for mixed-model U-lines for minimizing the number of stations.     

Multi-objective optimization of a stochastic assembly line balancing: A hybrid simulated annealing algorithm

This paper deals with multi-objective optimization of a single-model stochastic assembly line balancing problem with parallel stations. The objectives are as follows: (1) minimization of the smoothness index and (2) minimization of the design cost. To obtain Pareto-optimal solutions for the problem, we propose a new solution algorithm, based on simulated annealing (SA), called m_SAA. m_SAA implements a multinomial probability mass function approach, tabu list, repair algorithms and a diversification strategy. The effectiveness of m_SAA is investigated comparing its results with those obtained by another SA (using a weight-sum approach) on a suite of 24 test problems. Computational results show that m_SAA with a multinomial probability mass function approach is more effective than SA with weight-sum approach in terms of the quality of Pareto-optimal solutions. Moreover, we investigate the effects of properties (i.e., the tabu list, repair algorithms and diversification strategy) on the performance of m_SAA.     

Minimization of MRF Energy with Relaxation Labeling

Recently, there has been increasing interest in Markovrandom field (MRF) modeling for solving a variety of computer visionproblems formulated in terms of the maximum a posteriori(MAP) probability. When the label set is discrete, such as in imagesegmentation and matching, the minimization is combinatorial. Theobjective of this paper is twofold: Firstly, we propose to use thecontinuous relaxation labeling (RL) as an alternative approach forthe minimization. The motivation is that it provides a goodcompromise between the solution quality and the computational cost.We show how the original combinatorial optimization can be convertedinto a form suitable for continuous RL. Secondly, we compare variousminimization algorithms, namely, the RL algorithms proposed byRosenfeld et al., and by Hummel and Zucker, the mean field annealing ofPeterson and Soderberg, simulated annealing of Kirkpatrick, theiterative conditional modes (ICM) of Besag and an annealing versionof ICM proposed in this paper. The comparisons are in terms of theminimized energy value (i.e., the solution quality), the requirednumber of iterations (i.e., the computational cost), and also thedependence of each algorithm on heuristics.     

Tabu search for a class of single-machine scheduling problems

In this paper we develop a tabu search-based solution procedure designed specifically for a certain class of single-machine scheduling problems with a non-regular performance measure. The performance of the developed algorithm is tested for solving the variance minimization problem. Problems from the literature are used to test the performance of the algorithm. This algorithm can be used for solving other problems such as minimizing completion time deviation from a common due date.Scope and purposeScheduling problems with non-regular performance measures has gained a great importance in modern manufacturing systems. These problems are found to be hard to solve and analyze. The purpose of this paper is to present a tabu search approach for solving a certain class of single-machine scheduling problems with non-regular performance measure. Minimizing the variance of completion times and the total deviation from a common due date are two examples of such problems. The proposed approach is found to perform better than the simulated annealing approach for the variance minimization problem.     

Minimizing binary functions with simulated annealing algorithm with applications to binary tomography

The minimization of binary functions finds many applications in practice, and can be solved by the simulated annealing (SA) algorithm. However, the SA algorithm is designed for general combinatorial problems, not specifically for binary problems. Consequently, a direct application of the SA algorithm might not provide optimal performance and efficiency. Therefore, this study specifically investigated the performance of various implementations of the SA algorithm when applied to binary functions. Results obtained in this investigation demonstrated that 1) the SA algorithm can reliably minimize difficult binary functions, 2) a simple technique, analogous to the local search technique used in minimizing continuous functions, can exploit the special structure of binary problems and significantly improve the solution with negligible computational cost, and 3) this technique effectively reduces computational cost while maintaining reconstruction fidelity in binary tomography problems. This study also developed two classes of binary functions to represent the typical challenges encountered in minimization.     

新型遗传模拟退火算法求解带VRPTW问题

为了克服现有遗传算法不能有效求解时间窗车辆路径问题的缺陷,提出了一种由遗传算法结合模拟退火算法的混合算法求解该问题,并与遗传算法进行了比较。该算法利用了模拟退火算法具有较强的局部搜索能力的特性,有效地克服了传统遗传算法的“早熟收敛”问题。实验结果表明,该算法具有计算效率高、收敛速度快和求解质量优的特点,是解决车辆路径问题的有效方法。     

Efficient algorithms for the uncapacitated single allocation p-hub median problem

We present a new LP formulation for the single allocation p-hub median problem, which requires fewer variables and constraints than those traditionally used in the literature. We develop a good heuristic algorithm for its solution based on simulated annealing (SA). We use the SA upper bound to develop an LP-based branch-and-bound solution method. We present computational results for well-known problems from the literature which show that exact solutions can be found in a reasonable amount of computational time. We also benchmark our new solution approach on a new data set. This data set, which includes problems that are larger than those used in the literature, is based on a postal delivery network.     

Local search heuristics for two-stage flow shop problems with secondary criterion

This paper develops and compares different local search heuristics for the two-stage flow shop problem with makespan minimization as the primary criterion and the minimization of either the total flow time, total weighted flow time, or total weighted tardiness as the secondary criterion. We investigate several variants of simulated annealing, threshold accepting, tabu search, and multi-level search algorithms. The influence of the parameters of these heuristics and the starting solution are empirically analyzed. The proposed heuristic algorithms are empirically evaluated and found to be relatively more effective in finding better quality solutions than the existing algorithms.Scope and purposeTraditional research to solve multi-stage scheduling problems has focused on single criterion. However, in industrial scheduling practices, managers develop schedules based on multi-criteria. Scheduling problems involving multiple criteria require significantly more effort in finding acceptable solutions and hence have not received much attention in the literature. This paper considers one such multiple criteria scheduling problem, namely, the two-machine flow shop problem where the primary criterion is the minimization of makespan and the secondary criterion is one of the three most popular performance measures, namely, the total flow time, total weighted flow time, or total weighted tardiness. Based on the principles of local search, development of heuristic algorithms, that can be adapted for several multi-criteria scheduling problems, is discussed. Using the example of the two-machine flow shop problem with secondary criterion, computational experiments are used to evaluate the utility of the proposed algorithms for solving scheduling problems with a secondary criterion.     

A simulated annealing algorithm for multi-manned assembly line balancing problem

Assembly line balancing problems with multi-manned workstations usually occur in plants producing high volume products (e.g. automotive industry) in which the size of the product is reasonably large to utilize the multi-manned assembly line configuration. In these kinds of assembly lines, usually there are multi-manned workstations where a group of workers simultaneously performs different operations on the same individual product. However, owing to the high computational complexity, it is quite difficult to achieve an optimal solution to the balancing problem of multi-manned assembly lines with traditional optimization approaches. In this study, a simulated annealing heuristic is proposed for solving assembly line balancing problems with multi-manned workstations. The line efficiency, line length and the smoothness index are considered as the performance criteria. The proposed algorithm is illustrated with a numerical example problem, and its performance is tested on a set of test problems taken from literature. The performance of the proposed algorithm is compared to the existing approaches. Results show that the proposed algorithm performs well.     

A hybrid simulated annealing algorithm for location and routing scheduling problems with cross-docking in the supply chain

The location and routing scheduling problems with cross-docking can be regarded as new research directions for distribution networks in the supply chain. The aims of these problems are to concurrently design a cross-docking center location and a vehicle routing scheduling model, known as NP-hard problems. This paper presents a two-stage mixed-integer programming (MIP) model for the location of cross-docking centers and vehicle routing scheduling problems with cross-docking due to potential applications in the distribution networks. Then, a new algorithm based on a two-stage hybrid simulated annealing (HSA) with a tabu list taken from tabu search (TS) is proposed to solve the presented model. This proposed HSA not only prevents revisiting the solution but also maintains the stochastic nature. Finally, small and large-scale test problems are randomly generated and solved by the HSA algorithm. The computational results for different problems show that the proposed HSA performs well and converges fast to reasonable solutions.     

不确定车辆数的有时间窗车辆选径问题的混合算法

针对标准遗传算法在求解车辆选径问题中出现的早熟、收敛、易陷入局部极值点的问题，提出了一种由遗传算法结合模拟退火算法的混合算法求解车辆选径问题，并与遗传算法进行了比较。该算法利用了模拟退火算法具有的较强的局部搜索能力的特性，有效地克服了传统遗传算法的“早熟收敛”问题。实验结果表明，该算法具有计算效率高、收敛速度快和求解质量优的特点，是解决车辆选径问题的有效方法。     

Bregmanized Domain Decomposition for Image Restoration

Computational problems of large-scale data are gaining attention recently due to better hardware and hence, higher dimensionality of images and data sets acquired in applications. In the last couple of years non-smooth minimization problems such as total variation minimization became increasingly important for the solution of these tasks. While being favorable due to the improved enhancement of images compared to smooth imaging approaches, non-smooth minimization problems typically scale badly with the dimension of the data. Hence, for large imaging problems solved by total variation minimization domain decomposition algorithms have been proposed, aiming to split one large problem into N>1 smaller problems which can be solved on parallel CPUs. The N subproblems constitute constrained minimization problems, where the constraint enforces the support of the minimizer to be the respective subdomain. In this paper we discuss a fast computational algorithm to solve domain decomposition for total variation minimization. In particular, we accelerate the computation of the subproblems by nested Bregman iterations. We propose a Bregmanized Operator Splitting–Split Bregman (BOS-SB) algorithm, which enforces the restriction onto the respective subdomain by a Bregman iteration that is subsequently solved by a Split Bregman strategy. The computational performance of this new approach is discussed for its application to image inpainting and image deblurring. It turns out that the proposed new solution technique is up to three times faster than the iterative algorithm currently used in domain decomposition methods for total variation minimization.     

Solving the team orienteering problem using effective multi-start simulated annealing

The team orienteering problem (TOP) is known as an NP-complete problem. A set of locations is provided and a score is collected from the visit to each location. The objective is to maximize the total score given a fixed time limit for each available tour. Given the computational complexity of this problem, a multi-start simulated annealing (MSA) algorithm which combines a simulated annealing (SA) based meta-heuristic with a multi-start hill climbing strategy is proposed to solve TOP. To verify the developed MSA algorithm, computational experiments are performed on well-known benchmark problems involving numbers of locations ranging between 42 and 102. The experimental results demonstrate that the multi-start hill climbing strategy can significantly improve the performance of the traditional single-start SA. Meanwhile, the proposed MSA algorithm is highly effective compared to the state-of-the-art meta-heuristics on the same benchmark instances. The proposed MSA algorithm obtained 135 best solutions to the 157 benchmark problems, including five new best solutions. In terms of both solution quality and computational expense, this study successfully constructs a high-performance method for solving this challenging problem.     

Two-sided assembly line balancing considering the relationships between tasks

Previous studies of the two-sided assembly line balancing problem assumed equal relationships between each two tasks assignable to a side of the line. In practice, however, this relationship may be related to such factors as the distance between the implementation place and the tools required for implementation. We know that the more relationships exist between the tasks assigned to each station, the more efficient will be the assembly line. In this paper, we suggest an index for calculating the value of the relationship between each two tasks, and define a performance criterion called ‘assembly line tasks consistency’ for calculating the average relationship between the tasks assigned to the stations of each solution. We propose a simulated annealing algorithm for solving the two-sided assembly line balancing problem considering the three performance criteria of number of stations, number of mated-stations, and assembly line tasks consistency. Also, the simulated annealing algorithm is modified for solving the two-sided assembly line balancing problem without considering the relationships between tasks. This modification finds five new best solutions for the number of stations performance criterion and ten new best solutions for the number of mated-stations performance criterion for benchmark instances.     

Multi-objective optimal power flow using quasi-oppositional teaching learning based optimization

This paper describes teaching learning based optimization (TLBO) algorithm to solve multi-objective optimal power flow (MOOPF) problems while satisfying various operational constraints. To improve the convergence speed and quality of solution, quasi-oppositional based learning (QOBL) is incorporated in original TLBO algorithm. The proposed quasi-oppositional teaching learning based optimization (QOTLBO) approach is implemented on IEEE 30-bus system, Indian utility 62-bus system and IEEE 118-bus system to solve four different single objectives, namely fuel cost minimization, system power loss minimization and voltage stability index minimization and emission minimization; three bi-objectives optimization namely minimization of fuel cost and transmission loss; minimization of fuel cost and L-index and minimization of fuel cost and emission and one tri-objective optimization namely fuel cost, minimization of transmission losses and improvement of voltage stability simultaneously. In this article, the results obtained using the QOTLBO algorithm, is comparable with those of TLBO and other algorithms reported in the literature. The numerical results demonstrate the capabilities of the proposed approach to generate true and well-distributed Pareto optimal non-dominated solutions of the multi-objective OPF problem. The simulation results also show that the proposed approach produces better quality of the individual as well as compromising solutions than other algorithms.     

Multi-layer bus minimization for SoC

The deployment of multiple processing elements such as a microprocessor or a Digital Signal Processor in embedded systems often results in significant communication overheads. The challenge lies in resolving the communication cost minimization problem, while simultaneously satisfying the timing constraints of job executions. In this paper, we explore bus-layer minimization problems by first identifying factors that contribute to the NP-hardness of these problems. Existing proposed algorithms and NP-hard problems are then identified and elucidated. A simulated annealing algorithm is proposed and compared with heuristics-based algorithms to provide further insights for system designers. Lastly, a series of extensive simulations is carried out and a case study is presented to show comparisons among different approaches and workloads.     

Parallel hyper heuristic algorithm based on reinforcement learning for the corridor allocation problem and parallel row ordering problem

Hyper heuristics is a relatively new optimisation algorithm. Numerous studies have reported that hyper heuristics are well applied in combinatorial optimisation problems. As a classic combinatorial optimisation problem, the row layout problem has not been publicly reported on applying hyper heuristics to its various sub-problems. To fill this gap, this study proposes a parallel hyper-heuristic approach based on reinforcement learning for corridor allocation problems and parallel row ordering problems. For the proposed algorithm, an outer layer parallel computing framework was constructed based on the encoding of the problem. The simulated annealing, tabu search, and variable neighbourhood algorithms were used in the algorithm as low-level heuristic operations, and Q-learning in reinforcement learning was used as a high-level strategy. A state space containing sequences and fitness values was designed. The algorithm performance was then evaluated for benchmark instances of the corridor allocation problem (37 groups) and parallel row ordering problem (80 groups). The results showed that, in most cases, the proposed algorithm provided a better solution than the best-known solutions in the literature. Finally, the meta-heuristic algorithm applied to three low-level heuristic operations is taken as three independent algorithms and compared with the proposed hyper-heuristic algorithm on four groups of parallel row ordering problem instances. The effectiveness of Q-learning in selection is illustrated by analysing the comparison results of the four algorithms and the number of calls of the three low-level heuristic operations in the proposed method.     

Multi-rule Multi-objective Simulated Annealing Algorithm for Straight and U Type Assembly Line Balancing Problems

The task of balancing of assembly lines is of considerable industrial importance. It consists of assigning operations to workstations in a production line in such a way that (1) no assembly precedence constraint is violated, (2) no workstations in the line takes longer than a predefined cycle time to perform all tasks assigned to it, and (3) as few workstations as possible are needed to perform all the tasks in the set. This paper presents a new multiple objective simulated annealing (SA) algorithm for simple (line) and U type assembly line balancing problems with the aim of maximizing “smoothness index” and maximizing the “line performance” (or minimizing the number of workstations). The proposed algorithm makes use of task assignment rules in constructing feasible solutions. The proposed algorithm is tested and compared with literature test problems. The proposed algorithm found the optimal solutions for each problem in short computational times. A detailed performance analysis of the selected task assignment rules is also given in the paper.     

An agent-based algorithm for personnel shift-scheduling and rescheduling in flexible assembly lines

This article is about a multi-agent based algorithm for personnel scheduling and rescheduling in a dynamic environment of a paced multi-product assembly center. The purpose is first to elaborate daily employees?? assignment to workstations so as to minimize the operational costs as well as personnel dissatisfactions; the second is to generate an alternative planning when the first solution has to be rescheduled due to disturbances related to absenteeism. The proposed approach takes into account individual competencies, mobility and preferences of each employee, along with the competency requirements associated with each assembly activity, with respect to both the current master assembly schedule and the line balancing for each product. We use solutions obtained through a simulated annealing algorithm in order to benchmark the performance of the multi-agent approach. Experimental results show that our multi-agent approach can produce high-quality and efficient solutions in a short computational time.     

Initialization strategies to enhancing the performance of genetic algorithms for the p-median problem

Finding solutions to the p-median problem is an important research topic in location science. A number of meta-heuristic methods have been developed in the literature to find optimal or near optimal solutions to large-scale p-median problems within an acceptable computational time. Among these methods, the recent literature has demonstrated the effectiveness of genetic algorithms (GAs) and hybrid GAs. In this paper, we focus on the strategies of generating the initial population of a genetic algorithm and examine the impact of such strategies on the overall GA performance in terms of solution quality and computational time. Our initialization approach first produces a near optimal solution with low computational complexity, and then uses this solution as a seed to generate a set of solutions as the initial GA population, which is then used in an existing hybrid GA to test the performance of the proposed approach. Experiments based on the forty p-median problems in the OR Library are conducted. Results demonstrate that the proposed approach can significantly reduce computational time without compromising the quality of resulting solutions in almost all cases, and the excellence of the proposed approach increases with the problem scale. Furthermore, a geo-referenced dataset is also tested and the resulting solution maps visualize and validate the principle of the proposed approach.