Optimization of process planning with various flexibilities using an imperialist competitive algorithm

In this paper, we investigate the optimization of process planning in which various flexibilities are considered. The objective is to minimize total weighted sum of manufacturing costs. Various flexibilities, including process flexibility, sequence flexibility, machine flexibility, tool flexibility, and tool access direction (TAD) flexibility, generally exist in process planning and consideration of these flexibilities is essential for improving production efficiency and system flexibility. However, process planning is strongly NP-hard due to the existence of various flexibilities as well as complex machining precedence constraints. To tackle this problem, an imperialist competitive algorithm (ICA) is employed to find promising solutions with reasonable computational cost. ICA is a novel socio-politically motivated metaheuristic algorithm inspired by imperialist competition. It starts with an initial population and proceeds through assimilation, position exchange, imperialistic competition, and elimination. Computational experiments on three sets of process planning problem taken from literature are carried out, and comparisons with some existing algorithms developed for process planning are presented. The results show that the algorithm performs significantly better than existing algorithms like genetic algorithm (GA), simulated annealing (SA), tabu search (TS), and particle swarm optimization (PSO).     

Sensitivity search for the rescheduling of semiconductor photolithography operations

This study deals with the rescheduling problem of the photolithography area in semiconductor wafer fabrications. The objective is to find a schedule that minimizes the weighted sum of makespan, maximum tardiness, and total setup time. Practical issues such as machine breakdowns, limited number of available masks, restrictions on photoresist, production notice, and machine setup are considered. Three popular search algorithms—simulated annealing (SA), genetic algorithm (GA), and tabu search (TS) — are tested to solve the scheduling problem. We also propose a new sensitivity search approach. A new event changes the scheduling problem. Thus, the problem needs to be re-solved to reflect such changes. In an actual production environment, we propose that, instead of searching for a solution from scratch, the search process can be restarted from the best solution of an original problem that is very similar to the new problem. Using an industrial data set, this study tests the proposed approach. The results show that TS performs the best among the algorithms tested, and the performance of the sensitivity TS significantly surpasses that of the traditional approach.     

Two heads are better than one: an AIS- and TS-based hybrid strategy for job shop scheduling problems

Job shop problems (JSPs) widely exist in many fields and are usually very hard to solve. Despite the fact that many scheduling algorithms have been studied, it is still challenging to find optimal solutions for certain JSPs. Some studies have shown that it is difficult to solve these JSPs by only using a single search technique, while the hybrid of different ones is usually more effective. In this paper, a hybrid algorithm combining artificial immune system (AIS) with tabu search (TS) is proposed. The AIS is based on the clonal selection principle of biological immune systems and is used to find the solution space with potential high evaluation values. The TS is used to exploit the local solution space to further improve the quality of a solution. The neighborhood of the TS is based on a disjunctive graph model, and a smaller neighborhood structure is adopted to reduce the computational cost of the neighborhood search. To reduce the solution space of JSPs and balance convergence speed and solution quality, scheduling solutions are restricted in the set of parameterized active schedules, i.e., a subset of active schedules. Forty-three benchmark instances are used to evaluate the proposed hybrid algorithm, and experimental results are compared with those of other algorithms. Results show that the hybrid algorithm is very effective for JSPs.     

Heuristic search algorithms for lot streaming in a two-machine flowshop

The objective of this paper is to propose and evaluate heuristic search algorithms for a two-machine flowshop problem with multiple jobs requiring lot streaming that minimizes makespan. A job here implies many identical items. Lot streaming creates sublots to move the completed portion of a production lot to second machine. The three heuristic search algorithms evaluated in this paper are Baker’s approach (Baker), genetic algorithm (GA) and simulated annealing (SA) algorithm. To create neighborhoods for SA, three perturbation schemes, viz., pair-wise exchange, insertion and random insertion are used, and the performance of these on the final schedule is also compared. A wide variety of data sets is randomly generated for comparative evaluation. The parameters for GA and SA are obtained after conducting sensitivity analysis. The genetic algorithm is found to perform well for lot streaming in the two-machine flowshop scheduling.     

基于CMM测量路径优化算法的研究

随着计算机集成制造系统(CIMS)的深入发展,计算机辅助检测工艺规划(CAIP)已成为CIMS中集成质量系统(IQS)的关键环节。本文研究了基于坐标测量机(CMM)的测量路径优化算法,对坐标测量机的测量路径优化问题进行了合理的描述,分析了已有路径优化算法存在的不足,提出并实现了将遗传算法和禁忌搜索算法结合的策略用于测量路径优化的GATS算法,取得了良好的效果。     

A guided tabu search/path relinking algorithm for the job shop problem

The job shop scheduling problem with makespan criterion is valuable from both practical and theoretical points of view. This problem has been attacked by most of the well-known meta-heuristic algorithms. Among them, tabu search has emerged as the most effective approach. The proposed algorithm takes advantages of both N1 and N6 neighborhoods. N1 neighborhood is used as a path relinking procedure while N6 neighborhood with its guideposts is applied in a tabu search framework. In addition, a method is presented for updating the topological order, heads and tails in N6 neighborhood. The algorithm is tested on standard benchmark sets, outperformed all previous approaches (include i-TSAB) and found six new upper bounds among the unsolved problems. Furthermore, we have tried to collect the newest upper bounds for the other problems.     

一种求解作业车间JIT调度问题的混合TS/MP算法

作业车间JIT调度属于一类典型的非正规性能指标调度问题,该类问题为每道工序设置了交货期约束,工序的提前或拖期完工均会产生相应的惩罚成本。采用禁忌搜索和数学规划相结合的混合调度方法进行求解。在算法的迭代搜索过程中,首先,由每个个体产生各机器上的工件加工序列,由此松弛了调度模型中的机器能力析取约束,然后,调用数学规划方法来优化各机器的空闲时间和各工序的开工时间。为提高禁忌搜索算法的计算效率,设计了一种包含交换和插入操作的邻域结构产生方案。最后,用JIT调度领域的32个标准测试算例验证了该调度算法的有效性。     

A hybrid two-phase encoding particle swarm optimization for total weighted completion time minimization in proportionate flexible flow shop scheduling

A proportionate flow shop (PFS) is a special case of the m machine flow shop problem. In a PFS, a fixed sequence of machines is arranged in s stages (s?>?1) with only a single machine at each stage, and the processing time for each job is the same on all machines. Notably, PFS problems have garnered considerable attention recently. A proportionate flexible flow shop (PFFS) scheduling problem combines the properties of PFS problems and parallel-identical-machine scheduling problems. However, few studies have investigated the PFFS problem. This study presents a hybrid two-phase encoding particle swarm optimization (TPEPSO) algorithm to the PFFS problem with a total weighted completion time objective. In the first phase, a sequence position value representation is designed based on the smallest position value rule to convert continuous position values into job sequences in the discrete PFFS problem. During the second phase, an absolute position value representation combined with a tabu search (TS) is applied starting from the current position of particles that can markedly improve swarm diversity and avoid premature convergence. The hybrid TPEPSO algorithm combines the cooperative and competitive characteristics of TPEPSO and TS. Furthermore, a candidate list strategy is designed for the TS to examine the neighborhood and concentrate on promising moves during each iteration. Experimental results demonstrate the robustness of the proposed hybrid TPEPSO algorithm in terms of solution quality. Moreover, the proposed hybrid TPEPSO algorithm is considerably faster than existing approaches for the same benchmark problems in literature.     

Development of integrated evolutionary optimization algorithm and its application to optimum design of ship structures

This paper proposes an integrated evolutionary optimization algorithm (IEOA) which is combined with genetic algorithm (GA), random tabu search method (TS) and response surface methodology (RSM). This algorithm, in order to improve the convergent speed that is thought to be the demerit of GA, uses RSM and the simplex method. Though mutation of GA offers random variety, systematic variety can be secured through the use of tabu-list. Efficiency of this method has been proven by applying traditional test functions and comparing the results to GA. And it is an evidence that the newly suggested algorithm can effectively find the global optimum solution by applying it to minimize the weight of fresh water tank that is placed in the rear of ship designed to avoid resonance. According to the results, GA’s convergent speed in initial phase has been improved by using RSM. An optimized solution was calculated without the evaluation of additional actual objective function. Finally, it can be concluded that IEOA is a very useful global optimization algorithm from the viewpoint of convergent speed and global search ability.     

Parallel machine scheduling with earliness-tardiness penalties and space limits

In order to maximize an availability of machine and utilization of space, the parallel machines scheduling problem with space limit is frequently discussed in the industrial field. In this paper, we consider the parallel machine scheduling problem in which n jobs having different release times, due dates, and space limits are to be scheduled on m parallel machines. The objective function is to minimize the weighted sum of earliness and tardiness. To solve this problem, a heuristic is developed which is divided into three modules hierarchically: job selection, machine selection and job sequencing, and solution improvement. To illustrate its effectiveness, a proposed heuristic is compared with genetic algorithm (GA), hybrid genetic algorithm (HGA), and tabu search (TS), which are well-known meta-heuristics in a large number of randomly generated test problems based on the field situation. Also, we determine the job selection rule that is suitable to the problem situation considered in this paper and show the effectiveness of our heuristic method.     

求解模糊作业车间调度问题的混合优化算法

针对模糊作业车间调度问题(Fuzzy job-shop scheduling problem, FJSSP),提出一种结合化学反应优化和禁忌搜索的混合算法(Chemical-reaction optimization and tabu search, CROTS),优化的目标是最小化最大模糊完工时间。算法采用基于工序的编码,通过扩展壁面碰撞、分子碰撞、合成、分解等操作算子,改进了基本化学反应优化(Chemical-reaction optimization, CRO)的四类基元反应。给出一种有效的交叉算子,并应用到分子碰撞、合成、分解三种基元反应中。对最好解进行禁忌搜索,进一步提高种群的搜索能力。结合16个经典算例试验分析,并与三种典型算法比较,验证算法具有较强的全局和局部搜索能力。通过18个随机算例的测试,验证算法具备求解较大规模问题的能力。     

A Petri net approach for simple assembly line balancing problems

A simple assembly line balancing problem of type-1 (SALBP-1) aims to minimize the number of workstations for a given cycle time. In the relevant literature, several heuristics based on a branch-and-bound procedure, tabu search, and genetic algorithms (GAs) were proposed to solve SALBP-1. In this paper, an algorithm based on the reachability analysis of Petri nets is developed for SALBP-1. The proposed algorithm searches enabled transitions (or assignable tasks) in the Petri net model of precedence relations between tasks, and then the task minimizing the idle time is assigned to the station under consideration. The algorithm is coded in MATLAB, and its efficiency is tested on Talbot’s and Hoffmann’s benchmark datasets according to some performance measures and classifications. A computational study validates its effectiveness on Tonge’s 70-task problem by comparison with optimal solutions of traditional heuristics and a GA.     

A hybrid discrete particle swarm optimization algorithm for solving fuzzy job shop scheduling problem

In this paper, a hybrid algorithm combining particle swarm optimization (PSO) and tabu search (TS) is proposed to solve the job shop scheduling problem with fuzzy processing time. The object is to minimize the maximum fuzzy completion time, i.e., the fuzzy makespan. In the proposed algorithm, PSO performs the global search, i.e., the exploration phase, while TS conducts the local search, i.e., the exploitation process. The global best particle is used to direct other particles to optimal search space. Therefore, in the proposed algorithm, TS-based local search approach is applied to the global best particle to conduct find-grained exploitation. In order to share information among particles, one-point crossover operator is embedded in the hybrid algorithm. The proposed algorithm is tested on sets of the well-known benchmark instances. Through the analysis of experimental results, the highly effective performance of the proposed algorithm is shown against the best performing algorithms from the literature.     

A hybrid random-key genetic algorithm to minimize weighted number of late deliveries for a single machine

This paper presents a memetic algorithm (MA) to minimize the total weighted number of late jobs (or deliveries) on a single machine. The proposed MA combines a genetic algorithm (GA) with a neighborhood search. The performance of the proposed algorithm is compared with four heuristics from the literature, namely the early due date (EDD), the weighted shortest processing time (WSPT), the forward algorithm (FA), and the weighted forward algorithm (WFA), against 10 benchmark problems and three real-world problems. The results suggest that the MA outperformed the EDD, WSPT, FA, and WFA on the benchmark problems and performed as good as WFA on two of the three real-world problems and outperformed WFA on one real-world problem. The EDD performed the worst among the five solution approaches.     

Optimization of cutting conditions during continuous finished profile machining using non-traditional techniques

Optimum machining parameters are of great concern in manufacturing environments, where economy of machining operation plays a key role in competitiveness in the market. Many researchers have dealt with the optimization of machining parameters for turning operations with constant diameters only. All Computer Numerical Control (CNC) machines produce the finished components from the bar stock. Finished profiles consist of straight turning, facing, taper and circular machining.This research work concentrates on optimizing the machining parameters for turning cylindrical stocks into continuous finished profiles. The machining parameters in multi-pass turning are depth of cut, cutting speed and feed. The machining performance is measured by the production cost.In this paper the optimal machining parameters for continuous profile machining are determined with respect to the minimum production cost subject to a set of practical constraints. The constraints considered in this problem are cutting force, power constraint, tool tip temperature, etc. Due to high complexity of this machining optimization problem, six non-traditional algorithms, the genetic algorithm (GA), simulated annealing algorithm (SA), Tabu search algorithm (TS), memetic algorithm (MA), ants colony algorithm (ACO) and the particle swarm optimization (PSO) have been employed to resolve this problem. The results obtained from GA, SA,TS, ACO, MA and PSO are compared for various profiles. Also, a comprehensive user-friendly software package has been developed to input the profile interactively and to obtain the optimal parameters using all six algorithms. New evolutionary PSO is explained with an illustration .     

A fuzzy-neural approach for estimating the monthly output of a semiconductor manufacturing factory

The customer order scheduling problem (COSP) is defined as to determine the sequence of tasks to satisfy the demand of customers who order several types of products produced on a single machine. A setup is required whenever a product type is launched. The objective of the scheduling problem is to minimize the average customer order flow time. Since the customer order scheduling problem is known to be strongly NP-hard, we solve it using four major metaheuristics and compare the performance of these heuristics, namely, simulated annealing, genetic algorithms, tabu search, and ant colony optimization. These are selected to represent various characteristics of metaheuristics: nature-inspired vs. artificially created, population-based vs. local search, etc. A set of problems is generated to compare the solution quality and computational efforts of these heuristics. Results of the experimentation show that tabu search and ant colony perform better for large problems whereas simulated annealing performs best in small-size problems. Some conclusions are also drawn on the interactions between various problem parameters and the performance of the heuristics.     

An intensive search evolutionary algorithm for single-machine total-weighted-tardiness scheduling problems

In this paper, an intensive search evolutionary algorithm is proposed to solve single machine total weighted tardiness scheduling problems. A specialised locally improved random swap mutation operator and an ordered crossover operator are used for evolution. The proposed algorithm starts with a pair of sequences: one generated by a greedy heuristic, namely, a backward phase heuristic acts as one parent, and a randomly generated sequence acts as the other. A computational experiment is conducted by applying the mutation operator on the backward phase sequence and the proposed algorithm with the same number of generations as the termination criteria. A total of 125 benchmark instances for sizes 40, 50 and 100 available in the OR library are solved and the results are compared with the available best-known results. It is observed that the proposed evolutionary algorithm provides better results than others .     

Tabu search for multiple-criteria manufacturing cell design

Cellular manufacturing (CM) is an important application of group technology (GT) in which families of parts are produced in manufacturing cells or in a group of various machines. Cell design/formation is the first step in the design of cellular manufacturing systems. Many efforts have been made towards cell design taking into consideration multiple criteria. This paper presents a Pareto-optimality-based multi-objective tabu search (MOTS) algorithm to the machine-part grouping problems with multiple objectives: minimizing the weighted sum of inter-cell and intra-cell moves and minimizing the total cell load variation A new approach is developed to evaluate the non-dominance of solutions produced by the tabu search. Comparisons between MOTS and the genetic algorithm (GA) are done and the results show that MOTS is quite promising in multi-objective cell design .     

Sequencing of an M machine flow shop with setup, processing and removal times separated

In this research, a flow shop scheduling problem in which setup, processing and removal times are separated, with the objective of minimizing makespan, is considered. A tabu search based heuristic is presented for solving the addressed problem. The proposed heuristic begins with the construction of artificial processing times for each operation; then a modified NEH algorithm is used to generate an initial solution, followed by a designed tabu search procedure applied for further improvement of the solution. The proposed heuristic, as well as the existing one, is evaluated in a large number of randomly generated problems. The results of the experimental investigations of the proposed heuristic algorithm and the existing heuristic in meeting the objective of makespan are also reported. It is found that the solution quality of the proposed tabu search heuristic is better than that of the existing heuristic, but for large size problems more computational efforts are needed; however, the CPU time is still acceptable.     

Tabu search for multiple-criteria manufacturing cell design

Cellular manufacturing (CM) is an important application of group technology (GT) in which families of parts are produced in manufacturing cells or in a group of various machines. Cell design/formation is the first step in the design of cellular manufacturing systems. Many efforts have been made towards cell design taking into consideration multiple criteria. This paper presents a Pareto-optimality-based multi-objective tabu search (MOTS) algorithm to the machine-part grouping problems with multiple objectives: minimizing the weighted sum of inter-cell and intra-cell moves and minimizing the total cell load variation A new approach is developed to evaluate the non-dominance of solutions produced by the tabu search. Comparisons between MOTS and the genetic algorithm (GA) are done and the results show that MOTS is quite promising in multi-objective cell design.