pith. sign in

arxiv: 2508.18272 · v2 · submitted 2025-07-02 · 🧮 math.GM

An Improvement-Path Framework and an Exact Algorithm for Single-Machine Scheduling with Release Times

Xiaoyang Duan , Peixin Zhao This is my paper

Pith reviewed 2026-05-19 07:02 UTC · model grok-4.3

classification 🧮 math.GM
keywords single-machine schedulingrelease timestotal waiting timeimprovement pathexact algorithmlocal optimarepair operatorsNP-hard scheduling
0
0 comments X

The pith

An iterative repair algorithm finds globally optimal schedules for single-machine problems with release times by following ideal improvement paths.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

This paper introduces an improvement-path framework for the NP-hard single-machine scheduling problem with release times that minimizes total waiting time. Treating idle time as negative waiting time compresses the problem into a two-dimensional representation based solely on processing times and waiting times. Ideal directions are defined from optimal solution structures, and it is shown that every non-optimal schedule admits an ideal improvement path whose improvable directions act independently without coordination. Queue discontinuity is identified as the only structural obstacle to realizing these paths, allowing characterization of local optima and design of targeted repair operators. An iterative repair algorithm is then constructed and proved to terminate in finitely many steps while returning a globally optimal schedule with an explicit time-complexity bound.

Core claim

By establishing a unified two-dimensional waiting-time formulation, the authors define ideal directions and prove that every non-optimal schedule admits an ideal improvement path. Improvable ideal directions can be handled independently, and queue discontinuity is the unique structural obstacle to their realization. This leads to a characterization of local optima and repair operators, upon which an iterative repair algorithm is built that terminates in finitely many steps, returns a globally optimal schedule, and admits an explicit upper bound on its time complexity.

What carries the argument

the ideal improvement path, a sequence of independent improvable ideal directions realized by repairing queue discontinuities through local flow adjustments

If this is right

  • Local optima are completely characterized by unresolved queue discontinuities.
  • The independence of improvable directions permits sequential or parallel application of repair operators without coordination.
  • The algorithm supplies an exact solution method for this NP-hard problem with a finite termination guarantee.
  • An explicit upper bound on time complexity follows directly from the finite number of improvement steps and the finite checks per direction.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The two-dimensional waiting-time representation may simplify analysis of related objectives such as tardiness or makespan in similar machine environments.
  • The path-repair approach could be tested on benchmark instances to measure practical running times against branch-and-bound or dynamic-programming methods.
  • Similar ideal-direction and discontinuity concepts might extend to multi-machine or preemptive variants of the problem.

Load-bearing premise

Every non-optimal schedule admits an ideal improvement path, and improvable ideal directions require no coordination and can be treated as independent improvement units.

What would settle it

A concrete scheduling instance in which the iterative repair algorithm either fails to terminate in finite steps, returns a schedule that is not globally optimal, or encounters a realizability obstacle other than queue discontinuity.

Figures

Figures reproduced from arXiv: 2508.18272 by Peixin Zhao, Xiaoyang Duan.

Figure 1
Figure 1. Figure 1: This figure shows how queue waiting times are computed and how the queue leader [PITH_FULL_IMAGE:figures/full_fig_p007_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: Illustration of the position adjustment for job 3. If adjusting the processing order [PITH_FULL_IMAGE:figures/full_fig_p008_2.png] view at source ↗
Figure 3
Figure 3. Figure 3: (a) presents the original queue; (b) illustrates how the waiting times change after [PITH_FULL_IMAGE:figures/full_fig_p009_3.png] view at source ↗
Figure 4
Figure 4. Figure 4: The Normal column shows a solution with a step length of 3 under normal con￾ditions. The Decomposition column displays the breakdown of this multi-step solution. In Step 1 of the Decomposition column, a job move is selected from the forward solution set that is theoretically beneficial to the total waiting time. Steps 2 and 3 then perform further optimization under the guidance of optimality conditions. se… view at source ↗
Figure 5
Figure 5. Figure 5: We provide two examples in the figure, columns (a) and (b), corresponding to the [PITH_FULL_IMAGE:figures/full_fig_p021_5.png] view at source ↗
Figure 6
Figure 6. Figure 6: In the figure, blue and yellow areas represent [PITH_FULL_IMAGE:figures/full_fig_p025_6.png] view at source ↗
Figure 1
Figure 1. Figure 1: Job 4 moves to the position between jobs 5 and 6. [PITH_FULL_IMAGE:figures/full_fig_p041_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: Fig 2. Job 4 moves to the position between jobs 6 and 7. [PITH_FULL_IMAGE:figures/full_fig_p055_2.png] view at source ↗
Figure 3
Figure 3. Figure 3: Fig 3. Job 4 is moved to the position between jobs 3 and 4. [PITH_FULL_IMAGE:figures/full_fig_p074_3.png] view at source ↗
Figure 4
Figure 4. Figure 4: Fig 4. Job 4 moves to the position between job 1 and 2. [PITH_FULL_IMAGE:figures/full_fig_p084_4.png] view at source ↗
read the original abstract

This paper studies the non-preemptive single-machine scheduling problem with heterogeneous release times and processing times, with the objective of minimizing total waiting time. The problem is known to be NP-hard. By modeling machine idle time as negative waiting time, we establish a unified waiting-time formulation that compresses the original four-dimensional description into a two-dimensional representation depending only on processing times and waiting times, thereby substantially simplifying the structural analysis of the problem. Based on this representation, ideal directions are defined from the structure induced by an optimal solution, and it is shown that every non-optimal schedule admits an ideal improvement path. It is further proved that improvable ideal directions require no coordination and can therefore be treated as independent improvement units. The theoretical analysis also shows that the realizability of every improvable ideal direction can be determined in finitely many steps, thereby laying the foundation for an overall solution framework. For each improvable ideal direction, by analyzing the propagation of the decrease flow and the increase flow under local adjustments, we prove that queue discontinuity is the unique structural obstacle to the realization of ideal improvement paths. A complete characterization of the resulting local optima is then established, and corresponding repair operators are designed. On this basis, an iterative repair algorithm under the improvement-path framework is developed. It is proved to terminate in finitely many steps, return a globally optimal schedule, and admit an explicit upper bound on its time complexity. This work provides a new analytical perspective and solution framework for this class of NP-hard scheduling problems.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

3 major / 2 minor

Summary. The paper studies the NP-hard single-machine scheduling problem with release times to minimize total waiting time. It introduces a unified waiting-time formulation that models idle time as negative waiting time, compressing the problem into a two-dimensional representation based on processing times and waiting times. From this, ideal directions are defined relative to optimal solution structure; the authors claim every non-optimal schedule admits an ideal improvement path, that improvable directions require no coordination, that queue discontinuity is the sole obstacle to realizability, and that local repair operators suffice to characterize local optima. An iterative repair algorithm is then developed and proved to terminate in finitely many steps, return a globally optimal schedule, and admit an explicit time-complexity bound.

Significance. If the central proofs hold, the work supplies a new structural framework and exact algorithm for a classic NP-hard scheduling problem, with the finite-termination guarantee and explicit complexity bound as notable strengths. The two-dimensional compression and improvement-path perspective could offer reusable insights for related scheduling variants, though the absence of computational experiments or machine-checked verification limits immediate practical assessment.

major comments (3)
  1. [unified waiting-time formulation and ideal-directions section] The claim that the two-dimensional waiting-time formulation fully preserves release-time ordering constraints (and therefore that every non-optimal schedule admits a realizable ideal improvement path) is load-bearing for both the path-existence theorem and the subsequent optimality proof; the manuscript does not provide an explicit verification that no ordering information is lost under simultaneous flow propagations from multiple directions.
  2. [characterization of local optima and repair operators] The assertion that queue discontinuity is the unique structural obstacle and that local repair operators suffice to realize all improvable ideal directions (thereby guaranteeing finite termination) requires a complete case analysis; if simultaneous adjustments can generate new discontinuities not captured by the defined operators, the termination and global-optimality arguments would not cover all instances.
  3. [proof that improvable ideal directions require no coordination] The independence claim that improvable ideal directions require no coordination is used to treat them as separate improvement units; this step is central to the algorithm design yet rests on the modeling choice without an independent combinatorial argument showing that cross-direction interactions cannot create additional realizability obstacles.
minor comments (2)
  1. [preliminaries] Notation for the two-dimensional waiting-time vector and the definition of 'decrease flow' versus 'increase flow' should be introduced with an explicit example early in the manuscript to improve readability.
  2. [algorithm complexity analysis] The explicit upper bound on time complexity is stated but its derivation is only sketched; a self-contained derivation or reference to the precise recurrence would strengthen the presentation.

Simulated Author's Rebuttal

3 responses · 0 unresolved

We thank the referee for the careful and constructive review of our manuscript. The comments identify areas where greater explicitness in the proofs would strengthen the presentation. We address each major comment below and will incorporate clarifications and additional arguments in the revised version.

read point-by-point responses

  1. Referee: [unified waiting-time formulation and ideal-directions section] The claim that the two-dimensional waiting-time formulation fully preserves release-time ordering constraints (and therefore that every non-optimal schedule admits a realizable ideal improvement path) is load-bearing for both the path-existence theorem and the subsequent optimality proof; the manuscript does not provide an explicit verification that no ordering information is lost under simultaneous flow propagations from multiple directions.

    Authors: We appreciate this observation. The unified waiting-time formulation encodes release-time constraints directly into the waiting-time variables (with idle time as negative waiting time), so that the two-dimensional representation inherits the original ordering. Ideal directions are then defined relative to the optimal structure, ensuring that any admissible path respects these constraints. While this preservation is implicit in the derivation of the path-existence theorem, we agree that an explicit verification for simultaneous multi-direction propagations would improve clarity. In the revision we will add a dedicated lemma proving that no ordering information is lost under simultaneous flow propagations, thereby reinforcing both the path-existence result and the optimality argument. revision: yes

  2. Referee: [characterization of local optima and repair operators] The assertion that queue discontinuity is the unique structural obstacle and that local repair operators suffice to realize all improvable ideal directions (thereby guaranteeing finite termination) requires a complete case analysis; if simultaneous adjustments can generate new discontinuities not captured by the defined operators, the termination and global-optimality arguments would not cover all instances.

    Authors: We thank the referee for emphasizing the need for a complete case analysis. Our analysis of decrease- and increase-flow propagations under local adjustments shows that queue discontinuity is the only structural obstacle that can arise, because other potential conflicts are resolved locally. To address the possibility that simultaneous adjustments might create new discontinuities, we will expand the relevant section with an exhaustive case analysis of all pairwise and multi-direction interaction patterns. This will explicitly confirm that every new discontinuity is captured by the defined repair operators, thereby securing the finite-termination and global-optimality claims. revision: yes

  3. Referee: [proof that improvable ideal directions require no coordination] The independence claim that improvable ideal directions require no coordination is used to treat them as separate improvement units; this step is central to the algorithm design yet rests on the modeling choice without an independent combinatorial argument showing that cross-direction interactions cannot create additional realizability obstacles.

    Authors: We acknowledge that the independence of improvable ideal directions would benefit from a self-contained combinatorial argument. The manuscript derives independence from the separation of flow propagations in the two-dimensional representation. To supply an independent combinatorial justification, we will insert a new proposition that models the schedule as a directed graph and shows, via a simple path-decomposition argument, that adjustments along distinct ideal directions cannot interfere with each other's realizability. This will provide the requested combinatorial support without relying solely on the modeling choice. revision: yes

Circularity Check

0 steps flagged

No significant circularity detected

full rationale

The derivation starts from an explicit modeling choice (idle time as negative waiting time) that produces the two-dimensional representation. Ideal directions and the existence of improvement paths are then defined and proved from the induced structure and problem properties, without the definitions presupposing the claimed existence or optimality. The finite termination, global optimality, and complexity bound follow from separate analysis of flow propagation, queue discontinuity, and local repair operators. No load-bearing step reduces by construction to a fitted input, self-definition, or self-citation chain; the central claims retain independent content from the modeling and proof steps.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The paper relies on standard combinatorial optimization assumptions and introduces analytical constructs such as ideal directions derived directly from the problem structure rather than new postulated entities.

axioms (2)
  • domain assumption The single-machine scheduling problem with release times and total waiting time objective is NP-hard.
    Accepted as established prior knowledge in the abstract.
  • domain assumption Machine idle time can be modeled as negative waiting time to produce a unified two-dimensional formulation.
    This is the central modeling step that enables the subsequent structural analysis.

pith-pipeline@v0.9.0 · 5802 in / 1264 out tokens · 41513 ms · 2026-05-19T07:02:39.128283+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

What do these tags mean?
matches
The paper's claim is directly supported by a theorem in the formal canon.
supports
The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends
The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses
The paper appears to rely on the theorem as machinery.
contradicts
The paper's claim conflicts with a theorem or certificate in the canon.
unclear
Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.

Reference graph

Works this paper leans on

44 extracted references · 44 canonical work pages · 1 internal anchor

  1. [1]

    doi: https://doi.org/10.1016/S0167-5060(08)70743-X

    Elsevier, 1977. doi: https://doi.org/10.1016/S0167-5060(08)70743-X. URL https: //www.sciencedirect.com/science/article/pii/S016750600870743X. Igor Malheiros, Artur Pessoa, Micha¨ el Poss, and Anand Subramanian. Computing the worst- case due dates violations with budget uncertainty.Operations Research Letters, 56:107148,

    work page doi:10.1016/s0167-5060(08)70743-x 1977

  2. [2]

    doi: https://doi.org/10.1016/j.orl.2024.107148

    ISSN 0167-6377. doi: https://doi.org/10.1016/j.orl.2024.107148. URL https: //www.sciencedirect.com/science/article/pii/S0167637724000841. Artur Alves Pessoa, Teobaldo Bulh˜ oes, Vitor Nesello, and Anand Subramanian. Exact approaches for single machine total weighted tardiness batch scheduling. INFORMS Journal on Computing , 34(3):1512–1530, 2022. doi: 10....

    work page doi:10.1016/j.orl.2024.107148 2024

  3. [3]

    An Improvement-Path Framework and an Exact Algorithm for Single-Machine Scheduling with Release Times

    ISSN 0377-2217. doi: https://doi.org/10.1016/j.ejor.2013.02.048. URL https: //www.sciencedirect.com/science/article/pii/S0377221713001975. Shunji Tanaka, Shuji Fujikuma, and Mituhiko Araki. An exact algorithm for single-machine scheduling without machine idle time. Journal of Scheduling , 12:575–593, 2009. doi: 110.1007/s10951-008-0093-5. URL https://doi....

    work page internal anchor Pith review Pith/arXiv arXiv doi:10.1016/j.ejor.2013.02.048 2013

  4. [4]

    Case 1: wi > 0,wi+1 > 0, both job i and i + 1 are in the same continuous queue

    Therefore, only two cases need to be discussed. Case 1: wi > 0,wi+1 > 0, both job i and i + 1 are in the same continuous queue. We have max(0,wi) +pi =wi +pi =ro 0 +po 0−ri +pi, max(0,wi+1) =wi+1 =ro 0 +po 0 +pi−ri+1, ∵the first-come, last-served ri+1 <r i,∴max(0,wi) +pi < max(0,w (i + 1)). The inequality holds. Case 2: wi ≤0,wi+1 > 0, job i is the queue ...

    work page

  5. [5]

    0” to “1

    The equation for the change in total waiting time is as follows: ∆w =I1 +I2 +π6(I2), where I1 =p5−∆w− 6−min(0,w 5), and initial value is ∆ w− 5 =p4−min(0,w 4). I2 =    p4, if w5≤0, max(min(w4, 0),−p5,p 4−w5), if w5 > 0. The updated waiting time of job 4 is: w2 4 =p4 +p5−∆w− 6−min(0,w 5) + max(0,w 4). where initial value is ∆ w− 5 =p4−min(0,w 4). We hav...

    work page

  6. [6]

    The impact of job 3 on the total waiting time is: ∆ 3 = ∆w+ 4 = 0

    When p3 +p4−w4≤0, job 3 is the queue leader. The impact of job 3 on the total waiting time is: ∆ 3 = ∆w+ 4 = 0. The adjustment of job 5 is as follows: ∆w5 =ro 3 +p3−r5−w5 =ro 3 +p3−r5−(ro 3 +p3 +p4−r5) =−p4. The change of total waiting time is: ∆w = ∆ 3 + ∆ 4 +π5(∆w5) =p4−w4−p4 +π5(−p4)

    work page

  7. [7]

    The impact of job 3’ waiting time change on the total waiting time is: ∆ 3 = ∆w+ 4 =p3 +p4−w4

    When p3 +p4−w4 > 0, it means job 3 is part of the continuous queue. The impact of job 3’ waiting time change on the total waiting time is: ∆ 3 = ∆w+ 4 =p3 +p4−w4. The change of job 5’s waiting time is: ∆w5 =r3 +w2 3 +p3−r5−w5 =ro 3 +p3 +p4−w4 +p3−r5−(ro 3 +p3 +p4−r5) =p3−w4. 47 The change of total waiting time is: ∆w = ∆ 3 + ∆ 4 +π5(∆w5) =p4−w4 +p3−w4 +π5...

    work page

  8. [8]

    The change of job 5 is: ∆w5 =r3 +w2 3 +p3−r5−w5 =r3 +w3 +p4 +p3−r5−(ro 3 +p3 +p4−r5) =w3

    When w3 +p4 > 0, job 3 is in the continuous queue, its impact on the total waiting time is: ∆ 3 = ∆w+ 4 =w3 +p4. The change of job 5 is: ∆w5 =r3 +w2 3 +p3−r5−w5 =r3 +w3 +p4 +p3−r5−(ro 3 +p3 +p4−r5) =w3. Then, the adjustment of total waiting time is: ∆w = ∆ 3 + ∆ 4 +π5(∆w5) =p4−p3 +w3 +w3 +π5(w3)

    work page

  9. [9]

    48 The change of job 5 is: ∆w5 =ro 3 +p3−r5−w5 =ro 3 +p3−r5−(r3 +p3 +p4−r5) =−p4

    When w3 +p4≤0, job 3 is the queue leader, it changes the total waiting time by: ∆ 3 = ∆w+ 4 = 0. 48 The change of job 5 is: ∆w5 =ro 3 +p3−r5−w5 =ro 3 +p3−r5−(r3 +p3 +p4−r5) =−p4. The change of total waiting time is as follows: ∆w = ∆ 3 + ∆ 4 +π5(∆w5) =w3−p3 +p4−p4 +π5(−p4). Case 4: w4 > 0,w 3 > 0, both jobs 3 and 4 are the members of the continuous queue....

    work page

  10. [10]

    The new information of job 3 is: ∆w3 =ro 2 +p2−r3−w3 =w3−w3 = 0

    Whenw2 +p4≤0, job 2 is the queue leader, the influence of job 2 on the total waiting time is: ∆ 2 = ∆w+ 3 = 0. The new information of job 3 is: ∆w3 =ro 2 +p2−r3−w3 =w3−w3 = 0. w2 3 =w3 + ∆w3 =w3≤0. Then, job 3 is the queue leader, the effect of job 3 on the total waiting time is: ∆ 3 = ∆w+ 4 = 0. 60 The change of job 5’s waiting time is: ∆w5 =ro 3 +p3−r5−...

    work page

  11. [11]

    The updated information about job 3 is: ∆w3 =r2 +w2 2 +p2−r3−w3 =w2 2 =w2 +p4

    When w2 +p4 > 0, job 2 belongs to the continuous queue, its influence on the total waiting time is: ∆ 2 = ∆w+ 3 =w2 +p4. The updated information about job 3 is: ∆w3 =r2 +w2 2 +p2−r3−w3 =w2 2 =w2 +p4. w2 3 =w3 + ∆w3 =w2 +w3 +p4. i ) When w2 +w3 +p4≤0, job 3 is the queue leader, and its affect on the total waiting time can be listed: ∆ 3 = ∆w+ 4 = 0. The ch...

    work page

  12. [12]

    62 The information of job 3, after job 4’s relocation, is as follows: ∆w3 =r2 +w2 2 +p2−r3−w3 =p2 +p3 +p4−w3−w4

    When p2 +p3 +p4−w3−w4 > 0, job 2 is part of continuous queue, its influence on the total waiting time is: ∆ 2 = ∆w+ 3 =p2 +p3 +p4−w3−w4. 62 The information of job 3, after job 4’s relocation, is as follows: ∆w3 =r2 +w2 2 +p2−r3−w3 =p2 +p3 +p4−w3−w4. w2 3 =w3 + ∆w3 =p2 +p3 +p4−w4. i ) When p2 +p3 +p4−w4≤0, job 3 is the queue leader, and its impact on the t...

    work page

  13. [13]

    The new information about job 3, after job 4’s moved, is as follows: ∆w3 =ro 2 +p2−r3−w3 = 0, w2 3 =w3 + ∆w3 =w3

    When p2 +p3 +p4−w3−w4≤0, job 2 is the queue leader, and its impact on the total waiting time is: ∆ 2 = ∆w+ 3 = 0. The new information about job 3, after job 4’s moved, is as follows: ∆w3 =ro 2 +p2−r3−w3 = 0, w2 3 =w3 + ∆w3 =w3. Forw3≤0, job 3 still be the queue leader, and its impact on the total waiting time is: ∆ 3 = ∆w+ 4 = 0. The change of total waiti...

    work page

  14. [14]

    The updated information of job 3 is: ∆w3 =r2 +w2 2 +p2−r3−w3 =r2 +w2 +p4 +p2−r3−w3 =w2 +p4

    When w2 +p4 > 0, job 2 belongs to the continuous queue, and its influence on the total waiting time is: ∆ 2 = ∆w+ 3 =w2 +p4. The updated information of job 3 is: ∆w3 =r2 +w2 2 +p2−r3−w3 =r2 +w2 +p4 +p2−r3−w3 =w2 +p4. w2 3 =w3 + ∆w3 =w3 +w2 +p4 > 0. 65 Forw2 3 > 0, job 3 is one of the members of the continuous queue, and its impact on the total waiting tim...

    work page

  15. [15]

    The new information about job 3 is: ∆w3 =ro 2 +p2−r3−w3 = 0

    When w2 +p4≤0, job 2 is the queue leader, and its affect on the total waiting time is: ∆ 2 = ∆w+ 3 = 0. The new information about job 3 is: ∆w3 =ro 2 +p2−r3−w3 = 0. w2 3 =w3 + ∆w3 =w3. The total waiting time’s change is: ∆w = ∆ 2 + ∆ 3 + ∆ 4 +π5(∆w5) =w2−p2−p3 +p4−p4 +π5(−p4). (2) If w2 +w4−p2−p3≤0, job 4 is the queue leader, we can calculate that: ∆ 4 = ...

    work page

  16. [16]

    The new information of job 3 is: ∆w3 =r2 +p2 +w2 2−r3−w3 =p2 +p2 +p3 +p4−w4 +r2−r3−w3 =p2 +p3 +p4−w4

    When p2 +p3 +p4−w4 > 0, job 2 is part of continuous queue, and its impact on the total waiting time is: ∆ 2 = ∆w+ 3 =p2 +p3 +p4−w4. The new information of job 3 is: ∆w3 =r2 +p2 +w2 2−r3−w3 =p2 +p2 +p3 +p4−w4 +r2−r3−w3 =p2 +p3 +p4−w4. w2 3 =w3 + ∆w3 =p2 +p3 +p4−w4 +w3 > 0. Now, job 3 belongs to the continuous queue, and its influence on the total waiting t...

    work page

  17. [17]

    The updated information about job 3 is: ∆w3 =ro 2 +p2−r3−w3 = 0, w2 3 =w3 > 0 Forw2 3 > 0, the impact of job 3 on the total waiting time is: ∆ 3 = ∆w+ 4 = 0

    When p2 +p3 +p4−w4≤0, job 2 is the queue leader, and its effect on the total waiting time is: ∆ 2 = ∆w+ 3 = 0. The updated information about job 3 is: ∆w3 =ro 2 +p2−r3−w3 = 0, w2 3 =w3 > 0 Forw2 3 > 0, the impact of job 3 on the total waiting time is: ∆ 3 = ∆w+ 4 = 0. The change of job 5’s waiting time is: ∆w5 =r3 +w3 +p3−r3−w5 =r3 +w3 +p3−r5−(r3 +w3 +p3 ...

    work page

  18. [18]

    The change of waiting time of job 5 is: ∆w5 =ro 3 +p3−r5−w5 =−p4

    If p4 +w3≤0, at this point, job 3 is the queue leader, and its impact on the total waiting time is: ∆ 3 = ∆w+ 4 = 0. The change of waiting time of job 5 is: ∆w5 =ro 3 +p3−r5−w5 =−p4. Finally, the change of total waiting time is: ∆w = ∆ 2 + ∆ 3 + ∆ 4 +π5(∆w5) =w3−p2−p3 +p4 +p4−p4 +π5(−p4) 69

    work page

  19. [19]

    The change of job 5’s waiting time is: w5 =r3 +w2 3 +p3−r5−w5 =p4 +w3−p4 =w3

    If p4 +w3 > 0, job 3 is in the continuous queue, the impact of job 3 on the total waiting time is: ∆ 3 = ∆w+ 4 =w3 +p4. The change of job 5’s waiting time is: w5 =r3 +w2 3 +p3−r5−w5 =p4 +w3−p4 =w3. The change of total waiting time is as follows: ∆w = ∆ 2 + ∆ 3 + ∆ 4 +π5(∆w5) =p4 +w3−p2−p3 +p4 +w3 +π5(w3). (2) When w4 +w3−p2−p3≤≤0, job 4 is the queue leade...

    work page

  20. [20]

    The change of job 5’s waiting time is: ∆w5 =r3 +w2 3 +p3−r5−w5 =r3 +p2 +p3 +p4−w4 +p3−r5−(ro 3 +p3 +p4−r5) =p2 +p3−w4

    If p2 +p3 +p4−w4 > 0, job 3 is one of the members of the continuous queue, and its influence on the total waiting time is: ∆ 3 = ∆w+ 4 =p2 +p3 +p4−w4−w3. The change of job 5’s waiting time is: ∆w5 =r3 +w2 3 +p3−r5−w5 =r3 +p2 +p3 +p4−w4 +p3−r5−(ro 3 +p3 +p4−r5) =p2 +p3−w4. Finally, the adjustment of total waiting time is as follows: ∆w = ∆ 2 + ∆ 3 + ∆ 4 +π...

    work page

  21. [21]

    The change of job 5’s waiting time is: ∆w5 =ro 3 +p3−r5−w5 =ro 3 +p3−r5−(ro 3 +p3 +p4−r5) =−p4

    If p2 +p3 +p4−w4≤0, job 3 is the queue leader, and its impact on the total waiting time is: ∆ 3 = ∆w+ 4 = 0. The change of job 5’s waiting time is: ∆w5 =ro 3 +p3−r5−w5 =ro 3 +p3−r5−(ro 3 +p3 +p4−r5) =−p4. Finally, the adjustment of total waiting time caused by job 4’s relocation is calculated 71 as: ∆w = ∆ 2 + ∆ 3 + ∆ 4 +π5(∆w5) =p4−w4 +p2 +p3 +p4−w3−w4−p...

    work page

  22. [22]

    The adjacent exchange of jobs 4 and 5 essentially is job 4 relocating after job 5, or 76 equivalently, job 5 relocating before job 4

    + min(0,w 2 5)). The adjacent exchange of jobs 4 and 5 essentially is job 4 relocating after job 5, or 76 equivalently, job 5 relocating before job 4. The computation formula of the job’s waiting time after the exchange is: w2 5 =w5 + min(0,w 4)−p4, w2 4 =w4 + max(p5,p 4 +p5−min(0,w 4)−w5), jobs 4 and 5 satisfy the condition of Proposition 1: max(0,w 4) +...

    work page

  23. [23]

    The additional adjustment caused by the exchange is: ∆wminus = min(0,w 4) + min(0,w 5)−min(0,w 2 4)−min(0,w 2

    + min(0,w 2 5)) =fI. The additional adjustment caused by the exchange is: ∆wminus = min(0,w 4) + min(0,w 5)−min(0,w 2 4)−min(0,w 2

    work page

  24. [24]

    Finally, we have: f 3 T =f 2 T + ∆wminus =fI =f 0 T

    = 0. Finally, we have: f 3 T =f 2 T + ∆wminus =fI =f 0 T. This shows that if fI meets the condition of Case 1, exchanging jobs 4 and 5 does not affect the subsequence queue, and at this point, the local optimum is the global optimum. Case 2: w2 5≥fI > 0, it means:w5 + min(0,w 4)−p4≥fI > 0 The proof process is the same as the Case 1. Case 3: −fI≤w2 5≤0, im...

    work page

  25. [25]

    The additional adjustment due to the exchange is: ∆wminus = min(0,w 4) + min(0,w 5)−min(0,w 2 4)−min(0,w 2

    + min(0,w 2 5)) = max(0,fI +w5−p4). The additional adjustment due to the exchange is: ∆wminus = min(0,w 4) + min(0,w 5)−min(0,w 2 4)−min(0,w 2

    work page

  26. [26]

    78 From the precondition, we get−fI≤w5−p4, sof 2 T = max(0,fI +w5−p4) =fI +w5−p4

    =p4−w5. 78 From the precondition, we get−fI≤w5−p4, sof 2 T = max(0,fI +w5−p4) =fI +w5−p4. Finally, the initial value of the increasing flow for job 6 is: f 3 T =f 2 T + ∆wminus =fI =f 0 T. It shows that exchanging jobs 4 and 5 does not affect the subsequence queue; at this point, the local optimum is the global optimum. (2) When w4 > 0,w 5≤0: In this cond...

    work page

  27. [27]

    The extra adjustment caused by the swap is: ∆wminus = min(0,w 4) + min(0,w 5)−min(0,w 2 4)−min(0,w 2 5) =−(w5−p4) +w5 =p4

    + min(0,w 2 5)) = max(0,fI +w5−p4), According to preconditions,−fI≤w5−p4 holds, so it can deduce that: f 2 T = max(0,fI +w5−p4) =fI +w5−p4. The extra adjustment caused by the swap is: ∆wminus = min(0,w 4) + min(0,w 5)−min(0,w 2 4)−min(0,w 2 5) =−(w5−p4) +w5 =p4. 79 Finally, the initial value of the increasing flow passed to job 6 is: f 3 T =f 2 T + ∆wminu...

    work page

  28. [28]

    The extra adjustment for job 6’s initial value of the increasing flow is: ∆wminus = min(0,w 4) + min(0,w 5)−min(0,w 2 4)−min(0,w 2 5) =w4−(w5−p4 +w4) =p4−w5

    + min(0,w 2 5)) = max(0,fI +w5−p4 +w4) =fI +w5−p4 +w4. The extra adjustment for job 6’s initial value of the increasing flow is: ∆wminus = min(0,w 4) + min(0,w 5)−min(0,w 2 4)−min(0,w 2 5) =w4−(w5−p4 +w4) =p4−w5. 80 Finally: f 3 T =f 2 T + ∆wminus =fI +w4 =f 0 T. This shows that exchanging jobs 4 and 5 does not affect the subsequence queue; now, the local...

    work page

  29. [29]

    The additional adjustment caused by the swap is: ∆wminus = min(0,w 4) + min(0,w 5)−min(0,w 2 4)−min(0,w 2 5) =w4 +w5−(w5−p4 +w4) =p4

    + min(0,w 2 5)) = max(0,fI +w5−p4 +w4) =fI +w5−p4 +w4. The additional adjustment caused by the swap is: ∆wminus = min(0,w 4) + min(0,w 5)−min(0,w 2 4)−min(0,w 2 5) =w4 +w5−(w5−p4 +w4) =p4. Finally, we have: f 3 T =f 2 T + ∆wminus =fI +w4 +w5 =f 0 T. Now, the local optimum is the global optimum. Case 4 : w2 5 <−fI≤0, it means that w5 + min(0,w 4)−p4 <−fI≤0...

    work page

  30. [30]

    According to preconditions,−fI >w 5−p4 holds, thus it can imply that f 2 T = 0

    + min(0,w 2 5)) = max(0,fI +w5−p4). According to preconditions,−fI >w 5−p4 holds, thus it can imply that f 2 T = 0. The extra adjustment for the initial value of the increasing flow can expressed as: ∆wminus = min(0,w 4) + min(0,w 5)−min(0,w 2 4)−min(0,w 2 5) =p4−w5. Finally, it can be written as: f 3 T =f 2 T + ∆wminus =p4−w5 >f I =f 0 T. At this point, ...

    work page

  31. [31]

    + min(0,w 2 5)) = max(0,fI +w5−p4). Since−fI >w 5−p4, sof 2 T = 0.The extra adjustment of the initial value of the increasing flow, following the swap, is: ∆wminus = min(0,w 4) + min(0,w 5)−min(0,w 2 4)−min(0,w 2 5) =−(w5−p4) +w5 =p4. In the end, we obtain that: f 3 T =f 2 T + ∆wminus =p4 >f 0 T. At this point, the swap affects the subsequent queue, and i...

    work page

  32. [32]

    The additional adjustment after the exchange is: ∆wminus = min(0,w 4) + min(0,w 5)−min(0,w 2 4)−min(0,w 2 5) =w4−(w5−p4 +w4) =p4−w5

    + min(0,w 2 5)) = max(0,fI +w5−p4 +w4) = 0. The additional adjustment after the exchange is: ∆wminus = min(0,w 4) + min(0,w 5)−min(0,w 2 4)−min(0,w 2 5) =w4−(w5−p4 +w4) =p4−w5. Finally, we can get that: f 3 T =f 2 T + ∆wminus =p4−w5 >f 0 T. At this point, the swap increases the waiting time of the subsequent queue, and it cannot be determined that a local...

    work page

  33. [33]

    The additional adjustment caused by the exchange is: ∆wminus = min(0,w 4) + min(0,w 5)−min(0,w 2 4)−min(0,w 2 5) =w4 +w5−(w5−p4 +w4) =p4

    + min(0,w 2 5)) = max(0,fI +w5−p4 +w4) = 0. The additional adjustment caused by the exchange is: ∆wminus = min(0,w 4) + min(0,w 5)−min(0,w 2 4)−min(0,w 2 5) =w4 +w5−(w5−p4 +w4) =p4. Finally, we have that: f 3 T =f 2 T + ∆wminus =p4 >f 0 T. Under those conditions, it cannot be determined that a local optimum is the global optimum. Conclusion: In summary, i...

    work page

  34. [34]

    + min(0,w 2 4)≤fI + min(0,w 2 5), 0≤fI + 5∑ j=4 min(0,w 2 j ). This formula indicates that if the initial value of the increasing flow can offset the total machine idle time of the swapped queue, the solution offered by the Adjacent Exchange Rule is the globally optimum. The general expression is: 0≤fI + σ′ t(n)∑ σ′ t(j)∈σ′ t min(0,w 2 σ′ t(j)), where σ′ ...

    work page

  35. [35]

    To reduce the total waiting time, both ways require ∆ wpositive < 0

    The preceding analysis reveals that the Adjacent Exchange Rule affects the increasing flow of the following queue in only two outcomes: no change or an increase. To reduce the total waiting time, both ways require ∆ wpositive < 0. Therefore, we discuses ∆ wpositive < 0 under Cases 1, 2, and 3 to find the optimality conditions for the Adjacent Exchange Rul...

    work page

  36. [36]

    While when ∆ wpositive < 0 holds, it can imply that ∆wpositive =p5 +p4−2w5−2fI < 0, the condition p4 +p5 < 2(w5 +fI) is bound to hold

    So, it is only when p5 <p 4 holds, we can have ∆ wpositive < 0. While when ∆ wpositive < 0 holds, it can imply that ∆wpositive =p5 +p4−2w5−2fI < 0, the condition p4 +p5 < 2(w5 +fI) is bound to hold. (2) When w4 > 0,w 5≤0: The waiting time of the exchanged jobs 4 and 5 are: w2 5 =w5−p4≤0, w2 4 =w4 +p4 +p5−w5≥0. The corresponding change in waiting time afte...

    work page

  37. [37]

    At this point, ∆ wpositive < 0 can be hold, only when p5 <p 4

    If w5 +fI > 0, it can be deduced that: ∆wpositive =p4 +p5−w5−fI−w5−fI ≥p5−p4. At this point, ∆ wpositive < 0 can be hold, only when p5 <p 4. It follows that ∆ wpositive = p5 +p4−2w5−2fI < 0, so p4 +p5 < 2(w5 +fI) holds. 2) If w5 +fI≤0, it follows that: ∆wpositive =p4 +p5−w5−fI. Sincep4−w5−fI≥0 and p5 > 0, ∆wpositive is always bigger than 0. Therefore, it ...

    work page

  38. [38]

    94 According to the preconditions (w4 +w5 +fI)≤p4, we have ∆wpositive =p4 +p5−2(w4 +w5 +fI) ≥p4 +p5−2p4 =p5−p4

    If w4 +fI > 0, it follows that: ∆wpositive = (p4 +p5−w5)−(w4 +fI)−(w4 +fI +w5) =p4 +p5−2(w4 +w5 +fI). 94 According to the preconditions (w4 +w5 +fI)≤p4, we have ∆wpositive =p4 +p5−2(w4 +w5 +fI) ≥p4 +p5−2p4 =p5−p4. The condition ∆ wpositive < 0 can be hold, if and only if p5 <p 4. If ∆ wpositive < 0 holds, we obtain: p4 +p5 < 2(w5 +fI)

    work page

  39. [39]

    From the conditions of Proposition 1 p4 + max(0,w 4)≥max(0,w 5), it follows that p4≥w5

    If w4 +fI≤0, we have that: ∆wpositive = (p4 +p5−w5)−w5 =p4 +p5−2w5 =p5−p4 + 2(p4−w5). From the conditions of Proposition 1 p4 + max(0,w 4)≥max(0,w 5), it follows that p4≥w5. Therefore, it is only when p5 <p 4, ∆ wpositive < 0 can be hold. When ∆ wpositive < 0 is true, it follows that ∆wpositive =p4 +p5−2w5 < 0. We can further imply that p4 +p5 < 2w5≤2(w5 ...

    work page

  40. [40]

    Because of preconditions w5 + min(0,w 4)−p4 <−fI, we have (w4 +w5 +fI)<p 4, so: ∆wpositive =p4 +p5−2(w4 +w5 +fI) >p 4 +p5−2p4 =p5−p4

    If w4 +fI > 0 and fI +w4 +w5 > 0, it follows that: ∆wpositive =p4 +p5−w5−(w4 +fI)−(fI +w4 +w5) =p4 +p5−2(w4 +w5 +fI). Because of preconditions w5 + min(0,w 4)−p4 <−fI, we have (w4 +w5 +fI)<p 4, so: ∆wpositive =p4 +p5−2(w4 +w5 +fI) >p 4 +p5−2p4 =p5−p4. ∆wpositive < 0 is only possible, when p5 <p 4 holds. At this point, we have p4 +p5 < 2(w4 +w5 +fI)≤2(w5 +...

    work page

  41. [41]

    Because of the preconditions w5 + min(0,w 4)−p4 <−fI, we have (w4 +w5 +fI)<p 4

    If w4 +fI > 0,fI +w4 +w5≤0, it follows that: ∆wpositive =p4 +p5−w5−(w4 +fI) =p4 +p5−(w4 +w5 +fI). Because of the preconditions w5 + min(0,w 4)−p4 <−fI, we have (w4 +w5 +fI)<p 4. So it has: ∆wpositive =p4 +p5−(w4 +w5 +fI) >p 4 +p5−p4 =p5 > 0. ∆wpositive < 0 fails to hold, and it is impossible to improve the total waiting time at this point

    work page

  42. [42]

    From the Proposition 1 p4 + max(0,w 4)≥max(0,w 5), it follows that p4≥w5

    If w4 +fI≤0, we can obtain that: ∆wpositive =p4 +p5−w5. From the Proposition 1 p4 + max(0,w 4)≥max(0,w 5), it follows that p4≥w5. So ∆wpositive =p4 +p5−w5 > 0. It is no way to reduce the total waiting time. Conclusion: In summary, When p5 < p4 holds, the Adjacent Exchange Rule may lead to an improvement in total waiting time. Moreover, although Lemma 3 wa...

    work page

  43. [43]

    The initial value of the decreasing flow passed to job 6 is: f 3 T =f 2 T−wminus = min(w5−p4,w 4 +p5)

    = 0. The initial value of the decreasing flow passed to job 6 is: f 3 T =f 2 T−wminus = min(w5−p4,w 4 +p5). The change of total waiting time is: ∆wpositive = max(0,w 2 5−∆w2− 5 ) + max(0,w 2 4−∆w2− 4 )−max(0,w 4−∆w− 4 )−max(0,w 5−∆w− 5 ) = max(0,p 4 +p5 +w4−w5)−max(0,w 5−w4). Compare p4 +p5 +w4−w5 to 0, we can get: i ) w5−p4≥p5 +w4 : It follows that: f 3 ...

    work page

  44. [44]

    The decreasing flow’s initial value passed to job 6 is: f 3 T =f 2 T−wminus =w5−p4

    = 0. The decreasing flow’s initial value passed to job 6 is: f 3 T =f 2 T−wminus =w5−p4. The change of the total waiting time is: ∆wpositive = max(0,w 2 5−∆w2− 5 ) + max(0,w 2 4−∆w2− 4 )−max(0,w 4−∆w− 4 )−max(0,w 5−∆w− 5 ) =w4 +p5−(w5−p4)−max(0,w 5−w4). Compare w5−w4 to 0, we have: i ) w5 >w 4: f 0 T =w4, f 0 T =w4≥w5−p4 =f 3 T, ∆wpositive =p4 +p5 + 2w4−2...

    work page