While this submission is a draft, it cannot be used by other submissions.

Relations of the Scheduling Zoo that need an encoding

Lax434175.Encodings · concepts/Lax434175/Encodings.lean · lax-434175

proven

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

    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 pjp_j and due date djd_j completes exactly at its due date if and only if it is on time and starts no earlier than dj−pjd_j - p_j. Hence 1∣∣∑Zj1 \mid\mid \sum Z_j is a special case of 1∣rj∣∑Uj1 \mid r_j \mid \sum U_j with the release dates rj=dj−pjr_j = d_j - p_j, 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 00 on the first machine followed by its operation on the second machine. Hence the decision version of 1∣∣∑Zj1 \mid\mid \sum Z_j reduces to that of F2∣∣∑ZjF2 \mid\mid \sum Z_j, 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 00. Hence the decision versions of F2∣∣∑ZjF2 \mid\mid \sum Z_j and of P∣∣∑ZjP \mid\mid \sum Z_j reduce to that of FF(1,m)∣∣∑ZjFF(1,m) \mid\mid \sum Z_j, 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 mm parallel machines has m+1m + 1, that of a flow shop two.

    Theorem. These eight relations hold, with these numbers of jobs and machines.

    Concept map
    25 concepts; 1 descendant hidden
    100%
    Proven claimDefinitionThis conceptRelated conceptA → B: B builds on A
    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

    4 identical_flexibleFlow_weighted proven

    5 justInTime_onTime proven

    7 single_flow2_weighted proven

    8 weightedJustInTime_onTime proven

    Lean source view on GitHub

    1import Lax434175.ParallelProblems
    2import Lax434175.ShopProblems
    3import Lax434175.Parameters
    4
    5/-!
    6---
    7title: Relations of the Scheduling Zoo that need an encoding
    8type: theorem
    9---
    10Eight relations of The Scheduling Zoo do not compare two specifications field
    11by field, and are not threshold steps: the more special problem has to be
    12encoded 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
    15time pjp_j and due date djd_j completes exactly at its due date if and only
    16if it is on time and starts no earlier than dj−pjd_j - p_j. Hence
    171∣∣∑Zj1 \mid\mid \sum Z_j is a special case of 1∣rj∣∑Uj1 \mid r_j \mid \sum U_j with
    18the release dates rj=dj−pjr_j = d_j - p_j, and likewise with weights.
    19
    20**A single machine inside a two-machine flow shop.** A job of the single
    21machine becomes a job with an operation of length 00 on the first machine
    22followed by its operation on the second machine. Hence the decision version
    23of 1∣∣∑Zj1 \mid\mid \sum Z_j reduces to that of F2∣∣∑ZjF2 \mid\mid \sum Z_j, and
    24likewise with weights.
    25
    26**Flow shops and parallel machines inside the two-stage flexible flow
    27shop.** A two-machine flow shop is a two-stage flexible flow shop with one
    28machine in the second stage, and a problem on identical parallel machines is
    29one in which every first operation has length 00. Hence the decision
    30versions of F2∣∣∑ZjF2 \mid\mid \sum Z_j and of P∣∣∑ZjP \mid\mid \sum Z_j reduce to
    31that of FF(1,m)∣∣∑ZjFF(1,m) \mid\mid \sum Z_j, and likewise with weights.
    32
    33The relations across machine models are stated for decision versions,
    34because a problem on parallel machines has instances without machines and
    35hence without schedules, which a shop problem cannot represent by an
    36instance but only by an unreachable threshold.
    37
    38Each reduction across machine models is stated with its effect on the
    39numbers of jobs and machines: the number of jobs is unchanged; the flow shop
    40has two machines, and the flexible flow shop of a problem on mm parallel
    41machines has m+1m + 1, that of a flow shop two.
    42
    43**Theorem.** These eight relations hold, with these numbers of jobs and
    44machines.
    45-/
    46
    47namespace Lax434175.Encodings
    48open Lax434175 Lax434175.Problems Lax434175.Assembly Lax434175.Parameters
    49
    50/-- `1 || γ` -/
    51def single (objective : Objectives.Value) : Spec ParallelProblems.nonpreemptive :=
    52 ParallelProblems.spec _ (environment := .identical) (machineCount := .atMost 1)
    53 (objective := objective)
    54
    55/-- `1 | r_j | γ` -/
    56def singleRelease (objective : Objectives.Value) : Spec ParallelProblems.nonpreemptive :=
    57 ParallelProblems.spec _ (environment := .identical) (machineCount := .atMost 1)
    58 (release := .releaseDates) (objective := objective)
    59
    60/-- `P || γ` -/
    61def identical (objective : Objectives.Value) : Spec ParallelProblems.nonpreemptive :=
    62 ParallelProblems.spec _ (environment := .identical) (objective := objective)
    63
    64/-- `F2 || γ` -/
    65def 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) || γ` -/
    70def 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. -/
    74def 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. -/
    79def shopSize {s : Spec ShopProblems.family} (x : Inst ShopProblems.family s) : ℕ × ℕ :=
    80 (x.base.jobs, x.base.machines)
    81
    82axiom justInTime_onTime :
    83 SpecialCase (problem _ (single .sumZ)) (problem _ (singleRelease .sumU))
    84
    85axiom weightedJustInTime_onTime :
    86 SpecialCase (problem _ (single .sumWZ)) (problem _ (singleRelease .sumWU))
    87
    88axiom 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
    92axiom 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
    96axiom 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
    100axiom 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
    104axiom 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
    108axiom 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
    112end Lax434175.Encodings
    113
    Show ProofShow ProofShow ProofShow ProofShow ProofShow ProofShow ProofShow Proof

    Discussion

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

    Loading discussion…