Decomposition Methods for Complex Factory Scheduling Problems

The rapidly changing and highly competitive nature of today’s global markets have made manufacturing management practices an important weapon in companies’ competitive arsenal. The drive towards customer satisfaction brought by the Total Quality Management (TQM) movement has resulted in companies facing more stringent demands from their customers to reduce lead times and improve delivery performance. Customers are also demanding more customized products, resulting in a more diverse product mix than was previously the case. In addition, many production processes, such as those in electronics manufacturing, are rapidly becoming more complex as new, innovative technologies are deployed.

The basic thesis of this work, as mentioned in the previous chapter, is the need for research applying the extensive body of knowledge developed by scheduling research to actual industrial problems. It is thus necessary to start from an industrial problem, develop an acceptable formulation as a scheduling problem and relate it to the existing body of theory. In this work, the motivating industrial applications are drawn from the semiconductor industry. Hence in this chapter we describe the industrial environment, formulate a job shop scheduling problem, discuss the limitations of this formulation and relate it to existing literature. We then describe the decomposition approach we suggest and motivate its use in this environment.

In the previous chapter we presented a complex industrial scheduling environment and formulated it as a job shop scheduling problem. We then introduced decomposition procedures for these problems, discussed their various practical and computational advantages and the issues involved in the development of effective decomposition methods. In this chapter we provide a review of decomposition approaches for scheduling problems that have been considered in the literature, and discuss how they have addressed the issues raised in the previous chapter.

As discussed in the previous chapter, there are several dimensions along which we can decompose a factory scheduling problem. These involve creating a set of subproblems from the basic set of atomic scheduling objects (operations and machines). However, decomposition procedures based on solving the subproblems one by one without considering the constraints they place on solutions for those remaining unsolved are unlikely to give good results. Indeed, it is easy to construct examples of such procedures which yield infeasible or very poor solutions. This is due to the fact that as each subproblem is solved, it imposes additional constraints on the possible solutions to those remaining unsolved. Jobs become available for the unsolved subproblems at certain times, and will take a certain amount of time to complete after processing on the resources contained in the subproblem considered. Hence a critical component of successful decomposition methods is a mechanism to model the interactions between subproblems. Ideally, this mechanism allows the constraints imposed on the unsolved subproblems by the solved ones to be propagated as the procedure progresses, ensuring feasible, high-quality solutions. This requires a representation of the problem that is rich enough to model the variety of workcenters arising in the factory environment being considered, and which will permit computationally efficient constraint propagation.

In the preceding chapters we have presented a view of the factory scheduling problem, using the semiconductor manufacturing environment as an example of an industrial scheduling problem which is considerably more complex than the classical job shop problems studied extensively in the literature. Based on the characteristics of these industrial problems, we make a case for the use of decomposition methods and provide a taxonomy of decomposition approaches to such problems.

The previous chapters have outlined the industrial scheduling problems for which we wish to develop scheduling algorithms, the advantages of decomposition algorithms for these problems and a review of decomposition methods that have been developed for various scheduling problems in the past. In particular, Chapter 5 discussed workcenter-based decomposition algorithms for the job shop environment without sequence-dependent setup times. These approaches are generic in that they do not exploit special structure in the routings or other aspects of the problem.

The main goal of this research, as discussed in Chapter 2, is to develop effective decomposition procedures to minimize Lmax in complex job shops of the type encountered in semiconductor testing and wafer fabrication facilities. In the workcenter-based approach we have followed, a key subproblem is that of minimizing Lmax on a workcenter consisting of a single machine, or parallel identical machines, in the presence of sequence-dependent setup times. These problems are strongly NP-hard, and are thus of considerable interest in their own right, apart from their importance in developing effective decomposition procedures for the overall job shop problem. Experiments with generic decomposition procedures in Chapters 5 and 6 have shown that the quality of the subproblem solutions has a significant effect on the quality of the solution obtained for the overall problem. Hence it is desirable to develop heuristics that generate higher-quality solutions in reasonable computation times.

In this chapter, we extend the linear temporal decomposition approach developed in the previous chapter for workcenters consisting of a single machine with sequence-dependent setup times to workcenters with parallel identical machines (Ovacik and Uzsoy 1995). As was the case for the single-machine problems discussed in the previous chapter, these arise as subproblems in the workcenter-based decomposition procedure. Once again the operations arrive at the workcenter dynamically over time due to scheduling decisions made at other workcenters. These operation release times and due dates can be calculated using the graph representation of partial schedules at intermediate iterations of the shop decomposition procedure. We again assume that all operations are independent (an assumption we shall relax in Chapter 10), and refer to the individual operations to be scheduled as jobs for the sake of conciseness, keeping in mind that in the context of the job shop problem they are operations of jobs involving a number of such operations at different workcenters.

The decomposition procedures described in Chapters 5 and 6 are workcenter-or machine-based decomposition procedures according to the taxonomy of decomposition methods in Chapter 3. They decompose the job shop into subproblems involving operations on the same workcenter. In Chapter 10, we discuss an operation-based decomposition procedure for scheduling individual workcenters, where the set of operations processed on the workcenter are divided into sets of critical and non-critical operations. Both workcenter-based and operation-based decomposition procedures are entity-based decomposition methods in that the overall problem is decomposed into subproblems that consist of physical entities such as machines and jobs.

In Chapters 5 and 6, we presented generic workcenter-based decomposition procedures. Implementing these procedures in job shops and flow shops, as well as semiconductor testing facilities showed that they perform significantly better than dispatching rules. These experiments not only showed that this is a valid approach to problems of this kind, but also highlighted the critical elements of the procedure we need to improve on to make the procedure work even better. In this chapter, we combine the subproblem solution procedures developed in Chapters 7 and 8 with insights obtained from the experiments with the generic decomposition procedures in Chapters 5 and 6 to develop improved workcenter-based decomposition procedures for the semiconductor testing environment.

In this chapter, we present computational experiments to evaluate the performance of the decomposition procedures developed in the previous chapter. The procedures are used to solve a large number of randomly generated problems based on data obtained from a major semiconductor company. These results indicate that the tailored decomposition procedures DEC and DECwR significantly outperform both myopic and extended dispatching rules both on average and in the worst case.

In the previous chapter we have examined the performance of several tailored decomposition procedures for semiconductor testing problems. These results indicate that the integration of tailored control structures with effective, optimization-based procedures for solving the subproblems can yield substantial improvements in solution quality over myopic dispatching rules or generic decomposition procedures in computation times that are reasonable for the environments being considered.

Throughout the body of this book we have covered a number of different aspects of decomposition methods for complex factory scheduling problems. In this chapter we shall review the main developments of this work, and suggest a number of directions for future research. We shall also discuss briefly what type of software and information systems issues need to be resolved for decomposition methods such as those presented in this book to be practical and cost-effective.