A grammatical optimization approach for integrated process planning and scheduling

Rapid developments in computerized manufacturing environments and increasing overlapping in the capability of manufacturing resources provoked integration of many manufacturing functions including process planning scheduling. Several approaches have been developed in the literature in order to integrate process planning and scheduling. In this paper a novel approach which makes use of grammatical representation of generic process plans is used within a multiple objective tabu search framework in order to integrate process planning and scheduling effectively. Detailed explanations along with an example problem are presented in the paper. Proposed approach is tested on literature problems and also hypothetically generated flexible job shop scheduling problems with alternative process plans to analyze its performance and efficiency.     

Metaheuristics for scheduling a non-permutation flowline manufacturing cell with sequence dependent family setup times

The broad applications of cellular manufacturing make flowline manufacturing cell scheduling problems with sequence dependent family setup times a core topic in the field of scheduling. Due to computational complexity, almost all published studies focus on using permutation schedules to deal with this problem. To explore the potential effectiveness of treating this argument using non-permutation schedules, three prominent types of metaheuristics—a simulated annealing, a genetic algorithm and a tabu search—are proposed and empirically evaluated. The experimental results demonstrate that in general, the improvement made by non-permutation schedules over permutation schedules for the due-date-based performance criteria were significantly better than that for the completion-time-based criteria. The results of this study will provide practitioners a guideline as to when to adopt a non-permutation schedule, which may exhibit better performance with additional computational efforts.     

A GA-Tabu algorithm for scheduling in-line steppers in low-yield scenarios

This paper presents a scheduling algorithm for an in-line stepper in low-yield scenarios, which mostly appear in cases when new process/production is introduced. An in-line stepper is a bottleneck machine in a semiconductor fab. Its interior comprises a sequence of chambers, while its exterior is a dock equipped with several ports. The transportation unit for entry of each port is a job (a group of wafers), while that for each chamber is a piece of wafer. This transportation incompatibility may lead to a capacity-loss, in particular in low-yield scenarios. Such a capacity-loss could be alleviated by effective scheduling. The proposed scheduling algorithm, called GA-Tabu, is a combination of a genetic algorithm (GA) and a tabu search technique. Numerical experiments indicate that the GA-Tabu algorithm outperforms seven benchmark ones. In particular, the GA-Tabu algorithm outperforms a prior GA both in solution quality and computation efforts.     

Integrated process planning and scheduling in a supply chain

This paper deals with the integration of process planning and scheduling, which is one of the most important functions in a supply chain to achieve high quality products at lower cost, lower inventory, and high level of performance. Solving the problem is essential for the generation of flexible process sequences with resource selection and for the decision of the operation schedules that can minimize makespan. We formulate a mixed integer programming model to solve this problem of integration. This model considers alternative resources: sequences and precedence constraints. To solve the model, we develop a new evolutionary search approach based on a topological sort. We use the topological sort to generate a set of feasible sequences in the model within a reasonable computing time. Since precedence constraints between operations are handled by the topological sort, the developed evolutionary search approach produces only feasible solutions. The experimental results using various sizes of problems provide a way to demonstrate the efficiency of the developed evolutionary search approach.     

Bicriteria scheduling problem for unrelated parallel machines with release dates

This research proposes a heuristic and a tabu search algorithm (TSA) to find non-dominated solutions to bicriteria unrelated parallel machine scheduling problems with release dates. The two objective functions considered in this problem are to minimize both makespan and total weighted tardiness. The computational results show that the proposed heuristic is computationally efficient and provides solutions of reasonable quality. The proposed TSA outperforms other algorithms in terms of the number of non-dominated solutions and the quality of its solutions.     

Effect of solution representations on Tabu search in scheduling applications

This research investigates the application of meta-heuristic algorithms to a scheduling problem called permutation manufacturing-cell flow shop (PMFS) from two perspectives. First, we examine the effect of using different solution representations (S_new and S_old) while applying Tabu-search algorithm. Experimental results reveal that Tabu_S_new outperforms Tabu_S_old. The rationale why Tabu_S_new is superior is further examined by characterizing the intermediate outcomes of the evolutionary processes in these two algorithms. We find that the superiority of S_new is due to its relatively higher degree of freedom in modeling Tabu neighborhood. Second, we propose a new algorithm GA_Tabu_S_new, which empirically outperforms the state-of-the-art meta-heuristic algorithms in solving the PMFS problem. This research highlights the importance of solution representation in the application of meta-heuristic algorithm, and establishes a significant milestone in solving the PMFS problem.     

An active learning genetic algorithm for integrated process planning and scheduling

In traditional approaches, process planning and scheduling are carried out sequentially, where scheduling is done separately after the process plan has been generated. However, the functions of these two systems are usually complementary. The traditional approach has become an obstacle to improve the productivity and responsiveness of the manufacturing system. If the two systems can be integrated more tightly, greater performance and higher productivity of a manufacturing system can be achieved. Therefore, the research on the integrated process planning and scheduling (IPPS) problem is necessary. In this paper, a new active learning genetic algorithm based method has been developed to facilitate the integration and optimization of these two systems. Experimental studies have been used to test the approach, and the comparisons have been made between this approach and some previous approaches to indicate the adaptability and superiority of the proposed approach. The experimental results show that the proposed approach is a promising and very effective method on the research of the IPPS problem.     

A tabu search algorithm for order acceptance and scheduling

We consider a make-to-order production system, where limited production capacity and order delivery requirements necessitate selective acceptance of the orders. Since tardiness penalties cause loss of revenue, scheduling and order acceptance decisions must be taken jointly to maximize total revenue. We present a tabu search algorithm that solves the order acceptance and scheduling problem on a single machine with release dates and sequence dependent setup times. We analyze the performance of the tabu search algorithm on an extensive set of test instances with up to 100 orders and compare it with two heuristics from the literature. In the comparison, we report optimality gaps which are calculated with respect to bounds generated from a mixed integer programming formulation. The results show that the tabu search algorithm gives near optimal solutions that are significantly better compared to the solutions given by the two heuristics. Furthermore, the run time of the tabu search algorithm is very small, even for 100 orders. The success of the proposed heuristic largely depends on its capability to incorporate in its search acceptance and scheduling decisions simultaneously.     

Project-driven planning and scheduling support for virtual manufacturing

The paper addresses the issue of decision-making support for small and medium-size enterprises operating within a virtual project-driven enterprise environment. The problem considered here can be defined in terms of finding a feasible schedule that satisfies the constraints imposed by the work-order duration, the price, and the time-constrained resource availability. The problem belongs to the class of multi-mode case problems of project scheduling, where finding a feasible solution is NP-hard. A heuristic method for process planning and scheduling is proposed. The method is based on a critical path approach and the branch and bound search scheme. It has been implemented in a web-enabled interactive software package, and is illustrated using the example of a virtual construction enterprise. Received: February 2005 / Accepted: January 2006     

A GES/TS algorithm for the job shop scheduling

The job shop scheduling problem is a difficult combinatorial optimization problem. This paper presents a hybrid algorithm which combines global equilibrium search, path relinking and tabu search to solve the job shop scheduling problem. The proposed algorithm used biased random sampling to have a better covering of the solution space. In addition, a new version of N6 neighborhood is applied in a tabu search framework. In order to evaluate the algorithm, comprehensive tests are applied to it using various standard benchmark sets. Computational results confirm the effectiveness of the algorithm and its high speed. Besides, 19 new upper bounds among the unsolved problems are found.     

Mathematical modeling and evolutionary algorithm-based approach for integrated process planning and scheduling

Traditionally, process planning and scheduling were performed sequentially, where scheduling was implemented after process plans had been generated. Considering their complementarity, it is necessary to integrate these two functions more tightly to improve the performance of a manufacturing system greatly. In this paper, a mathematical model of integrated process planning and scheduling has been formulated. And, an evolutionary algorithm-based approach has been developed to facilitate the integration and optimization of these two functions. To improve the optimized performance of the approach, efficient genetic representation and operator schemes have been developed. To verify the feasibility and performance of the proposed approach, experimental studies have been conducted and comparisons have been made between this approach and some previous works. The experimental results show that the integrated process planning and scheduling is necessary and the proposed approach has achieved significant improvement.     

A tabu method for a two-agent single-machine scheduling with deterioration jobs

In recent 10 years, the multi-agent idea applied in scheduling issues has received continuing attention. However, the study of the multi-agent scheduling with deteriorating jobs is relatively limited. In light of this, this paper deliberates upon a two-agent single-machine scheduling problem with deteriorating jobs. Taking the proposed model, the actual processing time of a job from both the first agent and the second agent is modeled as a linearly increasing function of its starting time. The goal of this paper is to minimize the total weighted number of tardy jobs of the first agent subject to the condition that the maximum lateness of the second agent is allowed to have an upper bound. The complexity of the model concerned in the paper is claimed as an NP-hard one. Following that, several dominance rules and a lower bound are proposed to be applied in a branch-and-bound algorithm for the optimal solution, and a tabu algorithm is applied to find near-optimal solutions for the problem. The simulation results obtained from all the proposed algorithms are also reported.     

Integration of process planning and scheduling—A modified genetic algorithm-based approach

Traditionally, process planning and scheduling for parts were carried out in a sequential way, where scheduling was done after process plans had been generated. Considering the fact that the two functions are usually complementary, it is necessary to integrate them more tightly so that performance of a manufacturing system can be improved greatly. In this paper, a new integration model and a modified genetic algorithm-based approach have been developed to facilitate the integration and optimization of the two functions. In the model, process planning and scheduling functions are carried out simultaneously. In order to improve the optimized performance of the modified genetic algorithm-based approach, more efficient genetic representations and operator schemes have been developed. Experimental studies have been conducted and the comparisons have been made between this approach and others to indicate the superiority and adaptability of this method. The experimental results show that the proposed approach is a promising and very effective method for the integration of process planning and scheduling.     

Algorithms for the generalized weighted frequency assignment problem

We report the performance of 15 construction heuristics to find initial solutions, and 4 search algorithms to solve a frequency assignment problem where the value of an assigned frequency is determined by the site where it is assigned. The algorithms were tested on 3 sets of problems, the first one corresponds to the well-known Philadelphia problems, and the last two correspond to situations frequently encountered when FM frequencies are assigned in Mexico. Our experimental results show that the construction heuristics that consider the weights of the sites perform well. Among the 4 search algorithms tested, the one based on cross entropy performed better than the others in small problems, whereas in large problems the algorithm based on simulated annealing performed the best.     

Tabu search and lower bound for an industrial complex shop scheduling problem

This paper deals with an industrial shop scheduling problem that arises in a metal goods production group. The scheduling problem can be seen as a multi-mode job shop with assembly. Jobs have additional constraints such as release date, due date and sequence-dependent setup times. The aim of the decision-makers is to minimize the maximum lateness. This article introduces a tabu search procedure to solve the whole problem and a valid lower bound used to evaluate the tabu search procedure.     

Mathematical modeling and heuristic approaches to flexible job shop scheduling problems

Scheduling for the flexible job shop is very important in both fields of production management and combinatorial optimization. However, it is quite difficult to achieve an optimal solution to this problem in medium and actual size problem with traditional optimization approaches owing to the high computational complexity. For solving the realistic case with more than two jobs, two types of approaches have been used: hierarchical approaches and integrated approaches. In hierarchical approaches assignment of operations to machines and the sequencing of operations on the resources or machines are treated separately, i.e., assignment and sequencing are considered independently, where in integrated approaches, assignment and sequencing are not differentiated. In this paper, a mathematical model and heuristic approaches for flexible job shop scheduling problems (FJSP) are considered. Mathematical model is used to achieve optimal solution for small size problems. Since FJSP is NP-hard problem, two heuristics approaches involve of integrated and hierarchical approaches are developed to solve the real size problems. Six different hybrid searching structures depending on used searching approach and heuristics are presented in this paper. Numerical experiments are used to evaluate the performance of the developed algorithms. It is concluded that, the hierarchical algorithms have better performance than integrated algorithms and the algorithm which use tabu search and simulated annealing heuristics for assignment and sequencing problems consecutively is more suitable than the other algorithms. Also the numerical experiments validate the quality of the proposed algorithms.     

一种基于混合遗传算法的聚类方法

针对遗传算法在聚类时存在的搜索速度慢和早熟的问题,将禁忌搜索的自适应优点引入遗传操作来改良其全局搜索性能,并采用带有权重的相似性度量方法,提出了一种基于混合遗传算法的聚类算法.通过与常用的聚类方法的实验结果比较,表明这种方法具有良好的聚类效果.     

A new heuristic for scheduling the two-stage flowshop with additional resources

This paper deals with the problem of preemptive scheduling in a two-stage flowshop with parallel unrelated machines at the first stage and a single machine at the second stage. At the first stage, jobs use some additional resources which are available in limited quantities at any time. The resource requirements are of 0–1 type. The objective is the minimization of makespan. The problem is NP-hard. Heuristic algorithms are proposed which solve to optimality the resource constrained scheduling problem at the first stage of the flowshop, and at the same time, minimize the makespan in the flowshop by selecting appropriate jobs for simultaneous processing. Several rules of job selection are considered. The performance of the proposed heuristic algorithms is analyzed by comparing solutions with the lower bound on the optimal makespan. The extensive computational experiment shows that the proposed heuristic algorithms are able to produce near-optimal solutions in short computational time.     

禁忌结合遗传结果对配送路径优化的应用研究

在建立物流配送路径优化问题数学模型的基础上,构造了求解该问题的混合算法,并进行了实验计算.计算结果表明,用混合算法进行物流配送路径优化,可以方便有效地求得问题的最优解或近似最优解,结果稳定性高.