Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Collections

Scheduling Theory

Machine, flowshop, jobshop and project scheduling: optimality of classic rules, complexity reductions, and approximation guarantees.

70 missions

Missions

1–25 of 70
Open4Completed66All70
🏆Completed
CombinatoricsOperations ResearchTheoretical Computer Science·Captain: mikedeng1

One-Processor Scheduling with Symmetric Earliness and Tardiness Penalties 1: Minimizing the Total Discrepancy from Preferred Times Is NP-CompleteResearch Paper

Scheduling with earliness and tardiness penalties asks for schedules in which a job finishing early is as undesirable as a job finishing late. The model fits production planned for just-in-time delivery, where finished goods held before their due date cost money, and sequences of experiments tied to fixed external events. It departs from classical…

37 thms10 active usersReviewed
🏆Completed
CombinatoricsComplexity TheoryOperations Research+1·Captain: mikedeng1

Scheduling Subject to Resource Constraints: Classification and Complexity I: Unit-Time Chains on Two Identical Machines with One Unit Resource Are Strongly NP-hardResearch Paper

Machine scheduling asks how to assign jobs to machines over time so that a criterion such as the makespan Cmax⁡C_{\max}Cmax​, the time at which the last job completes, is as small as possible. In practice jobs also compete for scarce resources beyond the machines themselves: tools, operators, memory, power. Błażewicz, Lenstra and Rinnooy Kan (DAM 1983) extended the…

46 thms8 active usersReviewed
🏆Completed
Complexity TheoryOperations ResearchOptimization+1·Captain: mikedeng1

Project Scheduling with Time Windows and Scarce Resources IX: Deciding Feasibility with Cumulative Resources Is NP-Complete Even for Acyclic Project NetworksTextbook

Project scheduling with cumulative resources models production and logistics projects in which activities fill and empty storage: an activity withdraws material from an inventory when it starts and deposits its output when it completes, and every inventory must stay between a safety stock and a storage capacity. Neumann, Schwindt and Zimmermann treat this…

29 thms7 active usersReviewed
🏆Completed
CombinatoricsComplexity TheoryGraph Theory+2·Captain: mikedeng1

Scheduling Subject to Resource Constraints: Classification and Complexity II: Unit-Time Jobs on Two Uniform Machines with Unit Resources Are Strongly NP-hardResearch Paper

Machine scheduling asks how to assign jobs to machines over time. In many applications a job also needs additional scarce resources while it runs: a tool, a skilled operator, a memory bank, a channel. Adding such resources can turn a problem with a polynomial algorithm into an NP-hard one. Błażewicz, Lenstra and Rinnooy Kan (DAM 1983) extended the standard…

41 thms7 active usersReviewed
🏆Completed
Complexity TheoryOperations ResearchTheoretical Computer Science·Captain: mikedeng1

Complexity of Machine Scheduling Problems 7: Makespan Reduces to Total Completion Time on Identical Machines with Precedence ConstraintsResearch Paper

Scheduling jobs on parallel machines under precedence constraints is the core model of project and parallel-processing scheduling: a job may start only after its predecessors have finished. Two criteria dominate the literature, the makespan Cmax⁡C_{\max}Cmax​ (when does the last job finish?) and the total completion time ∑jCj\sum_j C_j∑j​Cj​ (how long do jobs wait on…

20 thms6 active usersReviewed
🏆Completed
Complexity TheoryGraph TheoryOperations Research+1·Captain: mikedeng1

Complexity of Machine Scheduling Problems 6: DIRECTED HAMILTON PATH Reduces to No-Wait Flow Shop Makespan and Total Completion TimeResearch Paper

In a no-wait flow shop every job passes through the machines M1,…,MmM_1,\dots,M_mM1​,…,Mm​ in the same order, and once it has started it may never wait between two machines. The constraint comes from processes in which the material changes state if it is left standing, such as hot metal rolling, chemical and food processing, and some pharmaceutical lines; see the survey of…

25 thms6 active usersReviewed
🏆Completed
Complexity TheoryOperations ResearchTheoretical Computer Science·Captain: mikedeng1

Complexity of Machine Scheduling Problems 3: KNAPSACK Reduces to Single-Machine Total Weighted TardinessResearch Paper

Minimizing total weighted tardiness on a single machine, written n∣1∣∣∑wjTjn|1||\sum w_jT_jn∣1∣∣∑wj​Tj​, is one of the basic problems of deterministic scheduling. A job that finishes after its due date is penalized in proportion to its lateness and its weight. Practitioners use this criterion to model penalty clauses and customer priority. In the theory it was a reference…

23 thms6 active usersReviewed
🏆Completed
Complexity TheoryOperations ResearchTheoretical Computer Science·Captain: mikedeng1

Complexity of Machine Scheduling Problems 2: KNAPSACK Reduces to Single-Machine Maximum Lateness, Weighted Number of Late Jobs, and Weighted Completion Time with DeadlinesResearch Paper

Deterministic machine scheduling was one of the first application areas of the theory of NP-completeness. After Cook (1971) and Karp (1972) showed that a large family of combinatorial problems are polynomially equivalent, Brucker, Lenstra and Rinnooy Kan set out to locate the boundary between the polynomially solvable and the NP-complete scheduling…

15 thms6 active usersReviewed
🏆Completed
Complexity TheoryOperations ResearchTheoretical Computer Science·Captain: mikedeng1

Complexity of Machine Scheduling Problems 1: PARTITION Reduces to Makespan and to Weighted Completion Time on Two Identical MachinesResearch Paper

Deterministic machine scheduling asks how to process a set of jobs on a set of machines so that an overall criterion, such as the time at which the last job finishes, is as small as possible. In the early 1970s many such problems had efficient algorithms (Johnson's rule for the two-machine flow shop, Smith's ratio rule for a single machine, Lawler's rule…

15 thms6 active usersReviewed
🏆Completed
CombinatoricsOperations ResearchOptimization·Captain: mikedeng1

Scheduling of Vehicles from a Central Depot to a Number of Delivery Points: The Savings Procedure Always Ends in a Feasible Truck Allocation Whose Mileage Is the Initial Less the Linked SavingsResearch Paper

Delivering goods from one depot to many customers with a fleet of trucks is the vehicle routing problem. Dantzig and Ramser formulated it in 1959 as the "truck dispatching problem" (Management Sci. 6 (1959), doi:10.1287/mnsc.6.1.80). Five years later Clarke and Wright proposed the savings procedure (Oper. Res. 12 (1964), 568–581, doi:10.1287/opre.12.4.568):…

12 thms4 active usersReviewed
🏆Completed
CombinatoricsOperations ResearchOptimization·Captain: mikedeng1

Project Scheduling with Time Windows and Scarce Resources IV: Every Feasible Schedule Obeys a Minimal Delaying Mode of Each Forbidden SetTextbook

Resource-constrained project scheduling with general temporal constraints, written PS∣temp∣Cmax⁡PS|temp|C_{\max}PS∣temp∣Cmax​, asks for start times of the activities of a project that respect minimum and maximum time lags between activities and the capacities of renewable resources (staff, machines, reactors), and that minimize the project duration. Deciding whether a feasible…

8 thms4 active usersReviewed
🏆Completed
Algorithmic Game TheoryMechanism DesignOperations Research+1·Captain: mikedeng1

Algorithmic Mechanism Design I: MinWork Is a Strongly Truthful n-Approximation Mechanism for Task Scheduling on Unrelated MachinesResearch Paper

Algorithmic mechanism design asks for algorithms whose inputs are held by self-interested parties. Each party reports its private data, the algorithm computes an outcome, and payments are arranged so that no party gains by misreporting. Nisan and Ronen introduced the field in Algorithmic Mechanism Design (Games Econ. Behav. 35, 2001). Their running example…

9 thms4 active usersReviewed
🏆Completed
CombinatoricsOperations ResearchOptimization+2·Captain: mikedeng1

Approximation Techniques for Average Completion Time Scheduling I: Best-α on One Machine with Release DatesResearch Paper

Minimizing the average completion time of jobs that arrive over time is one of the basic objectives of machine scheduling: it measures how long, on average, a job waits in the system. On a single machine with release dates and no preemption (written 1∣rj∣∑Cj1|r_j|\sum C_j1∣rj​∣∑Cj​), the problem is strongly NP-hard, so research has focused on approximation algorithms whose…

9 thms4 active usersReviewed
🏆Completed
CombinatoricsOperations ResearchProbability+1·Captain: mikedeng1

Packet Routing and Job-Shop Scheduling in O(Congestion + Dilation) Steps: Edge-Simple Paths with Congestion c and Dilation d Admit an O(c + d)-Step Schedule with Constant-Size QueuesResearch Paper

In a store-and-forward network, messages are cut into packets that travel from node to node along wires, one wire per time step, and wait in buffers between moves. Routing such traffic splits into two problems: choosing a path for each packet, and scheduling the packets along their paths, deciding at every step which packets move and which wait. Leighton,…

10 thms3 active usersReviewed
🏆Completed
CombinatoricsOperations ResearchTheoretical Computer Science·Captain: mikedeng1

Flowshop and Jobshop Schedules: Complexity and Approximation 2: The 3-Partition Flow Shop on Three Machines Has a Preemptive Schedule of Finish Time 2tB Iff a 3-Partition ExistsResearch Paper

A flow shop is the simplest multi-stage production model: every job passes through the same machines in the same order, and the question is how to sequence the work so that everything is finished as early as possible. Gonzalez and Sahni's 1978 paper in Operations Research settled the computational complexity of the preemptive version of this problem, in…

8 thms3 active usersReviewed
🏆Completed
CombinatoricsOperations ResearchOptimization·Captain: mikedeng1

Optimization and Approximation in Deterministic Sequencing and Scheduling: A Survey 2: The Optimal Preemptive Open Shop Makespan Equals the Largest Machine Load or Job LengthResearch Paper

Open shops model production and service systems in which every job must visit every machine, but the order of the visits is free: a car that needs an inspection, a wash and a tyre change, a patient who needs several tests, a student who sits several exams. The survey of Graham, Lawler, Lenstra and Rinnooy Kan (Ann. Discrete Math. 5, 1979) fixed the…

9 thms3 active usersReviewed
🏆Completed
CombinatoricsOperations ResearchOptimization·Captain: mikedeng1

Optimization and Approximation in Deterministic Sequencing and Scheduling: A Survey 1: The Optimal Two-Machine Open Shop Makespan Is max{T₁, T₂, maxⱼ(aⱼ + bⱼ)}Research Paper

Shop scheduling asks how to sequence jobs that each need processing on several machines. In an open shop, a job's operations may be executed in any order, as in testing stations, repair bays, or classroom and examination timetables, where the order in which a candidate visits the stations is irrelevant. The objective studied here is the makespan Cmax⁡C_{\max}Cmax​,…

9 thms3 active usersReviewed
🏆Completed
CombinatoricsOperations ResearchTheoretical Computer Science·Captain: mikedeng1

On the Approximability of Single-Machine Scheduling with Precedence Constraints 2: Every Convex Bipartite Order Has a Realizer of Size 3Research Paper

The single-machine scheduling problem 1∣prec∣∑wjCj1|\mathrm{prec}|\sum w_j C_j1∣prec∣∑wj​Cj​ asks for an order in which to process nnn jobs, each with a processing time and a weight, on one machine, respecting a partial order of precedence constraints, so that the weighted sum of completion times is as small as possible. It is NP-hard, and the best known approximation ratio for…

7 thms3 active usersReviewed
🏆Completed
CombinatoricsGraph TheoryTheoretical Computer Science·Captain: mikedeng1

On the Approximability of Single-Machine Scheduling with Precedence Constraints 3: The Incomparable-Pairs Graphs of Canonical Interval Orders Have Unbounded Chromatic NumberResearch Paper

Single-machine scheduling with precedence constraints asks for an order in which one machine processes jobs while respecting prescribed comparisons between them. For the objective of minimizing total weighted completion time, the structure of the precedence order can influence the quality of approximation algorithms. Ambühl, Mastrolilli, Mutsanas, and…

7 thms3 active usersReviewed
🏆Completed
CombinatoricsGraph TheoryOperations Research+1·Captain: mikedeng1

On the Approximability of Single-Machine Scheduling with Precedence Constraints 1: A k-Fold Realizer of Size t Yields a Vertex Cover of Expected Weight at Most (2 − 2/(t/k)) Times OptimalResearch Paper

Single-machine scheduling with precedence constraints, written 1∣prec∣∑wjCj1|\mathrm{prec}|\sum w_jC_j1∣prec∣∑wj​Cj​ in the notation of Graham et al., asks for an order of nnn weighted jobs on one machine that respects a given partial order and minimizes the weighted sum of completion times. The problem is strongly NP-hard (Lawler 1978; Lenstra and Rinnooy Kan 1978), and closing its…

10 thms3 active usersReviewed
Control TheoryOperations ResearchProbability+1·Captain: mikedeng1

Scheduling a Multi Class Queue with Many Exponential Servers: Asymptotic Optimality in Heavy Traffic: The HJB-Based Preemptive Policy Is Asymptotically Optimal Among Work-Conserving PoliciesResearch Paper

Large call centers route several types of customers to a common pool of agents. When the pool is large and highly utilized, the relevant asymptotic regime is the quality-and-efficiency-driven (QED) or Halfin–Whitt regime (Halfin & Whitt 1981). The number of servers nnn grows while the offered load stays within O(n)O(\sqrt n)O(n​) of nnn. Waiting is then neither…

18 thms3 active usersReviewed
🏆Completed
Graph TheoryLinear OptimizationOperations Research+1·Captain: mikedeng1

Project Scheduling with Time Windows and Scarce Resources VIII: A Vertex Schedule Maximizes the Net Present Value iff Its Spanning-Tree Subprojects Have the Right SignsTextbook

Long-running projects such as construction, plant engineering or software development involve payments to and from the contractor at many points in time: disbursements when activities are carried out, progress payments when milestones are reached. When the planning horizon is long, money received later is worth less, and the natural financial objective is…

9 thms3 active usersReviewed
🏆Completed
CombinatoricsOperations ResearchOptimization+1·Captain: mikedeng1

Online Scheduling of a Single Machine to Minimize Total Weighted Completion Time: Delayed SWPT Has Competitive Ratio 2Research Paper

A single machine must process nnn jobs that arrive over time. Job jjj is released at time rjr_jrj​, needs pjp_jpj​ units of uninterrupted processing, and has weight wj>0w_j > 0wj​>0; the goal is to minimize the total weighted completion time ∑jwjCj\sum_j w_j C_j∑j​wj​Cj​. Offline, with all release dates equal to zero, Smith's rule (sequence by nondecreasing pj/wjp_j/w_jpj​/wj​) is optimal (Smith 1956);…

11 thms3 active usersReviewed
🏆Completed
CombinatoricsGraph TheoryOperations Research+1·Captain: mikedeng1

Project Scheduling with Time Windows and Scarce Resources II: A Time-Feasible Strict Order Is Feasible iff It Breaks Up Every Minimal Forbidden SetTextbook

Resource-constrained project scheduling asks for start times of the activities of a project so that prescribed time lags between activities are respected and, at every moment, the activities in progress do not require more of any renewable resource (staff, machines, reactors) than is available. When the time lags include maximum time lags (deadlines…

9 thms3 active usersReviewed
🏆Completed
Graph TheoryLinear OptimizationOperations Research+1·Captain: mikedeng1

Project Scheduling with Time Windows and Scarce Resources I: A Time-Feasible Schedule Exists iff the Project Network Has No Cycle of Positive LengthTextbook

Project scheduling assigns start times to the activities of a project subject to constraints between them. The classical critical path method (CPM) of Kelley and Walker (1959) and the program evaluation and review technique (PERT) allow only minimum time lags: activity jjj may start no earlier than a given time after activity iii starts. Practice also needs maxi…

8 thms3 active usersReviewed
PreviousPage 1 of 3Next

Top contributors

RankContributorAccepted solutionsSubmitted problems
1MRmrfancypants2090
2RYryanshin680
3NINickrobbins95585
4ARarexychen5396
5TItianyipeng238
6KMkmehltretter822110
7SCShuze Chen126
8SHshivm100
9VEvebis60
10MOmoona3k30

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me