Two-machine group scheduling problems in discrete parts manufacturing with sequence-dependent setups
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 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.first and the second machine n number of groups of jobs group j comprised of jobs number of jobs in group , run time for job i in group j on machines and , respectively; , ; setup time for group j on , , 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 and 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)
- et al.
Scheduling families of jobs with setup times
International Journal of Production Economics
(1997) - et al.
Scheduling with batchinga review
European Journal of Operational Research
(2000) - et al.
Minimizing the makespan of a group scheduling problema new heuristic
International Journal of Production Economics
(1991) - et al.
Job scheduling in a group technology environment for a single facility
Journal of Computers and Industrial Engineering
(1985) - et al.
The two-machine sequence dependent flowshop scheduling problem
European Journal of Operational Research
(1986) - et al.
Two-machine group scheduling problem with blocking and anticipatory setups
European Journal of Operational Research—Special Issue on Cellular Manufacturing Systems
(1993) - et al.
Combined heuristics for bi-level group scheduling problems
International Journal of Production Economics
(1995) - et al.
A review of flowshop scheduling research with setup times
Production and Operations Management
(2000) - et al.
On the complexity of scheduling with batch setups
Operations Research
(1989) - et al.
Analysis of heuristics for preemptive parallel machine scheduling with batch setup times
Operations Research
(1993)
Integrating scheduling with batching and lot-sizinga review of algorithms and complexity
Journal of the Operational Research Society
Cited by (65)
Intelligent optimization under the makespan constraint: Rapid evaluation mechanisms based on the critical machine for the distributed flowshop group scheduling problem
2023, European Journal of Operational ResearchAn effective two-stage iterated greedy algorithm for distributed flowshop group scheduling problem with setup time
2023, Expert Systems with ApplicationsRedefining hybrid flow shop group scheduling: Unveiling a novel hybrid modeling paradigm and assessing 48 MILP and CP models
2023, Swarm and Evolutionary ComputationMakespan optimization in a no-wait flowline manufacturing cell with sequence-dependent family setup times
2019, Computers and Industrial EngineeringA comprehensive review of flowshop group scheduling literature
2016, Computers and Operations ResearchCitation 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.
A hybrid algorithm for the multi-stage flow shop group scheduling with sequence-dependent setup and transportation times
2015, International Journal of Production Economics