The Giffler-Thompson Theorem (Algorithm) in Job Shop Scheduling

The Giffler-Thompson (GT) theorem — more commonly referred to as the Giffler-Thompson algorithm or Giffler-Thompson procedure — is a foundational result in scheduling theory that addresses the job shop scheduling problem. It was originally introduced by B. Giffler and G. L. Thompson in 1960 [1]. The theorem provides two essential contributions: (1) the concept of active schedules, and (2) a systematic algorithm for generating all active schedules for the job shop problem. The core insight is that for any regular measure of performance (e.g., makespan, mean flow time, total completion time), the optimal schedule belongs to the set of active schedules, making this set dominant — i.e., it is sufficient to search only among active schedules to find an optimum [1,2].

Key Concepts

1. Active Schedules

An active schedule is defined as a feasible schedule in which no operation can be started earlier than its current start time without delaying some other operation [1–3]. In other words, an active schedule allows no "global left-shift" — moving any operation earlier in time would necessarily force another operation to be postponed. This concept is distinguished from:

• Semi-active schedules: schedules where no operation can be started earlier without altering the processing sequence on some machine (allowing only "local left-shifts").
• Non-delay schedules: schedules where no machine is kept idle while an operation is available for processing.

The relationships among these categories are well-established: non-delay schedules ⊂ active schedules ⊂ semi-active schedules ⊂ feasible schedules [4,6]. The set of active schedules is the smallest dominant set in all feasible schedules for regular performance measures [7].

2. The Dominance Property (The "Theorem")

The central theoretical result — often called the Giffler-Thompson theorem — states that for any regular measure of performance (i.e., a non-decreasing function of job completion times, such as makespan or total flow time), the optimal schedule must be an active schedule [1,2,6]. This means that the search for an optimal solution can be restricted to the (generally much smaller) set of active schedules without loss of optimality.

As noted in the literature, "the optimum schedule is an active schedule" [2]. This dominance property has been rigorously proven and is a cornerstone of many exact and heuristic scheduling methods [3,4].

3. The Giffler-Thompson Algorithm

The GT algorithm is a constructive procedure that generates all active schedules through a branching process. The algorithm proceeds as follows [1,2,7]:

1. Initialize: Start with an empty partial schedule (PS) and a set S containing all currently schedulable operations (operations whose predecessor operations have already been scheduled).

2. Find the critical operation and machine: Compute the earliest completion time for each operation in S. Let $f^{\ast }$ be the minimum of these earliest completion times, and let $m^{\ast }$ be the machine associated with the operation achieving $f^{\ast }$.

3. Identify the conflict set: The conflict set C consists of all operations in S that require machine $m^{\ast }$ and whose earliest start time is strictly less than $f^{\ast }$. These operations are said to be in "conflict" — scheduling any one of them will block the others.

4. Branch: For each operation in the conflict set C, create a new partial schedule by adding that operation to PS, scheduling it at its earliest start time. Remove it from S and add its immediate successor (if any) to S.

5. Repeat: Return to step 2 for each new partial schedule, continuing until all operations have been scheduled.

This process generates a tree whose leaf nodes correspond to complete active schedules [2]. The number of active schedules can be enormous — for a job shop with $n$ jobs and $m$ machines, the upper bound on the number of active schedules is $O((nm){!}^m)$ [3].

4. Variants and Extensions

Non-Delay Schedule Generation

By modifying the eligibility criterion to only consider operations whose earliest start time equals the minimum earliest completion time, the GT algorithm can be adapted to generate non-delay schedules — a subset of active schedules where no machine is left idle when work is available [6]. However, non-delay schedules are not dominant (the optimal solution may not be a non-delay schedule), though empirical studies show that the optimal non-delay schedule is, on average, only about 1.64% worse than the overall optimum [6].

Flexible Manufacturing Systems (FMS)

The GT algorithm has been extended to FMS scheduling, where each operation can be performed by alternative machines. The modified algorithm (Chang and Sullivan's extension) considers all feasible machines in step 2 rather than a single machine [2]. Computational results show that the original GT algorithm adapted for FMS can produce near-optimal solutions much faster than more complex FMS-specific algorithms [2].

Sequence-Dependent Setup Times

Extending the GT algorithm to problems with sequence-dependent setup times (SDST-JSP) is non-trivial. Simple extensions based on operation appending do not guarantee active schedules because setup times break the transitivity of the conflict relation. Insertion-based SGSs and the serial SGS have been proposed as alternatives that can generate active schedules even in the presence of setup times [4].

Knowledge-Based GT Heuristic

The GT algorithm has been combined with machine learning techniques for dynamic rescheduling. The "kbGT" (knowledge-based Giffler-Thompson) heuristic uses a naïve Bayes classifier to dynamically select the most appropriate dispatching rule for resolving conflicts at each decision point, based on the current system state [5].

Genetic Algorithms

In genetic algorithm approaches to job shop scheduling, the GT method is used as an enforcement operator to transform infeasible or non-active schedules generated by crossover operations into active (feasible) schedules. This ensures that all individuals in the population are active schedules, improving the efficiency of the search [8].

Practical Significance

The Giffler-Thompson algorithm is not merely a theoretical construct — it has had substantial practical impact:

• It provides the branching scheme for many branch-and-bound exact optimization methods for job shop scheduling [6].
• It underlies priority rule-based heuristics: dispatching rules (like SPT, MWKR, etc.) are used to select a single operation from the conflict set at each step, generating one specific active schedule [5,7].
• It is used in Monte Carlo sampling methods where conflicts are resolved randomly, and the best schedule from many random runs is selected [1].
• It serves as the basis for schedule generation schemes (SGS) in more complex environments, including flexible manufacturing systems and shops with sequence-dependent setups [2,4].

Computational Complexity

The job shop scheduling problem is NP-hard for most objective functions [5]. The GT algorithm's state space grows exponentially with problem size, making complete enumeration infeasible for all but the smallest instances. However, the algorithm's strength lies in providing a structured way to navigate the search space, and when coupled with bounding techniques (branch-and-bound) or heuristic selection rules, it forms the backbone of many practical scheduling methods [2,6].

---

References

[1]Thompson, G. L. (1960). Recent developments in the job-shop scheduling problem. Naval Research Logistics Quarterly, 7(4), 585–598
DOI: 10.1002/nav.3800070427[2]Rodrigues, S. B., & de Souza, R. (1993). Giffler and Thompson's Algorithm for Job Shop Scheduling is Still Good for Flexible Manufacturing Systems. Journal of the Operational Research Society, 44(10), 1015–1023
DOI: 10.1057/jors.1993.88[3]Chang, Y.-L., & Sullivan, R. S. (1990). Schedule generation in a dynamic job shop. International Journal of Production Research, 28(1), 65–79
DOI: 10.1080/00207549008942684[4]Artigues, C., & Roubellat, F. (2005). Schedule Generation Schemes for the Job-Shop Problem with Sequence-Dependent Setup Times: Dominance Properties and Computational Analysis. Annals of Operations Research, 138, 21–52
DOI: 10.1007/s10479-005-2443-4[5]Aufenanger, M., Kloepper, B., Dangelmaier, W., & Lipka, N. (2009). A knowledge-based Giffler-Thompson heuristic for rescheduling job-shops. 2009 IEEE Symposium on Computational Intelligence in Scheduling, 33–40
DOI: 10.1109/scis.2009.4927010[6]Raman, N., & Talbot, F. B. (1990). Optimal nondelay job shop schedules. International Journal of Production Research, 28(7), 1265–1282
DOI: 10.1080/00207549008942707[7]Sun, D., Batta, R., & Lin, L. (1995). Effective job shop scheduling through active chain manipulation. Computers & Operations Research, 22(2), 159–172
DOI: 10.1016/0305-0548(94)E0018-3[8]Kobayashi, S., Ono, I., & Yamamura, M. (1996). A genetic algorithm for job-shop scheduling problems using job-based order crossover. Proceedings of IEEE International Conference on Evolutionary Computation, 547–552
DOI: 10.1109/icec.1996.542658