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

https://doi.org/10.1016/j.cor.2004.07.004Get rights and content

Abstract

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.

Scope and purpose

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.

Introduction

Group scheduling emerges as a problem following the formation of disaggregated manufacturing cells, typically intended to produce a set of discrete parts. Formation of disaggregated manufacturing cells guarantees that similar parts belonging to a group (part family) are completely processed on dissimilar machines assigned to the same cell as that of the parts. The objective of group scheduling is to identify a sequence of groups as well as a sequence of parts in each group that minimizes some measure of effectiveness. These measures of effectiveness include total completion time, total weighted flow time, and total weighted tardiness, amongst others. Unlike in conventional scheduling, the issues in group scheduling would have to be resolved at two levels. At the first level, a sequence for parts in a group that minimizes some measure of effectiveness must be determined, while at the second, a sequence for groups themselves that minimizes the same measure of effectiveness must be determined. As parts that belong to the same group are similar, changing from one part to another in the same group requires negligible setup time or it can be included along with the run time. However, a change from one group to another would require spending a significant amount of time that it cannot be disregarded. It means that the setup time for a group on a machine should be separated from the parts’ run time to perform a meaningful analysis.

Liaee and Emmons [1] review the existing literature on scheduling families of jobs with setup times on single or parallel machines. They consider scheduling with and without the group technology assumption (GTA) under a variety of performance measures. In the former, the jobs in the same group must be scheduled contiguously, while in the latter the jobs in the same group need not be scheduled contiguously. The motivation for scheduling with GTA is that jobs in a group are not split into sublots. Thus, the number of sublots in each job is one, and it is logical to schedule the jobs in the same family together. Scheduling without the GTA is based on the premise that jobs in a group are split into sublots, and therefore two interrelated decisions concerning the number and size of each sublot would have to be made [2]. A setup is incurred on a machine when there is a changeover from processing a sublot of one group to a sublot of another group. Appropriately, scheduling with GTA uses group setup times and that without GTA uses batch setup times, and is investigated either as a sequence-independent or sequence-dependent setup time problem. Solving batch-scheduling problems has been recognized to be difficult compared to the group scheduling problems by Monma and Potts [3], [4], and the reviews of existing literature are given in Potts and Van Wassenhove [5] and Potts and Kovalyov [6]. Recently, reviews of scheduling research involving setup time considerations have appeared in [7] and [2].

The work reported in this paper focuses on sequence-dependent group scheduling problems. As such, we focus on flow shop job scheduling and flow shop group scheduling to better position our contribution. As the jobs within a group are similar, they follow a flow line arrangement. Thus, algorithms that take advantage of some of the insights gained in solving regular flow shop scheduling problems have been developed for solving group-scheduling problems [8], [9], [10], [11], [12]. Nakamura et al. [13] and Ozden et al. [14] have investigated the single-machine group-scheduling problem within the context of minimizing the total tardiness. Baker [15] reported a dynamic programming algorithm for identifying an optimal sequence of parts that minimizes the mean completion time. Webster and Baker [16] review the research findings in group scheduling with regard to minimizing the total weighted flow time and the maximum lateness, although their review extends the results to cover the areas of group scheduling with batch availability and batch processing. Within the context of job scheduling, Sule [17] and Proust et al. [18] have considered the two-machine flow shop scheduling problems with setup and removal times separated. Gupta and Darrow [19], [20] have investigated a two machine sequence-dependent job-scheduling problem. They recognize that even the two-machine makespan minimization job (not group)-scheduling problem is NP-hard, and propose approximate algorithms to solve the problem. Ham et al. [21] were the first to present an optimizing algorithm for minimizing the total completion time in a two-machine sequence-independent group-scheduling problem. Following this, Logendran and Sriskandarajah [22] showed that a two-machine group-scheduling problem with no buffer and anticipatory setups is strongly NP-hard. It is a characteristic in which the setup on the second machine can be performed in anticipation of the arriving group of parts. Logendran et al. [23] developed an efficient heuristic solution algorithm for minimizing the total completion time in an m-machine (m>2) group-scheduling problem where the setup times are assumed to be sequence independent. Thus, it draws a marked contrast with that of [17], [18] which are limited to two machines and job scheduling, and [19], [20] which are also limited to two machines and job scheduling but with sequence-dependent setups. This paper specifically focuses on minimizing the total completion time (makespan) in a two-machine group-scheduling problemwhen setup times are sequence-dependent. The two machine flow shop (job) scheduling arrangements are still widely used in industry practice. The two machine group scheduling problems that abide by the group technology assumptions (GTA) and further impacted by sequence-dependent setup times to account for transferring from one group to another indeed have applicability in industry practice.

Section snippets

Problem characteristics

The following notations are introduced to characterize the problem.

M1,M2first and the second machine
nnumber of groups of jobs
Gj;j=1,,ngroup j comprised of jobs
qjnumber of jobs in group Gj, j=1,,n
aij,bijrun time for job i in group j on machines M1 and M2, respectively; aij>0, bij>0; i=1,,qj
spjksetup time for group j on Mk, (k=1,2), if group j is processed immediately after group p

We make the following assumptions: 1. The analysis is limited to static flowshop wherein the number of units of

Lower bounding mechanisms

Most practical scheduling problems would involve several groups and several jobs in each group and they have to be solved efficiently by the proposed solution algorithm. Although these solutions would be effective, knowing a lower bound for the original problem would enable assessing how good they are. We propose four different mechanisms for identifying this lower bound. Clearly, the largest of the four would be deemed as the most effective lower bound for assessing the quality of the solution

Search algorithm

We develop a higher-level search algorithm, based on tabu search, for solving large industry size problems efficiently. Tabu search [27] has been proven to be a remarkably efficient approach for solving hard combinatorial problems in scheduling, including that of FMS scheduling problems [28] and unrelated-parallel machine scheduling problem with job-splitting [29].

The algorithm for group scheduling problems typically consists of two levels of search. The first level, called the outside search,

Sample problem

We consider the following example with four groups and each group having four jobs and run times as shown in Table 2, Table 3, Table 4, Table 5. The setup times on machines M1 and M2 for changing from one group to another, including the reference group, are shown in Table 6, Table 7.

The search algorithm with short-term memory (SA1) is selected to demonstrate the application of the algorithm on this example.

Step 1: An initial feasible solution is required to initiate the search. In this

Experimental design and results

We design an experiment that is intended to extensively test of the computational efficacy and efficiency of the proposed search algorithms. Our aim is to solve problems classified into three different sizes—small, medium, and large. For a given group sequence for the original problem, as the optimal job sequence in each group can be determined by applying Johnson's ordering, the number of groups should serve as the deciding factor in developing the problem size classifications. Accordingly,

Conclusions

We have addressed the two-machine, sequence-dependent group-scheduling problem that is typically found in hardware manufacturing. The minimization of makespan is used as the measure of performance. The introduction of short- and long-term memory has led to developing three different search algorithms based on tabu search for solving industry-size scheduling problems. The problem instances are classified into three different sizes, namely small, medium, and large. In addition, three different

Acknowledgements

Research by the first and the second authors is funded in part by the National Science Foundation (USA) Grant No. DMI-0010118, and that by the third author is funded in part by the National Science Foundation (USA) Grant No. DMI-0100327. Their support is gratefully acknowledged.

References (33)

  • C.N. Potts et al.

    Integrating scheduling with batching and lot-sizinga review of algorithms and complexity

    Journal of the Operational Research Society

    (1992)
  • Allahverdi A, Gupta JND, Aldowaisan T. A review of scheduling research involving setup considerations. Omega 1999;...
  • Cho KK, Enscore Jr EE, Ham I. A heuristic algorithm for multistage group scheduling problem to minimize total...
  • Radharamanan R. A heuristic algorithm for group scheduling. Proceedings of the International Industrial Engineering...
  • Al-Qattan I. Designing GT cells enhanced by group scheduling: key to flexible manufacturing system. Proceedings of the...
  • Allison JD. Combining Petrov's heuristic and the CDS heuristic in group scheduling problems. Proceedings of the 12th...
  • Cited by (65)

    • A comprehensive review of flowshop group scheduling literature

      2016, Computers and Operations Research
      Citation Excerpt :

      This encoding scheme is also used for solving m-machine flowshop group scheduling problems by Liou and Hsieh [59]. Another alternative modeling for the two-machine permutation problem is presented by Logendran et al. [60]. On the basis of the structure of a single family schedule, the sequencing of families is solved as a traveling salesman problem.

    View all citing articles on Scopus
    View full text