The Two Conditions on a Feasible Set

Lax496464.Conditions · concepts/Lax496464/Conditions.lean · lax-496464

definition

Loading review…

Sign in with ORCID

Community review

Flags

Each flag is tied to a public ORCID identity and explains why this concept may be incorrect.

No flags have been submitted.

    Community review

    Flag this concept

    State precisely what appears incorrect. This explanation will be public under your ORCID name.

    No source line selected.

    Natural Language Statement

    Definition

    Two conditions on a set ZZ of jobs, one for each stage of the shop.

    Condition 1, ZZ can be preprocessed in time: for every j∈Zj \in Z, the jobs of ZZ whose second operations start no later than jj's fit, together, into [0,sj)[0, s_j).

    Condition 2, ZZ can be scheduled on mm machines: the jobs of ZZ can be partitioned into mm sets, no one of which contains two conflicting jobs.

    Concept map
    2 concepts; 11 descendants hidden
    100%
    Proven claimDefinitionThis conceptRelated conceptA → B: B builds on A

    In the paper

    • page 2 of this submission's paper

    Lean source view on GitHub

    1import Lax496464.FlowShop
    2
    3/-!
    4---
    5title: The Two Conditions on a Feasible Set
    6type: definition
    7---
    8Two conditions on a set ZZ of jobs, one for each stage of the shop.
    9
    10**Condition 1**, *ZZ can be preprocessed in time*: for every j∈Zj \in Z, the jobs of ZZ
    11whose second operations start no later than jj's fit, together, into [0,sj)[0, s_j).
    12
    13**Condition 2**, *ZZ can be scheduled on mm machines*: the jobs of ZZ can be
    14partitioned into mm sets, no one of which contains two conflicting jobs.
    15
    16# Formalization Notes
    17
    18The paper writes Condition 1 as ∑i∈Z, i≤jpi≤sj\sum_{i \in Z,\ i \le j} p_i \le s_j with the jobs
    19indexed in nondecreasing order of ss. That phrasing pins the sum down only once ties are
    20broken, and where the ss values are not distinct the form used here is the one the paper
    21means: two jobs with the same ss must *both* have been preprocessed by that time, so
    22both lengths count. A prefix of an enumeration that stopped at the first of them would
    23not. Sections 4 and 6 arrange for the ss values to be distinct, and there the two
    24readings agree; that they do is a statement of this submission rather than a convention
    25of this file, and so is the fact that the reading below is equivalent to the existence of
    26an actual schedule.
    27
    28Condition 2 is written as a colouring rather than as a partition. The data are the same —
    29a colour is the index of the part a job goes into — and a function is what the
    30formalization of a schedule uses; that a partition can be recovered is immediate. The
    31colour of a job outside ZZ is unconstrained.
    32
    33The sums are taken in Z\mathbb{Z}, where the start times live, so that no truncated
    34subtraction appears in the condition.
    35-/
    36
    37namespace Lax496464.Conditions
    38
    39open Lax496464.FlowShop Lax496464.FlowShop.Instance
    40
    41variable (I : Instance)
    42
    43/-- **Condition 1.** `Z` can be preprocessed in time: for every `j ∈ Z`, the jobs of `Z`
    44starting no later than `j` fit together into `[0, s j)`. -/
    45def Preprocessable (Z : Finset I.Job) : Prop :=
    46 ∀ j ∈ Z, ∑ i ∈ Z.filter (fun i => s i ≤ s j), (I.p i : ℤ) ≤ s j
    47
    48/-- **Condition 2.** `Z` can be scheduled on the `m` second-stage machines: its jobs can
    49be coloured with `m` colours so that no two conflicting jobs share a colour. -/
    50def MSchedulable (Z : Finset I.Job) : Prop :=
    51 ∃ c : I.Job → ℕ, (∀ j ∈ Z, c j < I.machines) ∧
    52 ∀ i ∈ Z, ∀ j ∈ Z, i ≠ j → c i = c j → ¬ Conflict i j
    53
    54end Lax496464.Conditions
    55
    Formalization Notes

    The paper writes Condition 1 as ∑i∈Z, i≤jpi≤sj\sum_{i \in Z,\ i \le j} p_i \le s_j with the jobs indexed in nondecreasing order of ss. That phrasing pins the sum down only once ties are broken, and where the ss values are not distinct the form used here is the one the paper means: two jobs with the same ss must both have been preprocessed by that time, so both lengths count. A prefix of an enumeration that stopped at the first of them would not. Sections 4 and 6 arrange for the ss values to be distinct, and there the two readings agree; that they do is a statement of this submission rather than a convention of this file, and so is the fact that the reading below is equivalent to the existence of an actual schedule.

    Condition 2 is written as a colouring rather than as a partition. The data are the same — a colour is the index of the part a job goes into — and a function is what the formalization of a schedule uses; that a partition can be recovered is immediate. The colour of a job outside ZZ is unconstrained.

    The sums are taken in Z\mathbb{Z}, where the start times live, so that no truncated subtraction appears in the condition.

    Discussion

    Ask a question or add context. Endorsements and structured flags are kept in the review panel above.

    Loading discussion…