The Two Conditions on a Feasible Set
Lax496464.Conditions · concepts/Lax496464/Conditions.lean · lax-496464
No public endorsements yet.
Loading review…
Sign in with ORCIDNatural Language Statement
Definition
Two conditions on a set of jobs, one for each stage of the shop.
Condition 1, can be preprocessed in time: for every , the jobs of whose second operations start no later than 's fit, together, into .
Condition 2, can be scheduled on machines: the jobs of can be partitioned into sets, no one of which contains two conflicting jobs.
Concept map
In the paper
- page 2 of this submission's paper
Lean source view on GitHub
| 1 | import Lax496464.FlowShop |
| 2 | |
| 3 | /-! |
| 4 | --- |
| 5 | title: The Two Conditions on a Feasible Set |
| 6 | type: definition |
| 7 | --- |
| 8 | Two conditions on a set of jobs, one for each stage of the shop. |
| 9 | |
| 10 | **Condition 1**, * can be preprocessed in time*: for every , the jobs of |
| 11 | whose second operations start no later than 's fit, together, into . |
| 12 | |
| 13 | **Condition 2**, * can be scheduled on machines*: the jobs of can be |
| 14 | partitioned into sets, no one of which contains two conflicting jobs. |
| 15 | |
| 16 | # Formalization Notes |
| 17 | |
| 18 | The paper writes Condition 1 as with the jobs |
| 19 | indexed in nondecreasing order of . That phrasing pins the sum down only once ties are |
| 20 | broken, and where the values are not distinct the form used here is the one the paper |
| 21 | means: two jobs with the same must *both* have been preprocessed by that time, so |
| 22 | both lengths count. A prefix of an enumeration that stopped at the first of them would |
| 23 | not. Sections 4 and 6 arrange for the values to be distinct, and there the two |
| 24 | readings agree; that they do is a statement of this submission rather than a convention |
| 25 | of this file, and so is the fact that the reading below is equivalent to the existence of |
| 26 | an actual schedule. |
| 27 | |
| 28 | Condition 2 is written as a colouring rather than as a partition. The data are the same — |
| 29 | a colour is the index of the part a job goes into — and a function is what the |
| 30 | formalization of a schedule uses; that a partition can be recovered is immediate. The |
| 31 | colour of a job outside is unconstrained. |
| 32 | |
| 33 | The sums are taken in , where the start times live, so that no truncated |
| 34 | subtraction appears in the condition. |
| 35 | -/ |
| 36 | |
| 37 | namespace Lax496464.Conditions |
| 38 | |
| 39 | open Lax496464.FlowShop Lax496464.FlowShop.Instance |
| 40 | |
| 41 | variable (I : Instance) |
| 42 | |
| 43 | /-- **Condition 1.** `Z` can be preprocessed in time: for every `j ∈ Z`, the jobs of `Z` |
| 44 | starting no later than `j` fit together into `[0, s j)`. -/ |
| 45 | def 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 |
| 49 | be coloured with `m` colours so that no two conflicting jobs share a colour. -/ |
| 50 | def 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 | |
| 54 | end Lax496464.Conditions |
| 55 |
Formalization Notes
The paper writes Condition 1 as with the jobs indexed in nondecreasing order of . That phrasing pins the sum down only once ties are broken, and where the values are not distinct the form used here is the one the paper means: two jobs with the same 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 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 is unconstrained.
The sums are taken in , 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.
0 comments