A divide-and-conquer strategy with particle swarm optimization for the job shop scheduling problem

An optimization algorithm based on the ‘divide-and-conquer’ methodology is proposed for solving large job shop scheduling problems with the objective of minimizing total weighted tardiness. The algorithm adopts a non-iterative framework. It first searches for a promising decomposition policy for the operation set by using a simulated annealing procedure in which the solutions are evaluated with reference to the upper bound and the lower bound of the final objective value. Subproblems are then constructed according to the output decomposition policy and each subproblem is related to a subset of operations from the original operation set. Subsequently, all these subproblems are sequentially solved by a particle swarm optimization algorithm, which leads directly to a feasible solution to the original large-scale scheduling problem. Numerical computational experiments are carried out for both randomly generated test problems and the real-world production data from a large speed-reducer factory in China. Results show that the proposed algorithm can achieve satisfactory solution quality within reasonable computational time for large-scale job shop scheduling problems.     

Application of genetic algorithms with dominant genes in a distributed scheduling problem in flexible manufacturing systems

Multi-factory production networks have increased in recent years. With the factories located in different geographic areas, companies can benefit from various advantages, such as closeness to their customers, and can respond faster to market changes. Products (jobs) in the network can usually be produced in more than one factory. However, each factory has its operations efficiency, capacity, and utilization level. Allocation of jobs inappropriately in a factory will produce high cost, long lead time, overloading or idling resources, etc. This makes distributed scheduling more complicated than classical production scheduling problems because it has to determine how to allocate the jobs into suitable factories, and simultaneously determine the production scheduling in each factory as well. The problem is even more complicated when alternative production routing is allowed in the factories. This paper proposed a genetic algorithm with dominant genes to deal with distributed scheduling problems, especially in a flexible manufacturing system (FMS) environment. The idea of dominant genes is to identify and record the critical genes in the chromosome and to enhance the performance of genetic search. To testify and benchmark the optimization reliability, the proposed algorithm has been compared with other approaches on several distributed scheduling problems. These comparisons demonstrate the importance of distributed scheduling and indicate the optimization reliability of the proposed algorithm.     

Jointly solving the group scheduling and machining speed selection problems: A hybrid tabu search and simulated annealing approach

In a cellular manufacturing environment, once the machines and parts have been grouped the remaining tasks are sequencing part families and scheduling operations for the parts within each part family so that some planning goals such as minimization of tardiness can be achieved. This type of problem is called group scheduling and will be analysed in this paper. The solution of the group scheduling is affected by the machining speed specified for each operation since the completion time of each operation is a function of machining speed. As such, the group scheduling and machining speed selection problems should be simultaneously solved to provide meaningful solutions. This, however, further complicates the solution procedure. In view of this, a hybrid tabu-simulated annealing approach is proposed to solve the group scheduling problem. The main advantage of this approach is that a short term memory provided by the tabu list can be used to avoid solution re-visits while preserving the stochastic nature of the simulated annealing method. The performance of this new method has been tested and favourably compared with two other algorithms using tabu search and simulated annealing alone.     

Design and scheduling of hybridmulti-cell flexible manufacturing systems

The objective of this paper is to minimize machine duplication by increasing its utilization, minimize intercell moves, simplify the scheduling problem and increase the flexibility of the manufacturing system. An integrated approach of design and scheduling alternative hybrid multi-cell flexible manufacturing systems (MCFMSs) in four steps will be presented in this paper. The first step is the implementation of branch and bound techniques which provide tools to design group technology (GT) cells. The second step is balancing the inter-cell workload of GT cells which leads to a hybrid MCFMS with better utilization of the machines. The problem of the exception machines and their utilization and workload balance will be solved within the MCFMScentre. Thus the performance of GT cells can be improved by transferring workloads from a congested (bottleneck) machine in one cell to an alternative one, a less congested (exception) machine in another cell within a group of GT cells forming a MCFMS centre. The third step is the group scheduling; a proposed heuristic method will be used for the scheduling of a family of parts with the objective of minimizing the maximum completion time of each part. The problem of scheduling under MCFMS can be reduced by considering the scheduling of each family of parts. Finally, the flexibility of the system will be enhanced by selecting appropriate machine tools and flexible material handling equipments. This approach is both effective and efficient-it has generated a hybrid MCFMS centre which includes several alternatives, for some benchmark problems in much shorter time than algorithms previously reported in the literature. In addition, the method is conceptually simple and easy to implement.     

A System for Manufacturing Scheduling with Interactive Computer Graphics

This article describes experience in developing an interactive factory scheduling system using computer graphics. The implementation contains three parts, each of which is graphically displayed and manipulated: a network-based model for describing the basic operation of the factory, a Gantt chart for scheduling the factory, and plots of inventory levels over time for evaluating the schedule. The system was implemented at Cornell's instructional computer graphics facility and used for teaching for a period of three years.     

GT cell formation for minimizing the intercell parts flow

A methodology is proposed to design a GT cell by considering the intercell parts flow in GT cellular manufacturing systems. The problem of GT cell formation is described in a graph using the quantities to be produced in the specified time period and the process routes for producing the products. The objective of this paper is to minimize the total number of parts produced in more than one cell. The problem, formulated as a quadratic assignment problem (QAP), is solved using both Lagrangean relaxation technique and the optimality conditions of quadratic program. Furthermore, in order to obtain the giobal optimal solution rather than the local optimal solution, a branch-and-bound algorithm is employed. Finally, numerical examples are used to show the effectiveness of the solution techniques and GT cell formation procedure. Moreover, a computer simulation is presented, showing the effectiveness of cellular manufacturing systems     

Mixed Self-adapting GA Optimal Scheduling Algorithm for a Multiple Resource Job-shop

With an aim at the job-shop scheduling problem of multiple resource constraints, this paper presents mixed self-adapting Genetic Algorithm （ GA ） , and establishes a job-shop optimal scheduling model of multiple resource constraints based on the effect of priority scheduling rules in the heuristic algorithm upon the scheduling target. New coding regulations or rules are designed. The sinusoidal function is adopted as the self-adapting factor, thus making cross probability and variable probability automatically change with group adaptability in such a way as to overcome the shortcoming in the heuristic algorithm and common GA, so that the operation efficiency is improved. The results from real example simulation and comparison with other algorithms indicate that the mixed self-adapting GA algorithm can well solve the job-shop optimal scheduling problem under the constraints of various kinds of production resources such as machine-tools and cutting tools.     

Modified Hamiltonian chain: A graph theoretic approach to group technology

Graph theory can be effectively applied to the group technology configuration problem (GTCP). Earlier attempts were made to use graph theoretic algorithms, e.g. minimal spanning tree (MST), tree search, and branch & bound to solve the group technology (GT) problem. The proposed algorithm is based on modified Hamiltonian chain (MHC) and consists of two stages. Stage I forms the graph from the machine part incidence matrix. Stage II generates a modified Hamiltonian chain which is a subgraph of the main graph developed in Stage I, and it gives machine sequence and part sequence directly. Dummy edges are considered in MHC for better accessibility in order to arrive at a block diagonal solution to the problem. This paper presents a simple approach by designing a MHC in the graph theoretic method to solve the group technology configuration problem. Results obtained from testing the method are compared with the other well-known methods and found to be satisfactory.     

The burn-in test scheduling problem with batch dependent processing time and sequence dependent setup time

The burn-in test scheduling problem (BTSP) is a variation of the complex batch processing machine scheduling problem, which is also a generalisation of the liquid crystal injection scheduling problem with incompatible product families and classical identical parallel machine problem. In the case we investigated on the BTSP, the jobs are clustered by their product families. The product families can be clustered by different product groups. In the same product group, jobs with different product families can be processed as a batch. The batch processing time is dependent on the longest processing time of those jobs in that batch. Setup times between two consecutive batches of different product groups on the same batch machine are sequentially dependent. In addition, the unequal ready times are considered in the BTSP which involves the decisions of batch formation and batch scheduling in order to minimise the total machine workload without violating due dates and the limited machine capacity restrictions. Since the BTSP involves constraints on unequal ready time, batch dependent processing time, and sequence dependent setup times, it is more difficult to solve than the classical parallel batch processing machine scheduling problem with compatible product families or incompatible product families. These restrictions mean that the existing methods cannot be applied into real-world factories directly. Consequently, this paper proposes a mixed integer programming model to solve the BTSP exactly. In addition, two efficient solution procedures which solve the BTSP are also presented.     

Scheduling a Single Machine to Minimize the Weighted Number of Tardy Jobs

In this paper the problem of scheduling jobs on a single machine to minimize the weighted number of tardy jobs is examined. It contains the framework for a new branch-and-bound procedure as well as the first extensive computational study of the problem. Results indicate that large problems, e.g. 50 jobs, can be solved in just a few seconds of computer time. Further, the computational results provide insight into how various problem parameters affect the solution difficulty of particular problems.     

A Petri-net-based state-transition model for an optimal operator cyclic walking pattern development in GT cells

An approach for developing the optimal operator scheduling solution for a group technology (GT) production problem is studied. A state-transition model is developed to analyse and gain insight into the operator-machine interaction of the problem. Operator cyclic walking patterns are then denned. A Petri net model has succeeded in determining the optimal cyclic walking pattern. The computational efforts needed for the Petri net model are compared with those for an integer programming model. The results show large savings in computational effort by using the Petri net model. In addition, the extendability of the Petri net model for various system aspects is addressed     

Scheduling the factory pick-up of new cars

Car manufacturers increasingly offer delivery programs for the factory pick-up of new cars. Such a program consists of a broad range of event-marketing activities. In this paper we investigate the problem of scheduling the delivery program activities of one day such that the sum of the customers waiting times is minimized. We show how to model this problem as a resource-constrained project scheduling problem with nonregular objective function, and we present a relaxation-based beam-search solution heuristic. The relaxations are solved by exploiting a duality relationship between temporal scheduling and min-cost network flow problems. This approach has been developed in cooperation with a German automaker. The performance of the heuristic has been evaluated based on practical and randomly generated test instances. Correspondence to: Christoph MellentienThe authors would like to thank Margit Frank (Porsche AG) and Benjamin Müller (University of Bern) for their valuable contributions to this work.     

A simple and effective heuristic for the resource constrained project scheduling problem

This paper investigates the development and application of a simple heuristic to the resource constrained project scheduling problem (RCPSP). This computer heuristic, which is based on the COMSOAL heuristic, constructs a feasible solution at each iteration and chooses the best solution of several iterations. Although COMSOAL was originally a solution approach for the assembly-line balancing problem, it can be extended to provide solutions to the resource allocation problem. The Modified COMSOAL technique presented in this paper uses priority schemes intermittently with a random selection technique. This hybrid of randomness and priority scheme allows a good solution to be found quickly while not being forced into the same solution at each iteration. Several different priority schemes are examined within this research. The COMSOAL heuristic modified with the priority schemes heuristic was tested on several established test sets and the solution values are compared with both known optimal values and the results of several other resource allocation heuristics. In the vast majority of cases, the Modified COMSOAL heuristic outperformed the other heuristics in terms of both average and maximum percentage difference from optimal. The Modified COMSOAL heuristic seems to have several advantages over other RCPSP heuristics in that it is easy to understand, easy to implement, and achieves good results.     

Cyclic scheduling in synchronous production lines

In this paper we address the scheduling problem in unpaced synchronous mixed-model production lines operated under a cyclic scheduling policy. We first discuss operations of a production line with the synchronous transfer of parts. We then present an integer programming formulation of the problem. The problem, however, is W-hard, and for its exact solution we propose an implicit enumeration scheme. We discuss a property of the scheduling problem which allows us to effectively solve large size instances of the problem. We also present an approximate solution procedure with very good avenge performance. Useful managerial insights are obtained as we search for ways to improve the performance of synchronous lines. The relaxation of one of our original assumptions in the scheduling problem formulation results in an easy problem whose solution generates the absolute best in throughput performance configuration of the production line. Implementation of this solution, however, requires increasing the number of buffers in the line. We suggest other performance improvement ways to better balance the tradeoff between throughput and average Work-In-Progress (WIP) inventory in the line.     

A Multiple criteria decision aid for personnel scheduling

The personnel scheduling problem is addressed through a multiple-criteria decision system. A four-stage process is proposed which utilizes analytic models and computer simulation to develop an aggregate shift schedule. The scheduler plays a key role in generating the personnel schedule. A queueing model converts customer (task) arrival rates into personnel requirements for each scheduling period. A goal programming model utilizes these personnel requirements to generate a shift schedule, allowing the decision maker a choice in establishing scheduling priorities. Priorities can be established for workforce levels in particular periods (from two distinct points of reference), full-time workforce levels, and part-time workforce levels. By varying priority relationships, different shift schedules result. A computer simulation model is included to evaluate the schedule generated by the goal program. The results of the simulation provide the decision maker with schedule performance information. Based upon this information, the scheduler can accept the schedule, revise the schedule, or revise certain model parameters and cycle back through the solution process. The flexibility of the scheduling model is illustrated through example priority formulations and a sample scheduling problem.     

Change to group technology: process organization is obsolete

The traditional type of organization for manufacturing is process organization, in which organizational units each specialize in a particular process. This is gradually being replaced by product organization; in the form of either continuous line flow (CLF), or group technology (GT). Group technology (GT) is a method of organization for manufacturing, in which the organizational units (groups) complete all the parts they make at their particular processing stage, and are equipped with all the machines and other facilities they need to do so. CLF is the preferred type of organization for process industries, and for a few cases of mass production in other types of industry. GT is the preferred type of organization for batch and jobbing production. This paper submits that if ’Production flow analysis’ (PFA) is used to plan the division into GROUPS of machines and associated FAMILIES of parts, then it is always possible in batch and jobbing production, to find a total division into groups, with very few exceptions and with no back-flow or cross-flow between groups. It bases this submission on 33 listed examples from practice, and on the observation that because most routeing data is very flexible, it would be very surprising if one ever found a case where GT was impossible. As GT is always possible where it is appropriate, and can always lead to major increases in efficiency, it follows that process organization is obsolete.     

A hybrid flowshop scheduling problem for a cold treating process in seamless steel tube production

Seamless steel tubes often have various categories and specifications, which further require complicated operations in production, especially in the cold treating process (CTP). This paper investigates the scheduling problem using the seamless tube plant of Baoshan Iron and Steel Complex as a study background. By considering the practical production constraints such as sequence-dependent setup times, maintenance schedule, intermediate material buffers, job-machine matches, we formulate the hybrid flowshop scheduling problem with a non-linear mixed integer programming model (NMIP). In addition, our model provides a flexibility to remove the permutation assumption, which is often a limitation in early studies. In order to obtain the solution of the above NMIP problem, a two-stage heuristic algorithm is proposed and it combines a modified genetic algorithm and a local search method. With real production instances, our computation experiments indicate that the proposed algorithm is efficient and it outperforms several other approaches. Industrial implementation also shows that such a scheduling tool brings a cost saving of more than 10% and it substantially reduces the computation time. Our study also illustrates the need of relaxing permutation assumption in such a scheduling problem with complicated operation sequences.     

Group technology in the US manufacturing industry: A survey of current practices

This paper reports the findings of a survey of 53 US users of group technology (GT). Respondent installations were medium to large electronics and metalworking manufacturers. They engaged predominantly in fabrication activities, producing a large number of component parts and/or end items. These firms applied GT to design, process planning (including NC programming), sales, purchasing, cost estimation, tooling, scheduling, new equipment sizing, and tool selection. In the majority of cases, firms used classification and coding systems as tools in applying GT. While users identified managerial and technical barriers which must be overcome in successfully applying GT, significant and varied operational and strategic benefits had been achieved. Further, most felt that GT would be an integral and important part of future CAD/CAM activities at their plant. The respondents' experiences confirm that GT's usefulness is quite broad and suggest that failure to understand GT as a general philosophy and, instead, to consider it a tool or equate it with a specific use, may result in lost opportunities to improve manufacturing productivity. A second paper, based on the same survey data, describes these manufacturers' experiences with cellular manufacturing (Wemmerlov and Hyer 1989).     

Production scheduling in almost continuous time

We present a large-scale production scheduling problem where each order is unique and the processing time for an operation can be close to the size of a time period. Because modeling the problem as a multiprocessor flowshop results in a computationally intractable formulation, we cast the problem in production planning terms and extract a production schedule from the solution. To solve our model, we introduce the notion of 'almost continuous time' and show how to obtain good solutions to large problems efficiently.     

Finite capacity scheduling using a predetermined placement sequence

This paper presents a new heuristic for the finite capacity scheduling of factories. It treats the task of scheduling a factory the same as scheduling a large project that has many delivery points. The job placement sequence on machines is used as a link between infinite capacity schedules and finite capacity schedules. An ideal placement sequence is proposed from the infinite capacity backward schedule and this is embedded into the project network for finite capacity scheduling. This allows a finite capacity algorithm whose boundary condition is the most tightly packed schedule possible, and is also ideal from a cash flow perspective. The paper proposes a preference list of machines as an integral part of the scheduling process and shows how to switch between machines using preferences. It also shows how to integrate infinite and finite capacity schedules within the same algorithm by using a parameter called the constraint horizon. The heuristic is explained using input-output matrices and by working through an example of a project network. The example includes a discussion of circuits and a detailed explanation of how to implement the heuristic in a computer program.