Two-machine group scheduling problems in discrete parts manufacturing with sequence-dependent setups

This paper focuses on minimizing the total completion time in two-machine group scheduling problems with sequence-dependent setups that are typically found in discrete parts manufacturing. As the problem is characterized as strongly NP-hard, three search algorithms based on tabu search are developed for solving industry-size scheduling problems. Four different lower bounding mechanisms are developed to identify a lower bound for all problems attempted, and the largest of the four is aptly used in the evaluation of the percentage deviation of the search algorithms to assess their efficacy. The problem sizes are classified as small, medium and large, and to accommodate the variability that might exist in the sequence-dependent setup times on both machines, three different scenarios are considered. Such finer levels of classification have resulted in the generation of nine different categories of problem instances, thus facilitating the performance of a very detailed statistical experimental design to assess the efficacy and efficiency of the three search algorithms. The search algorithm based on long-term memory with maximal frequencies either recorded a statistically better makespan or one that is indifferent when compared with the other two with all three scenarios and problem sizes. Hence, it is recommended for solving the research problem. Under the three scenarios, the average percentage deviation for all sizes of problem instances solved has been remarkably low. In particular, a mathematical programming based lower bounding mechanism, which focuses on converting (reducing) the original sequence-dependent group scheduling problem with several jobs in each group to a sequence-dependent job scheduling problem, has served well in identifying a high quality lower bound for the original problem, making it possible to evaluate a lower average percentage deviation for the search algorithm. Also, a 16-17-fold reduction in average computation time for solving a large problem instance with the recommended search algorithm compared with identifying just the lower bound of (not solving) the same instance by the mathematical programming based mechanism speaks strongly in favor of the search algorithm for solving industry-size group scheduling problems. With an ever increasing demand for setting up manufacturing cells in the production of discrete parts to realize the benefits advocated in lean manufacturing systems, group scheduling has become a topic of research with significant industrial relevance. The problem addressed in this paper is motivated by the need for having to investigate such a problem in the presence of sequence-dependent setups in a two-machine environment to minimize the makespan, which to the best of the authors' knowledge is the first of its kind. Recognizing the complexity of the problem, three search algorithms based on tabu search have been developed to efficiently solve problem instances that belong to nine different categories, as a result of considering three different sizes, ranging from small, medium to large, and three different scenarios. In order to assess the efficacy of the search algorithms, four different lower bounding mechanisms have been developed and the largest of the four is aptly used to evaluate the percentage deviation in every problem instance attempted. The average percentage deviation of the solutions found by the search algorithms has been remarkably low. We view our contribution as that which looks into such detailed levels of investigation, emphasizing a blend of new theory and practice in the area of group scheduling. (c) 2004 Elsevier Ltd. All rights reserved.