Relations of the Scheduling Zoo that need an encoding
Lax434175.Encodings · concepts/Lax434175/Encodings.lean · lax-434175
No public endorsements yet.
Loading review…
Sign in with ORCIDNatural Language Statement
Theorem
Eight relations of The Scheduling Zoo do not compare two specifications field by field, and are not threshold steps: the more special problem has to be encoded in the more general one by changing the instance.
Just in time inside on time. On a single machine, a job with processing time and due date completes exactly at its due date if and only if it is on time and starts no earlier than . Hence is a special case of with the release dates , and likewise with weights.
A single machine inside a two-machine flow shop. A job of the single machine becomes a job with an operation of length on the first machine followed by its operation on the second machine. Hence the decision version of reduces to that of , and likewise with weights.
Flow shops and parallel machines inside the two-stage flexible flow shop. A two-machine flow shop is a two-stage flexible flow shop with one machine in the second stage, and a problem on identical parallel machines is one in which every first operation has length . Hence the decision versions of and of reduce to that of , and likewise with weights.
The relations across machine models are stated for decision versions, because a problem on parallel machines has instances without machines and hence without schedules, which a shop problem cannot represent by an instance but only by an unreachable threshold.
Each reduction across machine models is stated with its effect on the numbers of jobs and machines: the number of jobs is unchanged; the flow shop has two machines, and the flexible flow shop of a problem on parallel machines has , that of a flow shop two.
Theorem. These eight relations hold, with these numbers of jobs and machines.
Concept map
Evidence
This concept declares 8 statements. Each proof establishes one of them relative to its assumptions.
1 flow2_flexibleFlow proven
2 flow2_flexibleFlow_weighted proven
3 identical_flexibleFlow proven
4 identical_flexibleFlow_weighted proven
5 justInTime_onTime proven
6 single_flow2 proven
7 single_flow2_weighted proven
8 weightedJustInTime_onTime proven
Lean source view on GitHub
| 1 | import Lax434175.ParallelProblems |
| 2 | import Lax434175.ShopProblems |
| 3 | import Lax434175.Parameters |
| 4 | |
| 5 | /-! |
| 6 | --- |
| 7 | title: Relations of the Scheduling Zoo that need an encoding |
| 8 | type: theorem |
| 9 | --- |
| 10 | Eight relations of The Scheduling Zoo do not compare two specifications field |
| 11 | by field, and are not threshold steps: the more special problem has to be |
| 12 | encoded in the more general one by changing the instance. |
| 13 | |
| 14 | **Just in time inside on time.** On a single machine, a job with processing |
| 15 | time and due date completes exactly at its due date if and only |
| 16 | if it is on time and starts no earlier than . Hence |
| 17 | is a special case of with |
| 18 | the release dates , and likewise with weights. |
| 19 | |
| 20 | **A single machine inside a two-machine flow shop.** A job of the single |
| 21 | machine becomes a job with an operation of length on the first machine |
| 22 | followed by its operation on the second machine. Hence the decision version |
| 23 | of reduces to that of , and |
| 24 | likewise with weights. |
| 25 | |
| 26 | **Flow shops and parallel machines inside the two-stage flexible flow |
| 27 | shop.** A two-machine flow shop is a two-stage flexible flow shop with one |
| 28 | machine in the second stage, and a problem on identical parallel machines is |
| 29 | one in which every first operation has length . Hence the decision |
| 30 | versions of and of reduce to |
| 31 | that of , and likewise with weights. |
| 32 | |
| 33 | The relations across machine models are stated for decision versions, |
| 34 | because a problem on parallel machines has instances without machines and |
| 35 | hence without schedules, which a shop problem cannot represent by an |
| 36 | instance but only by an unreachable threshold. |
| 37 | |
| 38 | Each reduction across machine models is stated with its effect on the |
| 39 | numbers of jobs and machines: the number of jobs is unchanged; the flow shop |
| 40 | has two machines, and the flexible flow shop of a problem on parallel |
| 41 | machines has , that of a flow shop two. |
| 42 | |
| 43 | **Theorem.** These eight relations hold, with these numbers of jobs and |
| 44 | machines. |
| 45 | -/ |
| 46 | |
| 47 | namespace Lax434175.Encodings |
| 48 | open Lax434175 Lax434175.Problems Lax434175.Assembly Lax434175.Parameters |
| 49 | |
| 50 | /-- `1 || γ` -/ |
| 51 | def single (objective : Objectives.Value) : Spec ParallelProblems.nonpreemptive := |
| 52 | ParallelProblems.spec _ (environment := .identical) (machineCount := .atMost 1) |
| 53 | (objective := objective) |
| 54 | |
| 55 | /-- `1 | r_j | γ` -/ |
| 56 | def singleRelease (objective : Objectives.Value) : Spec ParallelProblems.nonpreemptive := |
| 57 | ParallelProblems.spec _ (environment := .identical) (machineCount := .atMost 1) |
| 58 | (release := .releaseDates) (objective := objective) |
| 59 | |
| 60 | /-- `P || γ` -/ |
| 61 | def identical (objective : Objectives.Value) : Spec ParallelProblems.nonpreemptive := |
| 62 | ParallelProblems.spec _ (environment := .identical) (objective := objective) |
| 63 | |
| 64 | /-- `F2 || γ` -/ |
| 65 | def flow2 (objective : Objectives.Value) : Spec ShopProblems.family := |
| 66 | ShopProblems.spec (shopType := .flow) (machineSets := .byPosition) (machineCount := .atMost 2) |
| 67 | (objective := objective) |
| 68 | |
| 69 | /-- `FF(1,m) || γ` -/ |
| 70 | def flexibleFlow (objective : Objectives.Value) : Spec ShopProblems.family := |
| 71 | ShopProblems.spec (shopType := .flexibleFlow) (machineSets := .stages) (objective := objective) |
| 72 | |
| 73 | /-- The numbers of jobs and machines of an instance on parallel machines. -/ |
| 74 | def parallelSize {s : Spec ParallelProblems.nonpreemptive} |
| 75 | (x : Inst ParallelProblems.nonpreemptive s) : ℕ × ℕ := |
| 76 | (x.base.jobs, x.base.machines) |
| 77 | |
| 78 | /-- The numbers of jobs and machines of a shop instance. -/ |
| 79 | def shopSize {s : Spec ShopProblems.family} (x : Inst ShopProblems.family s) : ℕ × ℕ := |
| 80 | (x.base.jobs, x.base.machines) |
| 81 | |
| 82 | axiom justInTime_onTime : |
| 83 | SpecialCase (problem _ (single .sumZ)) (problem _ (singleRelease .sumU)) |
| 84 | |
| 85 | axiom weightedJustInTime_onTime : |
| 86 | SpecialCase (problem _ (single .sumWZ)) (problem _ (singleRelease .sumWU)) |
| 87 | |
| 88 | axiom single_flow2 : |
| 89 | ReducibleWith (A := problem _ (single .sumZ)) (B := problem _ (flow2 .sumZ)) parallelSize shopSize |
| 90 | (fun a b => b.1 = a.1 ∧ b.2 = 2) |
| 91 | |
| 92 | axiom single_flow2_weighted : |
| 93 | ReducibleWith (A := problem _ (single .sumWZ)) (B := problem _ (flow2 .sumWZ)) parallelSize shopSize |
| 94 | (fun a b => b.1 = a.1 ∧ b.2 = 2) |
| 95 | |
| 96 | axiom flow2_flexibleFlow : |
| 97 | ReducibleWith (A := problem _ (flow2 .sumZ)) (B := problem _ (flexibleFlow .sumZ)) shopSize shopSize |
| 98 | (fun a b => b.1 = a.1 ∧ b.2 = 2) |
| 99 | |
| 100 | axiom flow2_flexibleFlow_weighted : |
| 101 | ReducibleWith (A := problem _ (flow2 .sumWZ)) (B := problem _ (flexibleFlow .sumWZ)) shopSize shopSize |
| 102 | (fun a b => b.1 = a.1 ∧ b.2 = 2) |
| 103 | |
| 104 | axiom identical_flexibleFlow : |
| 105 | ReducibleWith (A := problem _ (identical .sumZ)) (B := problem _ (flexibleFlow .sumZ)) parallelSize shopSize |
| 106 | (fun a b => b.1 = a.1 ∧ b.2 = a.2 + 1) |
| 107 | |
| 108 | axiom identical_flexibleFlow_weighted : |
| 109 | ReducibleWith (A := problem _ (identical .sumWZ)) (B := problem _ (flexibleFlow .sumWZ)) parallelSize shopSize |
| 110 | (fun a b => b.1 = a.1 ∧ b.2 = a.2 + 1) |
| 111 | |
| 112 | end Lax434175.Encodings |
| 113 |
Used by
From Mathlib
none
Discussion
Ask a question or add context. Endorsements and structured flags are kept in the review panel above.
0 comments