A review on integrated process planning and scheduling <s> Brief review of scheduling <s> We describe an approximation method for solving the minimum makespan problem of job shop scheduling. It sequences the machines one by one, successively, taking each time the machine identified as a bottleneck among the machines not yet sequenced. Every time after a new machine is sequenced, all previously established sequences are locally reoptimized. Both the bottleneck identification and the local reoptimization procedures are based on repeatedly solving certain one-machine scheduling problems. Besides this straight version of the Shifting Bottleneck Procedure, we have also implemented a version that applies the procedure to the nodes of a partial search tree. Computational testing shows that our approach yields consistently better results than other procedures discussed in the literature. A high point of our computational testing occurred when the enumerative version of the Shifting Bottleneck Procedure found in a little over five minutes an optimal schedule to a notorious ten machines/ten jobs problem on which many algorithms have been run for hours without finding an optimal solution. <s> BIB001 </s> A review on integrated process planning and scheduling <s> Brief review of scheduling <s> In this paper, we propose a branch and bound method for solving the job-shop problem. It is based on one-machine scheduling problems and is made more efficient by several propositions which limit the search tree by using immediate selections. ::: ::: It solved for the first time the famous 10 × 10 job-shop problem proposed by Muth and Thompson in 1963. <s> BIB002 </s> A review on integrated process planning and scheduling <s> Brief review of scheduling <s> We describe an approximation algorithm for the problem of finding the minimum makespan in a job shop. The algorithm is based on simulated annealing, a generalization of the well known iterative improvement approach to combinatorial optimization problems. The generalization involves the acceptance of cost-increasing transitions with a nonzero probability to avoid getting stuck in local minima. We prove that our algorithm asymptotically converges in probability to a globally minimal solution, despite the fact that the Markov chains generated by the algorithm are generally not irreducible. Computational experiments show that our algorithm can find shorter makespans than two recent approximation approaches that are more tailored to the job shop scheduling problem. This is, however, at the cost of large running times. <s> BIB003 </s> A review on integrated process planning and scheduling <s> Brief review of scheduling <s> Abstract A fast branch and bound algorithm for the job-shop scheduling problem has been developed. Among other hard problems it solves the 10 × 10 benchmark problem which has been open for more than 20 years. We will give a complete description of this algorithm and will present computational results. <s> BIB004 </s> A review on integrated process planning and scheduling <s> Brief review of scheduling <s> We apply the global optimization technique called taboo search to the job shop scheduling problem and show that our method is typically more efficient than the shifting bottleneck procedure, and also more efficient than a recently proposed simulated annealing implementation. We also identify a type of problem for which taboo search provides an optimal solution in a polynomial mean time in practice, while an implementation of the shifting bottleneck procedure seems to take an exponential amount of computation time. Included are computational results that establish new best solutions for a number of benchmark problems from the literature. Finally, we give a fast parallel algorithm that provides good solutions to very large problems in a very short computation time. INFORMS Journal on Computing , ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499. <s> BIB005 </s> A review on integrated process planning and scheduling <s> Brief review of scheduling <s> We present a computational performance analysis of local search algorithms for job shop scheduling. The algorithms under investigation are iterative improvement, simulated annealing, threshold accepting and genetic local search. Our study shows that simulated annealing performs best in the sense that it finds better solutions than the other algorithms within the same amount of running time. Compared to more tailored algorithms, simulated annealing still finds the best results but only under the assumption that running time is of no concern. <s> BIB006 </s> A review on integrated process planning and scheduling <s> Brief review of scheduling <s> In this paper we introduce a genetic algorithm whose peculiarities are the introduction of an encoding based on preference rules and an updating step which speeds up the evolutionary process. This method improves on the results gained previously with Genetic Algorithms and has shown itself to be competitive with other heuristics. The same algorithm has been applied to flow shop problems, revealing itself to be considerably more effective than Branch and Bound techniques. <s> BIB007 </s> A review on integrated process planning and scheduling <s> Brief review of scheduling <s> A job shop consists of a set of different machines that perform operations on jobs. Each job has a specified processing order through the machines, i.e. a job is composed of an ordered list of operations each of which is determined by the machine required and the processing time on it. There are no precedence constraints among operations of different jobs. Operations can not be interrupted (non-preemption) and each machine can handle only one job at a time. Consequently, each job can be performed on only one machine at a time. The operation sequences on the machines are unknown and have to be determined in order to minimize the makespan, i. e. the time required to complete all jobs. <s> BIB008 </s> A review on integrated process planning and scheduling <s> Brief review of scheduling <s> Abstract Due to the stubborn nature of the deterministic job-shop scheduling problem many solutions proposed are of hybrid construction cutting across the traditional disciplines. The problem has been investigated from a variety of perspectives resulting in several analytical techniques combining generic as well as problem specific strategies. We seek to assess a subclass of this problem in which the objective is minimising makespan, by providing an overview of the history, the techniques used and the researchers involved. The sense and direction of their work is evaluated by assessing the reported results of their techniques on the available benchmark problems. From these results the current situation and pointers for future work are provided. © 1999 Elsevier Science B.V. All rights reserved. <s> BIB009 </s> A review on integrated process planning and scheduling <s> Brief review of scheduling <s> In recent years, a few researchers have addressed the need for the integration of process planning and scheduling functions in order to achieve superior overall system performance. Many of these researchers have discovered that the potential savings are substantial when process planning and scheduling are integrated. It has been reported that typical scheduling objectives, such as minimizing makespan, maximizing equipment utilization, etc, can be significantly improved as the result of integration of these two important manufacturing system functions. In this paper, we present a review of the reported research in this area, discuss the extent of applicability of various approaches, and suggest directions for future research. <s> BIB010 </s> A review on integrated process planning and scheduling <s> Brief review of scheduling <s> The job shop scheduling problem (JSP) is one of the most notoriously intractable NP-complete optimization problems. Over the last 10-15 years, tabu search (TS) has emerged as an effective algorithmic approach for the JSP. However, the quality of solutions found by tabu search approach depends on the initial solution. To overcome this problem and provide a robust and efficient methodology for the JSP, the heuristics search approach combining simulated annealing (SA) and TS strategy is developed. The main principle of this approach is that SA is used to find the elite solutions inside big valley (BV) so that TS can re-intensify search from the promising solutions. This hybrid algorithm is tested on the standard benchmark sets and compared with the other approaches. The computational results show that the proposed algorithm could obtain the high-quality solutions within reasonable computing times. For example, 17 new upper bounds among the unsolved problems are found in a short time. <s> BIB011
Scheduling is the process to allocate the operations to time intervals on the machines. A scheduling problem can be classified into different types based on four parameters  : job arrival patterns, number of machines in the shop, flow patterns in the shop and the criteria by which the schedule is to be evaluated. Among various scheduling types, job shop scheduling is one of the most important scheduling types. Job shop Scheduling Problem (JSP) can be defined as  : given a set of n jobs, which are to be processed on m machines with defined technological constraints for each job, find a sequence in which jobs pass between machines such that it satisfies the technological constraints and it is optimal with respect to some performance criteria BIB010 . The JSP is one of the hardest combinatorial optimisation problems. It is widely acknowledged as one of the most difficult NP-complete problems  . JSP has been studied by a significant number of researchers. Many optimisation algorithms and approximation algorithms have been proposed. The optimisation algorithms, which are mainly based on the brand and bound scheme such as BIB002 BIB002 BIB004 , have been successfully applied in solving small instances. However, they could not solve instances larger than 250 operations in a reasonable time. On the other hand, approximation algorithms, which include priority dispatch, shifting bottleneck approach, meta-heuristic methods and so on, provide quite good alternatives for the JSP. Approximation algorithms were first developed on the basis of dispatching rules, which were very fast, but the quality of solutions that they provided usually leaves plenty of room for improvement. A more elaborate algorithm, which could produce considerably better approximations at a higher computational cost, is the shifting bottleneck approach proposed by BIB001 . More recently, the meta-heuristic methods, such as Genetic Algorithm (GA) BIB007 , Simulated Annealing (SA) BIB003 and Tabu Search (TS) BIB005  BIB011 , could provide the high-quality solutions with reasonable computing time and have captured the attention of many researchers. The relevant researches had been summarised in BIB006 , BIB008 , and BIB009 .