Scheduling Theory

Motivation

A flexible manufacturing system is a set of machines through which parts of several types travel along fixed routes; each machine serves several buffers and must pay a set-up time whenever it switches from one buffer to another. Real-time scheduling decides, as the system evolves, which buffer each machine works on. Perkins and Kumar (IEEE Trans. Automat. Control 34, 1989) introduced simple distributed policies for this problem, of which the most natural is the clearing policy: a machine keeps working on a buffer until it is empty, and only then switches. They proved that every clear-a-fraction policy, a subclass of clearing policies, keeps every buffer bounded on acyclic systems whenever each machine has spare capacity, and left open whether clear-a-fraction policies stabilize all systems in which material flows around cycles.

Kumar and Seidman (IEEE Trans. Automat. Control 35(3), 1990, doi:10.1109/9.50339) answered no. Their Example 1 is a single part type that visits two machines in the order 1, 2, 2, 1. Every machine has spare capacity, yet under the clearing policy the buffer levels grow without bound, and they do so even when all set-up times are zero, so the instability comes from machines starving each other rather than from time lost to set-ups. Until then, instability had been suspected to require positive set-up times. Shortly afterwards Lu and Kumar exhibited instability of a static buffer-priority rule in a re-entrant network (IEEE Trans. Automat. Control 36, 1991); together these examples started the study of stability of multiclass queueing networks.

Setting

A manufacturing system has part types $p$ arriving at rates $d_p > 0$. Parts of type $p$ follow a route of length $n_p$: their $i$-th operation is at machine $\mu_{p,i}$, and they wait for it in buffer $b_{p,i}$, where each part needs processing time $\tau_{p,i} > 0$. Machine $m$ serves the buffers $B_m = \{b : \mu_b = m\}$, and switching from $b$ to $b'$ costs set-up time $\delta_{b,b'} \ge 0$.

Flows are continuous (fluid). The level of buffer $b$ at time $t \ge 0$ is $x_b(t) = x_b(0) + u_b(t) - y_b(t) \ge 0$, where $y_b(t)$ is its cumulative output and $u_b(t)$ its cumulative input: $d_p t$ for the first buffer of a route, and the output of the preceding buffer otherwise. Each machine works in runs: run $k$ is a set-up phase of length $\delta_{\beta_{k-1},\beta_k}$ followed by a processing phase on buffer $\beta_k$, during which the buffer is drained at rate $1/\tau_b$ while it is nonempty and passed through at its inflow rate when it is empty. The system is stable if $\sup_{0 \le t < \infty} x_b(t) < \infty$ for every buffer.

A clearing policy (Definition 1) is one in which a machine processing $b$ continues until the first time that $b$ is empty and some other buffer of the same machine is nonempty, and then commences a set-up for one of the nonempty buffers.

Example 1. One part type arrives at rate $d = 1$ and visits machine 1, machine 2, machine 2 and machine 1; its buffers are $1, 2, 3, 4$, so $B_1 = \{1, 4\}$ and $B_2 = \{2, 3\}$. Processing times are $\tau_1, \dots, \tau_4 > 0$, and $\delta_k$ is the time to set up to buffer $k$. The parameters satisfy the critical condition and the capacity condition

$$\tau_2 + \tau_4 > 1, \qquad \tau_1 + \tau_4 < 1, \qquad \tau_2 + \tau_3 < 1. \tag{3–5}$$

The initial state is $x(0) = (\xi, 0, 0, 0)$, with machine 1 set up for buffer 4 and machine 2 set up for buffer 3. Write

$$\lambda = \frac{\tau_4}{1-\tau_2} > 1, \quad \alpha = \frac{(\tau_4+1)(\delta_1+\delta_2)}{1-\tau_2} + \delta_3(\tau_4+1) + \delta_4, \quad \beta = \frac{\tau_4(\delta_1+\delta_2)}{1-\tau_2} + \tau_4\delta_3 + \delta_4.$$

Formalization targets

Goal: Example 1, both cases

Assume (3)–(5).

1. If $\delta_1, \dots, \delta_4 > 0$, there is $\xi_0$ such that for every $\xi \ge \xi_0$ ($\xi > 0$) a clearing trajectory from $(\xi, 0, 0, 0)$ exists, and every such trajectory has

$$\sup_{0 \le t < \infty} x_1(t) = +\infty.$$

2. If $\delta_1 = \dots = \delta_4 = 0$, the same holds for every $\xi > 0$.

Milestone: the Case 1 cycle map

For $\xi$ large enough, every clearing trajectory from $(\xi, 0, 0, 0)$ reaches, at $T_1 = (\lambda + \tau_2/(1-\tau_2))\xi + \alpha$,

$$x(T_1) = (\lambda\xi + \beta, 0, 0, 0),$$

with machines 1 and 2 again set up for buffers 4 and 3.

Milestone: the Case 2 magnification

With zero set-up times and any $\xi > 0$, every clearing trajectory reaches, at $t_5 = (\tau_2+\tau_4)\xi/(1-\tau_2)$,

$$x(t_5) = (\lambda\xi, 0, 0, 0),$$

with machines 1 and 2 again set up for buffers 4 and 3.

Significance

The example shows that the condition $\rho_m < 1$ on every machine, which is necessary for stability and sufficient for the existence of some stabilizing policy, does not make natural distributed policies stable once material flows around a cycle. The throughput of the line falls to $1/(\tau_2+\tau_4) < 1$ part per unit time although each machine could handle the demand. This motivates the paper's two positive results: sufficient conditions under which clear-a-fraction policies are stable (Theorem 1), and a supervisory mechanism that stabilizes any policy (Theorem 2), which are the subjects of the other missions of this series. The example is also an early instance of the phenomenon later studied as instability of multiclass fluid networks under work-conserving policies.

The paper's argument is a stage-by-stage computation of piecewise linear trajectories. No machine-checked version of it exists. A formal proof has to make precise what the paper leaves to the reader: that the clearing rule determines the trajectory, that the stage formulas are what that trajectory does, and that the cycle can be restarted. The formal model of runs, set-ups and the clearing rule built here is the same as in the other missions of the series.

Difficulty

The arithmetic of each cycle is routine once the trajectory is known. The difficulty is in the universal quantifier: the claim covers every clearing trajectory, and the clearing rule is defined implicitly, through "the first time thereafter" at which a buffer is empty and another one is nonempty. At several switching instants the buffer a machine switches to is empty and only starts to fill at that instant, and with zero set-up times a machine may begin a run at an instant where the switching condition already holds. Showing that each switch happens exactly when the paper says, and that the fluid levels then follow the printed formulas (including the reduced rate of a machine working on an empty buffer), is a uniqueness argument for a hybrid system, not a simulation. The existence half asks for the converse: an explicit trajectory, defined for all time, with infinitely many runs whose start times tend to infinity.

Formalization scope

• Time is real ($t \ge 0$); flows are fluid; there are no transport delays or assembly.
• The system is a general structure (part types Fin P, machines Fin M, buffers ⟨p, i⟩ with i : Fin (n p), paper index $i$ = Lean index $i+1$), instantiated as Example 1 with $d = 1$, route $(1,2,2,1)$, and $\delta_{b,b'} = \delta_{b'}$ for $b \ne b'$; staying on a buffer costs nothing.
• A trajectory is a schedule of runs per machine (possibly finitely many, the last lasting forever), with only finitely many run starts in any bounded interval. Processing obeys a rate cap ($y_b$ grows at most at rate $1/\tau_b$, and only while machine $\mu_b$ is in a processing phase of $b$) and runs at full rate while the buffer is nonempty.
• In Definition 1, a target buffer counts as "nonempty" when it is demanding: positive level, or inflow starting at that instant. The no-early-exit condition is imposed on the open processing interval. Under the literal reading (positive level) or a closed interval, the paper's own trajectories are not clearing, and the goal would hold vacuously; the existence clause in the goal rules out that trivialization.
• "Set up for buffer $b$ at time $T$" means the run in force on $(s_k, s_{k+1}]$.
• Unboundedness is stated for buffer 1: for every $C$ there is $t \ge 0$ with $x_1(t) > C$; "$\xi$ large enough" is $\exists \xi_0, \forall \xi \ge \xi_0$.

Useful contributions include lemmas about fluid trajectories that do not depend on the example (continuity of levels, the pass-through rate on an empty buffer, restarting a trajectory at a run boundary), which also serve the other missions of the series.

Selected references

• P. R. Kumar and T. I. Seidman, Dynamic instabilities and stabilization methods in distributed real-time scheduling of manufacturing systems, IEEE Trans. Automat. Control 35(3), 289–298, 1990. https://doi.org/10.1109/9.50339
• J. R. Perkins and P. R. Kumar, Stable, distributed, real-time scheduling of flexible manufacturing/assembly/disassembly systems, IEEE Trans. Automat. Control 34, 139–148, 1989 (reference [18] of the paper).
• S. H. Lu and P. R. Kumar, Distributed scheduling based on due dates and buffer priorities, IEEE Trans. Automat. Control 36, 1991.

Motivation

In a flow shop every job passes through the same machines in the same order. Choosing the order in which jobs enter the shop so that the last job finishes as early as possible (minimizing the makespan) is one of the oldest problems of scheduling theory. For two machines Johnson (1954) gave an exact sorting rule; for three machines his rule is exact only in special cases, and the general problem was later shown to be NP-hard (Garey, Johnson and Sethi, 1976). Exact methods for three or more machines therefore enumerate sequences, and the question is how to enumerate as few of them as possible.

Ignall and Schrage (1965), at the same time as Lomnicki (Operational Research Quarterly, 1965), introduced branch and bound for the three-machine permutation flow shop. Their lower bound, which adds to the time each machine becomes free the work that remains on it and the least work that must follow on later machines, became the template for the machine-based bounds used in flow-shop branch and bound ever since.

Timeline. 1954: Johnson proves the two-machine rule and shows that for three machines a common job order on all machines loses nothing for the makespan. 1960: Land and Doig introduce branch and bound for integer programs. 1965: Ignall–Schrage and Lomnicki apply it to the three-machine flow shop. 1976: Garey, Johnson and Sethi prove the three-machine makespan problem NP-hard, so exact enumeration with good bounds remains the method for exact solutions.

Setting

There are $n\ge1$ jobs and three machines $A$, $B$, $C$. Job $i$ needs time $a_i$ on $A$, then $b_i$ on $B$, then $c_i$ on $C$. Following Johnson, only permutation schedules are considered: a full sequence is a permutation $\sigma$ of the jobs, processed in that order on all three machines, each operation starting as early as possible. Its makespan is the time machine $C$ finishes the last job.

A node $J_r$ is a partial sequence: an ordered list of $r$ distinct jobs. Its unscheduled set $\bar J_r$ is the set of the other $n-r$ jobs. The attributes $\mathrm{TIMEA}(J_r)$, $\mathrm{TIMEB}(J_r)$, $\mathrm{TIMEC}(J_r)$ are the times at which machines $A$, $B$, $C$ finish the jobs of $J_r$ processed in order. A full sequence begins with $J_r$ when its first $r$ positions are $J_r$. The lower bound of a node with $\bar J_r\neq\emptyset$ is

$$LB(J_r)=\max\Big[\mathrm{TIMEA}(J_r)+\sum_{\bar J_r}a_i+\min_{\bar J_r}(b_i+c_i),\ \mathrm{TIMEB}(J_r)+\sum_{\bar J_r}b_i+\min_{\bar J_r}c_i,\ \mathrm{TIMEC}(J_r)+\sum_{\bar J_r}c_i\Big].$$

The branch-and-bound procedure keeps a list of nodes ranked by $LB$, starting from the root (no job scheduled). At each step it removes the first node, creates one child per unscheduled job by appending that job, and inserts the children ranked into the list, a new node going before old nodes of equal bound. It stops when the first node of the list is terminal, i.e. has scheduled $n-1$ jobs, so that its last job is forced.

Formalization targets

Goal: the stopping rule certifies an optimal sequence

$$\exists k:\ \text{the first node of } \mathrm{run}(k) \text{ is terminal},\qquad\text{and}\qquad \text{first node } P \text{ terminal} \ \Longrightarrow\ \mathrm{makespan}(\sigma_P)\le\mathrm{makespan}(\sigma)\ \ \forall\sigma ,$$

where $\sigma_P$ is $P$ followed by its one unscheduled job. This is the paper's "the problem is solved: that node's sequence is an optimal one" (p. 402), for any real processing times.

Milestones

1. Validity of the bound (p. 401): $LB(J_r)\le\mathrm{makespan}(\sigma)$ for every $\sigma$ beginning with $J_r$, $r<n$.
2. Exactness at depth $n-1$ (general form of an observation on p. 403): for $r=n-1$, $LB(J_{n-1})$ equals the makespan of the completed sequence.
3. Node counts (p. 403): at least $\tfrac12n(n+1)$ nodes are created before stopping, at most $1+n+n(n-1)+\cdots+n!$ are ever created, and the list never holds more than $n!$ nodes.
4. Dominance (pp. 403–404): if $J_r$ and $I_r$ contain the same jobs, $\mathrm{TIMEA}(J_r)=\mathrm{TIMEA}(I_r)$; if also $\mathrm{TIMEB}(J_r)\le\mathrm{TIMEB}(I_r)$ and $\mathrm{TIMEC}(J_r)\le\mathrm{TIMEC}(I_r)$, replacing $I_r$ by $J_r$ at the beginning of any sequence does not increase its makespan, and $LB(J_r)\le LB(I_r)$ (p. 404).
5. The 4-job example (pp. 402–403): the run stops after 6 steps with node 231 first, whose bound 62 is the optimal makespan.
6. The refined bound (p. 409): the strengthened bound used in the paper's computations is still a lower bound.

Significance

The goal is the correctness theorem of the Ignall–Schrage algorithm: best-first search over partial sequences, with a machine-based bound, returns an optimal permutation. Milestone 1 is the bound's validity, which every later machine-based flow-shop bound generalizes; milestone 4 is the dominance rule that justifies discarding nodes; milestone 3 brackets the effort of the search between the best case $\tfrac12n(n+1)$ and full enumeration.

The paper's arguments are short and informal: validity of the bound is asserted with a one-line reason, and optimality at stopping is argued on the example. None of these results has a machine-checked proof. The formalization makes the procedure itself a precise object (list, insertion rule, stopping rule) and turns the paper's claims into statements about it, so that the correctness of the search is proved rather than illustrated.

Difficulty

Each inequality is elementary, but the goal is a statement about an iterated list-manipulating procedure. The obvious argument "the first node has the smallest bound and the bound is valid" needs an invariant that the paper does not state: at every step, every full sequence begins with some node on the list, and the list is sorted. Both must be proved to survive one step of removal and ranked insertion. Termination is likewise not stated: it needs a measure that strictly decreases, for instance the set of nodes that remain to be created, which requires showing that no node is created twice. A tempting shortcut, proving optimality only among the sequences whose nodes were created, is not the theorem.

Formalization scope

Jobs are Fin n (the paper's job $i$ is $i-1$), processing times are arbitrary reals with no sign condition, and full sequences are Equiv.Perm (Fin n). The makespan is the machine-$C$ completion time of Johnson's as-soon-as-possible schedule, taken from the published definition JohnsonFlowShop.ThreeStage.asapSchedule. Nodes are lists of jobs, and the node attributes are the same recursion folded over the list. Minima over $\bar J_r$ are Finset.inf'; on an empty set the auxiliary minimum returns a placeholder $0$ that no statement evaluates.

Explicit readings of the paper's phrases:

• "is a lower bound … for any node that emanates from node $P$" is "$\le$ the makespan of every permutation whose first $r$ positions are $J_r$";
• "a node that has scheduled all $n$ jobs" is read as a node with $n-1$ jobs, whose sequence is completed by the forced last job. The example (stop at node 231 of a 4-job problem), the node counts and the formula for $LB$ all require this reading;
• "the problem is solved: that node's sequence is an optimal one" is termination together with optimality over all $n!$ permutations;
• "cannot be hurt by replacing $I_r$ with $J_r$" compares the completions of $J_r$ and $I_r$ by the same ordering of the remaining jobs;
• children are inserted one at a time in increasing job index, each before every node with an equal bound; this reproduces the paper's LIST table;
• dominance discarding is not part of the procedure in the goal.

A formalization in which the optimality claim ranges only over sequences the run created, or one that asserts optimality without termination, would be trivial or vacuous and is ruled out by the goal's statement.

Not formalized: the reduction from general schedules to permutation schedules (Johnson's Lemma 3, proved on the platform as JohnsonFlowShop.ThreeStage.same_ordering_dominant), the dominance bookkeeping and its percentages, the two-machine mean-completion problem (a separate mission of this series), the computational tables, and the TIMEB/TIMEC columns of the example's LIST table. No platform item treats flow-shop lower bounds or branch and bound over sequences; the nearest branch-and-bound mission, BiconvexProg.BranchBound (Al-Khayyal and Falk), concerns biconvex programs and is unrelated.

The lemmas a solver will want (the invariant of the list, monotonicity of the completion recursion in its start times, validity of the bound) are reusable for the two-machine mission and for any other machine-based bound. Proofs of the milestones, and of the goal from them, are welcome in any order.

Selected references

• E. Ignall and L. Schrage, Application of the branch and bound technique to some flow-shop scheduling problems, Operations Research 13(3), 400–412, 1965. https://doi.org/10.1287/opre.13.3.400
• S. M. Johnson, Optimal two- and three-stage production schedules with setup times included, Naval Research Logistics Quarterly 1(1), 61–68, 1954. https://doi.org/10.1002/nav.3800010110
• A. H. Land and A. G. Doig, An automatic method of solving discrete programming problems, Econometrica 28(3), 497–520, 1960. https://doi.org/10.2307/1910129
• M. R. Garey, D. S. Johnson and R. Sethi, The complexity of flowshop and jobshop scheduling, Mathematics of Operations Research 1(2), 117–129, 1976. https://doi.org/10.1287/moor.1.2.117

Burn-in ovens as batch processing machines

In semiconductor manufacturing, finished chips go through burn-in: they are loaded on boards and held in an oven at high temperature to expose early failures. An oven holds a bounded number of boards, a load cannot be interrupted once started, and a chip may stay in the oven longer than its specified burn-in time but not shorter. Lee, Uzsoy and Martin-Vega (Oper. Res. 40(4), 1992) model the oven as a batch processing machine and give polynomial algorithms for several due-date objectives. The model has since become a standard one in scheduling theory; the survey of Potts and Kovalyov (2000) traces the batching literature that grew from it.

This mission formalizes the part of the paper's §3 on minimizing maximum tardiness when all jobs are available at time $0$ and processing times and due dates are agreeable. That is the problem the paper writes $1/B/T_{\max}$. The paper's own route is a feasibility test by dynamic programming, Algorithm DP2, which a bisection over due-date shifts turns into a $T_{\max}$ minimizer.

The batch machine

There are $n$ jobs $1,\dots,n$. Job $i$ has a processing time $p_i$ and a due date $d_i$, both natural numbers. The machine has capacity $B\ge 1$. A batch is a nonempty set of at most $B$ jobs processed together. It occupies the machine for the processing time of its longest job,

$$t(P)=\max_{i\in P}p_i .$$

A batch schedule of a job set $J$ is a sequence $S=(P_1,\dots,P_m)$ of pairwise disjoint batches covering $J$, processed in this order and back to back from time $0$. Batch $P_k$ and all of its jobs complete at $C(P_k)=t(P_1)+\dots+t(P_k)$. The makespan is $C_{\max}(S)=C(P_m)$, and the maximum tardiness is

$$T_{\max}(S)=\max_k\max_{i\in P_k}\max\{0,\,C(P_k)-d_i\}.$$

A schedule is feasible when $T_{\max}(S)=0$, that is, when every job meets its due date.

A sequence is in batch-EDD order (Definition 1) if no job in an earlier batch has a strictly later due date than a job in a later batch. Processing times and due dates are agreeable if $p_i<p_j$ implies $d_i\le d_j$. A schedule is consecutive when every batch is a block $\{i,i+1,\dots,k\}$ of indices and the blocks appear in increasing order.

Algorithm DP2 computes values $f(0),\dots,f(n)\in\mathbb N\cup\{\infty\}$:

$$f(0)=0,\qquad f(j)=\min_{\max\{1,\,j-B+1\}\le i\le j} f_i(j),\qquad f_i(j)=\begin{cases}f(i-1)+p_j,& f(i-1)+p_j\le d_i,\\ \infty,&\text{otherwise.}\end{cases}$$

Formalization targets

Goal: correctness of DP2

Index the jobs so that $d_1\le\dots\le d_n$ and $p_1\le\dots\le p_n$. Then for every $0\le j\le n$,

$$f(j)=\min\{\,C_{\max}(S) : S \text{ a batch schedule of jobs } 1,\dots,j,\ T_{\max}(S)=0\,\},$$

with $\min\emptyset=\infty$. The minimum ranges over all schedules: any batching, any order. This is the paper's reading of $f(j)$ as "the minimum completion time of jobs $1,\dots,j$ if they can be scheduled feasibly, and infinity otherwise".

Milestones

1. Lemma 3. With agreeable processing times and due dates, if a feasible schedule exists, then a feasible schedule in batch-EDD order exists.
2. Consecutive partition (justification of DP2). Under the index order above, if jobs $1,\dots,j$ can be scheduled feasibly, then some feasible schedule of minimum makespan is consecutive.
3. FBEDD. With equal processing times and due dates in index order, the Full-Batch EDD schedule $\{1,\dots,B\},\{B+1,\dots,2B\},\dots$ has $T_{\max}$ no larger than that of any batch schedule.

Significance

DP2 is the paper's feasibility test for $1/B/T_{\max}$ with agreeable data. With a bisection over the common shift of the due dates, it yields a polynomial algorithm for minimizing $T_{\max}$. A correct statement of what DP2 computes is therefore the core of that result. The same consecutive-partition structure underlies the paper's DP1 (release times, equal processing times) and DP3 (number of tardy jobs), which are separate missions of this series.

No machine-checked proof of any of these statements is known. The dynamic program's correctness is argued in the paper only by reference ("the justification of this algorithm is similar to that of algorithm DP1"), and the index order it needs is left implicit. A formal proof pins down exactly which ordering of the jobs makes the recursion correct.

Difficulty

The recursion charges $p_j$ for the last batch $\{i,\dots,j\}$ and checks only $d_i$. Both shortcuts rely on the jobs being sorted by due date and by processing time at the same time. Lemma 3's exchange argument sorts a feasible schedule by due date, but it does not by itself produce consecutive blocks of a fixed index order. With ties in due dates the indexing also has to be compatible with processing times. Without that, the recursion is wrong: for $B=2$, $p=(3,1)$, $d=(5,5)$ it gives $f(2)=1$, while every schedule takes at least $3$. The goal compares the DP with the optimum over all schedules, so the exchange arguments have to bridge arbitrary batchings and the consecutive ones the recursion enumerates. That bridge is the main step left to prove.

Formalization scope

• Jobs are Fin n (job $i$ of the paper is index $i-1$); jobs $1,\dots,j$ are jobsUpTo n j. Data are natural numbers; the paper assumes integral data (p. 769).
• A schedule is a List (Finset (Fin n)); validity requires nonempty batches of size at most $B$ inside the job set, pairwise disjoint, covering the set. Batches start as early as possible. Batch time is the maximum processing time in the batch.
• $\infty$ is ⊤ : ℕ∞, and the goal's minimum is the infimum in ℕ∞, which is ⊤ exactly when no feasible schedule exists. DP2 is defined by the printed recursion, not as an optimum.
• Explicit readings of loose phrases:
  • "jobs are indexed in increasing order of due dates" (p. 767) becomes Monotone d ∧ Monotone p for DP2 and its justification, and Monotone d for FBEDD;
  • "agreeable" (printed "$p_i\le p_j$ implies $d_i\le d_j$", which would force equal due dates for equal processing times) becomes the strict form $p_i<p_j\Rightarrow d_i\le d_j$, a weaker hypothesis;
  • "optimally solves" for FBEDD becomes "valid, and $T_{\max}$ at most that of every valid schedule";
  • "a consecutive partition problem" becomes the existence of a consecutive minimum-makespan feasible schedule.
• Not formalized: the $O(nB)$ and $O[nB\log_2(np_{\max})]$ running times, the bisection procedure, and the remark that $np_{\max}$ bounds $T_{\max}$.
• Trivializations ruled out: the goal's minimum ranges over all valid schedules, not only batch-EDD or consecutive ones (which would assume the milestones), and DP2 is the printed recursion, not a restatement of the optimum.
• Infrastructure needed: list-indexed schedules, exchange arguments on adjacent batches, and induction on prefix length for the recursion. The single-machine batch model is shared in spirit with missions 1 and 3 of this series. No published platform definition was reused, since nothing on batch machines exists yet.

Selected references

• C.-Y. Lee, R. Uzsoy, L. A. Martin-Vega, Efficient Algorithms for Scheduling Semiconductor Burn-In Operations, Operations Research 40(4), 764–775, 1992. https://doi.org/10.1287/opre.40.4.764
• Y. Ikura, M. Gimple, Efficient scheduling algorithms for a single batch processing machine, Operations Research Letters 5(2), 61–65, 1986. https://doi.org/10.1016/0167-6377(86)90104-5
• C. N. Potts, M. Y. Kovalyov, Scheduling with batching: A review, European Journal of Operational Research 120(2), 228–249, 2000. https://doi.org/10.1016/S0377-2217(99)00153-8