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

Scheduling problems assembled from constraint modules

lax-434175·formalized by Yuval Itzhaki @yuvalyitz·created ·GitHub @ca2629f·Lean v4.33.0 epoch · mathlib db584cd6d46c

Loading review…

Sign in with ORCID

Community review

Flags

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

No flags have been submitted.

    Community review

    Flag this submission

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

    Abstract

    Scheduling problems in the three-field notation α∣β∣γ\alpha \mid \beta \mid \gamma are formalized as assemblies of independent fields, so that every problem is a problem in its own right and the relations between problems follow from relations between the values of single fields.

    A kernel fixes what a schedule is. A field over a kernel is a restriction of its instances, a constraint module that adds data and a condition on schedules, or an objective. A specification chooses one value in every field and determines a problem. If one specification is field by field a special case of another, the data maps of the fields combine into an embedding of the first problem into the second, which is sound whenever every field is. Two families of fields cover the problems: one in which every job is a sequence of operations, for parallel machines and shops with and without preemption, and one for serial and parallel batching. Their fields cover machine environments, processing times, numbers of machines and jobs, machine sets, release dates, deadlines, precedence constraints in sixteen classes with time lags, communication and transportation delays, a transport robot, a server with setup times, batch setups, no-wait, no-idle, forbidden times, high multiplicity, and sixteen objectives. Maximizing the smallest machine load and scheduling with rejection are formalized as problems of their own.

    The construction is carried out for The Scheduling Zoo. All 747 of its problems are specifications. Three of the 614 relations in its data come from two rules of its notation that do not hold; with the two rules corrected the data has 612 relations, and all are proved: 566 as special cases and 34 as reductions of decision versions, each checked by evaluation, and 12 encodings that change the instance, proved one by one. The general theorems also relate pairs of problems of the zoo that its data does not relate.

    Instances and schedules are read as words of natural numbers, every field written through its view, the meaning its constraints use, so that the word of an instance of a special case is also a word of its image. Against this reading, 950 results of the zoo are stated in terms of running times on the word RAM, P and NP-hardness, fixed-parameter tractability and W[t]-hardness, as defined in registered formalizations, and the open questions of the zoo are posed as pairs of competing propositions. Proved transfer theorems carry results along the relations: algorithms go down along special cases and hardness goes up, and hardness also goes along the threshold steps between objectives, along the encodings of machine sets, and from the standard encoding to high multiplicity. Strong hardness, with numbers polynomial in the length of the input, is distinguished from plain hardness throughout. Proved from the words up, building on registered formalizations: Smith's rule decides 1∣∣∑wjCj1 \mid\mid \sum w_jC_j within O(nlog⁡n)O(n \log n) instructions plus the length of the input; 1∣rj∣Lmax⁡1 \mid r_j \mid L_{\max} is strongly NP-hard, and para-NP-hard in pmax⁡p_{\max} and in the number of distinct processing times; P∣Mj∣∑wjZjP \mid M_j \mid \sum w_jZ_j is fixed-parameter tractable in m+pmax⁡m + p_{\max} and strongly W[1]-hard in mm; and FF(1,m)∣∣∑ZjFF(1,m) \mid\mid \sum Z_j is strongly NP-hard and strongly W[2]-hard in mm, while FF(1,m)∣∣∑wjZjFF(1,m) \mid\mid \sum w_jZ_j is solved within O(Wnm)O(W n^m), O(Wmqmax⁡n)O(W m^{q_{\max}} n) and O(W2χn)O(W 2^{\chi} n) instructions, WW the total weight.

    Concepts

    Concept map
    133 concepts
    100%
    Compressed sparse row encoding of a graphA graph with a parameter appendedConjunctive normal formBinary encoding of CNF formulasPolynomial many-one reductions andNP-completenessThe satisfiability language and verifierAssembling problems from fieldsOne family for serial and parallel batchingBatching problems in three-field notationBatch scheduling on a single machineScheduling on one machine as batchingProblems with bounds on parametersCommunication delaysComplexity classes along special casesBounds on the number of machines and jobsMaximum lateness against deadlinesDeadlinesResults between parameters of one problemRelations of the Scheduling Zoo that need anencodingMachine sets encoded by long processingtimesFine-grained hypotheses and reductions onshort wordsForbidden times and input encodingsStandard words into high-multiplicity wordsInterruption as a field of parallel-machineschedulingInterval scheduling with eligible machine setsas a zoo problemHardness of P | M_j | Σ w_j Z_j under thestandard readingP | M_j | Σ w_j Z_j is strongly W[1]-hardfor the number of machinesJust-in-time flow shops of lax-496464 as zooinstancesFF(1,m)||ΣZj is strongly NP-hard under thestandard readingThe running times of FF(1,m)||ΣwjZjFF(1,m)||ΣZj is strongly W[2]-hard for thenumber of machinesHardness of P | M_j | Σ w_j Z_jScheduling kernelsMaximizing the minimum machine loadMachine sets and multiprocessor tasksPreemption does not help the total weightedcompletion timeConstraint modules and objectivesNon-preemptive scheduling on parallelmachinesCompletion-time objectivesOnline scheduling as a gameScheduling with operationsOne family for parallel machines and shopsOne family for parallel machines with andwithout preemptionParallel machinesProblems on parallel machines in three-fieldnotationParameters along embeddingsPrecedence constraints and time lagsReversing precedence constraintsPreemption does not help on a singlemachinePreemptive scheduling on parallel machinesPreemptive shop problems in three-fieldnotationPreemptive shop schedulingOptimization problems and embeddingsResults along special casesParameters along special casesSingle-machine scheduling with rejectionRelease datesPreemption with restarts on parallelmachinesParameters of the zoo's resultsFrom exact running times to complexityclassesThe kinds of results on scheduling problemsTwo tests from the words up: NP-hardness of1|r_j|L_max and Smith's rule1|r_j|L_max is para-NP-hard for the largestand the number of processing timesA single server with setup timesNo-idle shops and batch setup timesOne family for shops with and withoutpreemptionShop problems in three-field notationShop schedulingThe standard reading of scheduling instancesand schedulesStrong and plain hardnessPara-NP-hardness along the steps betweenobjectivesThe steps between objectives on wordsThreshold reductions between objectivesTime reversalTransportation delays and a transport robotScheduling problems as parameterizedproblems on wordsAt most k scheduled jobs, and prescribedmachine loadsOpen questions of The Scheduling ZooOpen parameters of The Scheduling ZooThe Scheduling Zoo, non-preemptiveproblems on parallel machinesThe Scheduling Zoo, parallel batchingproblemsResults of The Scheduling Zoo, parallelbatching problemsResults of The Scheduling Zoo,non-preemptive problems on parallelmachinesParameters of scheduling problemsThe Scheduling Zoo, preemptive problems onparallel machinesResults of The Scheduling Zoo, preemptiveproblems on parallel machinesThe Scheduling Zoo, preemptive shopproblemsResults of The Scheduling Zoo, preemptiveshop problemsThe Scheduling Zoo, problems with restartson parallel machinesResults of The Scheduling Zoo, problemswith restarts on parallel machinesThe Scheduling Zoo, serial batchingproblemsResults of The Scheduling Zoo, serialbatching problemsThe Scheduling Zoo, shop problemsResults of The Scheduling Zoo, shopproblemsResults of The Scheduling Zoo, problemsoutside the familiesBinary encoding of an input and a certificateThe complexity class NPThe complexity class PBinary Encoding of an InstanceThe Construction of Section 8Just-in-Time Scheduling in a Two-StageFlexible Flow ShopHitting SetNP-Hardness, and Strong NP-Hardness, of aScheduling ProblemParameterized Problems andFPT-Reductions on a Word RAMTheorem 1Fixed-Parameter Time on the Word RAMFPT-Reductions, FPT, Hardness andCompletenessFinite Relational StructuresFirst-Order Formulas and the Classes Σ_tand Π_tModel Checking and Weighted FaginDefinabilityThe W-Hierarchy and the A-HierarchyClique, Independent Set and Dominating SetHitting SetMulticoloured Clique Is W[1]-CompleteDominating Set Is W[2]-CompleteNP-Hardness of a Problem on Words ofNumbersBinary encoding of finite wordsPolynomial-time computation by a wordRAMPolynomial-time computation by a TuringmachineThe word RAMComputing a function within a time boundBinary Encoding of a Scheduling InstanceWord Encoding of a (3,4) FormulaWord Encoding of a Scheduling InstanceMulticoloured CliqueNP-Hardness of a Scheduling Problem, andon a Class of InstancesParameterized Problems andFPT-Reductions on a Word RAMPolynomial-Time Many-One Reductions onthe Word RAM(3,4)-SatisfiabilityInterval Scheduling with Eligible MachineSetsThe Scheduling Problems, ParameterizedScheduling Every Job Is Hard for ConstantProcessing Times and Unit WeightsInterval Scheduling Is Fixed-ParameterTractable for the Machines and the LargestProcessing Time
    Proven claimDefinitionThis submissionOther submissionA → B: B builds on ADescendants are omitted for concepts with more than 10 descendants.

    Proofs

    Proof networkview on GitHub

    100%
    Lax345332.ConstructionLax345332.ThreeFourSatLax391470.Lemma1Lax391470.Lemma2Lax391470.SatConstructionLax391470.StackedConstructionLax391470.Theorem1Lax429075.CircuitMachineLax429075.EncodingCorrectLax429075.GateCorrectLax429075.SATEncodingLax429075.SATHardLax429075.TseitinCorrectAssemblyBatchFamilyBatchProblemsBatchingBatchingZeroSetupBoundedCommunicationDelaysComplexityClassesCountsDeadlineStepsDeadlinesDominationEncodingsEncodingsEligibilityForbiddenTimesHighMultiplicityInterruptionIsemLinkIsemStandardIsemStrongJitFlowShopJitFlowShopStandardJitFlowShopTimesJitFlowShopW2JitHardnessMachineSetsMcNaughtonNonpreemptiveObjectivesOnlineOperationsOperationsFamilyParallelFamilyParallelMachinesParallelProblemsParametersPrecedencePrecedenceReversalPreemptionUselessPreemptivePreemptiveShopProblemsPreemptiveShopsProblemsPropagationPropagationParametersReleaseDatesRestartsResultTransferSanitySanityParamsServersShopExtrasShopFamilyShopProblemsShopsStrongHardnessThresholdParamsThresholdWordsThresholdsTimeReversalTransportationWordProblemsZooOpenZooOpenParamsZooParallelZooParallelBatchingZooParametersZooPreemptiveZooPreemptiveShopsZooRestartsZooSerialBatchingZooShopsLax434930.CertificatesLax434930.FiniteStackEquivalenceLax434930.ModelEquivalenceLax496464.HittingSetHardnessLax496464.Theorem1Lax496464.Theorem2Lax496464.Theorem3Lax496464.WH_A3_ReductionCalculusLax496464.WH_A4_MachineFactsLax496464.WH_A5_BridgesLax496464.WH_A6_ComputableBoundsLax496464.WH_B5_HierarchyFactsLax496464.WH_D01_CliqueInW1Lax496464.WH_D02_CliqueInA1Lax496464.WH_D03_NegationEliminationLax496464.WH_D04_IncidenceStructureLax496464.WH_D05_BinaryToCliqueLax496464.WH_D06_CliqueA1CompleteLax496464.WH_D07_DefinabilityToWSatLax496464.WH_D08_WSatInA1Lax496464.WH_D09_W1EqA1Lax496464.WH_D10_CliqueW1CompleteLax496464.WH_D12_MulticolouredCliqueLax496464.WH_E1_HittingSetInW2Lax496464.WH_E2_HittingSetW2CompleteLax496464.WH_E3_DominatingSetLax759944.RamToTuringGenericTimeLax759944.TuringRamPolytimeEquivalenceLax888481.Construction1Lax888481.Construction2Lax888481.SatVariantLax888481.Theorem2Lax888481.Theorem3
    premise files concept fileProven claimClaim from this submission / another submissionAll proofs of one concept — hover for individual statements and proofsCycle between concept files
    Proof list

    Lean sources for these proofs: proofs/ on GitHub

    Proof code is not displayed; the archive records each proof's checked relationship between claims.

    Related submissions

    Submission map

    100%
    This submissionOther submissionA → B: B's concepts build on AA → B: only B's proofs build on A

    Cite this

    This is only the formalizers. The authors of the formalized results may be different (see References).

    @misc{lax-434175,
      author = {Yuval Itzhaki},
      title = {Scheduling problems assembled from constraint modules},
      year = {2026},
      howpublished = {Lax Archive, lax-434175},
      url = {https://laxarchive.org/lax-434175/},
      note = {draft},
    }

    Discussion

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

    Loading discussion…