Scheduling problems assembled from constraint modules
No public endorsements yet.
Loading review…
Sign in with ORCIDAbstract
Scheduling problems in the three-field notation 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 within instructions plus the length of the input; is strongly NP-hard, and para-NP-hard in and in the number of distinct processing times; is fixed-parameter tractable in and strongly W[1]-hard in ; and is strongly NP-hard and strongly W[2]-hard in , while is solved within , and instructions, the total weight.
Concepts
- thm✓
Assembly - thm✓
BatchFamily - thm✓
Batching - thm✓
BatchingZeroSetup - thm✓
BatchProblems - thm✓
Bounded - thm✓
CommunicationDelays - thm✓
ComplexityClasses - thm✓
Counts - thm✓
Deadlines - thm✓
DeadlineSteps - thm✓
Domination - thm✓
Encodings - thm✓
EncodingsEligibility - thm✓
ForbiddenTimes - thm✓
HighMultiplicity - thm✓
Interruption - thm✓
IsemLink - thm✓
IsemStandard - thm✓
IsemStrong - thm✓
JitFlowShop - thm✓
JitFlowShopStandard - thm✓
JitFlowShopTimes - thm✓
JitFlowShopW2 - thm✓
JitHardness - thm✓
MachineSets - thm✓
McNaughton - thm✓
Nonpreemptive - thm✓
Objectives - thm✓
Online - thm✓
Operations - thm✓
OperationsFamily - thm✓
ParallelFamily - thm✓
ParallelMachines - thm✓
ParallelProblems - thm✓
Parameters - thm✓
Precedence - thm✓
PrecedenceReversal - thm✓
PreemptionUseless - thm✓
Preemptive - thm✓
PreemptiveShopProblems - thm✓
PreemptiveShops - thm✓
Problems - thm✓
Propagation - thm✓
PropagationParameters - thm✓
ReleaseDates - thm✓
Restarts - thm✓
ResultTransfer - thm✓
Sanity - thm✓
SanityParams - thm✓
Servers - thm✓
ShopExtras - thm✓
ShopFamily - thm✓
ShopProblems - thm✓
Shops - thm✓
StrongHardness - thm✓
ThresholdParams - thm✓
Thresholds - thm✓
ThresholdWords - thm✓
TimeReversal - thm✓
Transportation - thm✓
WordProblems - thm✓
ZooOpen - thm✓
ZooOpenParams - thm✓
ZooParallel - thm✓
ZooParallelBatching - thm✓
ZooParameters - thm✓
ZooPreemptive - thm✓
ZooPreemptiveShops - thm✓
ZooRestarts - thm✓
ZooSerialBatching - thm✓
ZooShops
- def
FineGrained - def
Kernels - def
MachineCovering - def
Modules - def
Rejection - def
ResultParameters - def
Results - def
StandardReading - def
Wrappers - def
ZooParallelBatchingResults - def
ZooParallelResults - def
ZooPreemptiveResults - def
ZooPreemptiveShopsResults - def
ZooRestartsResults - def
ZooSerialBatchingResults - def
ZooShopsResults - def
ZooStandaloneResults
- thm✓
Lax391470.Lemma1 - thm✓
Lax391470.Lemma2 - thm✓
Lax391470.Theorem1 - thm✓
Lax496464.HittingSetHardness - thm✓
Lax496464.Theorem1 - thm✓
Lax496464.Theorem2 - thm✓
Lax496464.Theorem3 - thm✓
Lax496464.WH_A3_ReductionCalculus - thm✓
Lax496464.WH_A4_MachineFacts - thm✓
Lax496464.WH_A5_Bridges - thm✓
Lax496464.WH_A6_ComputableBounds - thm✓
Lax496464.WH_B5_HierarchyFacts - thm✓
Lax496464.WH_D12_MulticolouredClique - thm✓
Lax496464.WH_E3_DominatingSet - thm✓
Lax759944.RamToTuringGenericTime - thm✓
Lax759944.TuringRamPolytimeEquivalence - thm✓
Lax888481.Theorem2 - thm✓
Lax888481.Theorem3 - def✓
Lax391470.SatConstruction - def✓
Lax391470.StackedConstruction - lem✓
Lax429075.SATHard - def✓
Lax434930.Certificates - def✓
Lax888481.Construction1 - def✓
Lax888481.Construction2 - def✓
Lax888481.SatVariant - def✓
Lax888481.SchedulingProblems
- def
Lax271696.GraphEncoding - def
Lax271696.VertexCover - def
Lax391470.AuxiliaryProblem - def
Lax391470.BinaryEncoding - def
Lax391470.Scheduling - def
Lax429075.CNF - def
Lax429075.Encoding - def
Lax429075.Reductions - def
Lax429075.Satisfiability - def
Lax434930.NondeterministicPolynomialTime - def
Lax434930.PolynomialTime - def
Lax496464.BinaryEncoding - def
Lax496464.Construction - def
Lax496464.DynamicProgram - def
Lax496464.EstOrder - def
Lax496464.FlowShop - def
Lax496464.HittingSet - def
Lax496464.HittingSetFromSat - def
Lax496464.NPHardness - def
Lax496464.ParameterizedComplexity - def
Lax496464.Problems - def
Lax496464.WH_A1_FptTime - def
Lax496464.WH_A2_FptReductions - def
Lax496464.WH_B1_Structures - def
Lax496464.WH_B2_FirstOrder - def
Lax496464.WH_B3_LogicProblems - def
Lax496464.WH_B4_Hierarchies - def
Lax496464.WH_C1_GraphProblems - def
Lax496464.WH_C2_HittingSet - def
Lax496464.WH_F3_NPHard - def
Lax496464.WordEncoding - def
Lax759944.BinaryWordEncoding - def
Lax759944.RamPolytime - def
Lax759944.TuringPolytime - def
Lax808846.Ram - def
Lax808846.RamComputes - def
Lax888481.BinaryEncoding - def
Lax888481.Exact34Encoding - def
Lax888481.InstanceEncoding - def
Lax888481.MulticolouredClique - def
Lax888481.NPHardness - def
Lax888481.ParameterizedComplexity - def
Lax888481.PolynomialReduction - def
Lax888481.Scheduling
Concept map
Proofs
Proof networkview on GitHub
Proof list
-
⊢
Lax434175Proofs.BatchingZeroSetup.reducible_of_reducesToBatching -
no assumptions
thm✓Lax434175.Counts -
⊢
Lax434175Proofs.EncodingsEligibilityWords.stronglyNPHard_makespan -
⊢
Lax434175Proofs.EncodingsEligibilityWords.stronglyNPHard_sumC -
⊢
Lax434175Proofs.EncodingsEligibilityWords.stronglyNPHard_sumWC -
⊢
Lax434175Proofs.EncodingsEligibilityWords.stronglyNPHard_sumWZ -
⊢
Lax434175Proofs.EncodingsFlexible.identical_flexibleFlow_weighted -
⊢
Lax434175Proofs.HighMultiplicityTransfer.isFPT_numP_makespan -
⊢
Lax434175Proofs.McNaughton.preemption_useless_except_interruption -
⊢
Lax434175Proofs.OperationsFamily.reducible_of_reducesThroughFlow -
⊢
Lax434175Proofs.PadReduction.byMachines_fptReduces_jitByMachines -
⊢
Lax434175Proofs.ParallelFamily.reducible_of_reducesThroughFlow -
⊢
Lax434175Proofs.ParallelProblems.reducible_of_reducesThroughFlow -
⊢
Lax434175Proofs.PreemptionUseless.reducible_of_reducesByPreemption -
⊢
Lax434175Proofs.PreemptiveShopProblems.reducible_of_reduces -
⊢
Lax434175Proofs.Propagation.decidesWithinWide_restrict_down -
⊢
Lax434175Proofs.ResultTransfer.decidesWithinWide_of_decidesWithin -
⊢
Lax434175Proofs.TimeReversal.reducible_of_reducesByReversal -
⊢
Lax434175Proofs.ZooParallelBatching.thresholdReductions_hold -
⊢
Lax434175Proofs.ZooPreemptiveShops.thresholdReductions_hold
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
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.
0 comments