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

26–50 of 70
Open4Completed66All70
Algorithmic Game TheoryMechanism DesignOperations Research+1·Captain: mikedeng1

Algorithmic Mechanism Design VIII: A Truthful Approximation Scheme for Bounded Scheduling with VerificationResearch Paper

Algorithmic mechanism design asks for algorithms whose inputs are held by self-interested agents: the designer can pay the agents, and must choose payments so that each agent's own interest leads it to reveal what the algorithm needs. Nisan and Ronen introduced the framework with task scheduling on unrelated machines as the running example (Nisan–Ronen 2001)…

16 thms3 active users
🏆Completed
Algorithmic Game TheoryMechanism DesignOperations Research+1·Captain: mikedeng1

Algorithmic Mechanism Design IV: No Local Truthful Mechanism Achieves a c-Approximation for Task Scheduling for Any c < nResearch Paper

Nisan and Ronen's Algorithmic Mechanism Design (Games and Economic Behavior 35, 2001) asks how well a computational task can be carried out when its inputs are held by self-interested agents who may lie about them. Their test case is scheduling on unrelated machines: tasks must be assigned to agents (machines), each agent privately knows how long it needs…

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

Algorithmic Mechanism Design II: A Lower Bound for Truthful Task SchedulingResearch Paper

Algorithms deployed on the Internet often take their inputs from parties who own them and who may lie when lying pays. Nisan and Ronen's Algorithmic Mechanism Design (Games and Economic Behavior 35, 2001) proposed studying optimization problems in this setting: the algorithm designer may hand out payments, and must guarantee that the intended output is…

11 thms3 active usersReviewed
🏆Completed
Operations ResearchOptimizationProbability+1·Captain: mikedeng1

Single Machine Scheduling with Release Dates III: The Random Per-Job α-Schedule with a Truncated Exponential DensityResearch Paper

Scheduling jobs with release dates on one machine to minimize the total weighted completion time, written 1∣rj∣∑wjCj1|r_j|\sum w_jC_j1∣rj​∣∑wj​Cj​, is strongly NP-hard even with unit weights (Lenstra, Rinnooy Kan & Brucker, 1977). It is a basic model of scheduling theory and a standard testbed for approximation algorithms built on linear programming relaxations. Several LP…

21 thms3 active usersReviewed
🏆Completed
Operations ResearchOptimizationProbability+1·Captain: mikedeng1

Single Machine Scheduling with Release Dates II: The Random α-Schedule with a Truncated Exponential DensityResearch Paper

Minimizing the total weighted completion time ∑jwjCj\sum_j w_j C_j∑j​wj​Cj​ of jobs with release dates on a single machine, written 1 ∣ rj ∣ ∑wjCj1\,|\,r_j\,|\,\sum w_j C_j1∣rj​∣∑wj​Cj​ in scheduling notation, is strongly NP-hard. It is one of the basic models of machine scheduling, and it has served as a test case for a general technique in approximation algorithms: solve a linear programming…

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

Santa Claus Schedules Jobs on Unrelated Machines: The Configuration LP Has Integrality Gap at Most 33/17Research Paper

Scheduling jobs on unrelated machines so as to minimize the makespan (the time at which the last machine finishes) is one of the central problems of approximation algorithms. For the general problem, Lenstra, Shmoys and Tardos (1990) gave a 2-approximation and showed that no polynomial-time algorithm achieves a factor below 3/23/23/2 unless P = NP; closing the…

13 thms3 active usersReviewed
🏆Completed
Markov ChainOperations ResearchStochastic Systems·Captain: mikedeng1

Jobshop-Like Queueing Systems: The Equilibrium Distribution with State-Dependent Arrival and Service RatesResearch Paper

A jobshop is a factory in which each job visits a sequence of machine groups, the sequence differing from job to job. J. R. Jackson's 1963 paper Jobshop-Like Queueing Systems (Management Science 10(1), 131–142) models such a shop as a network of queues and computes its long-run distribution of queue lengths in closed form. It generalizes his 1957 paper Netwo…

6 thms3 active usersReviewed
🏆Completed
Graph TheoryOperations Research·Captain: mikedeng1

Critical-Path Planning and Scheduling I: Critical Jobs Occur Only When the Completion Time Is the Earliest, and Then Form a Path from Origin to TerminusResearch Paper

The Critical-Path Method (CPM) was introduced by J. E. Kelley, Jr. (Remington Rand) and M. R. Walker (du Pont) in Critical-Path Planning and Scheduling (Proc. Eastern Joint Computer Conference, 1959, pp. 160–173, doi:10.1145/1460299.1460318). Together with PERT, developed at the same time for the Polaris programme, it became the standard way to plan and…

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

Approximation Techniques for Average Completion Time Scheduling IV: List Scheduling from an Optimal One-Machine Schedule Is a 2-Approximation for In-TreesResearch Paper

Minimizing the sum of weighted completion times of jobs on identical parallel machines is one of the basic objectives of machine scheduling: it measures the average time a job spends in the system, weighted by its importance. When the jobs are subject to precedence constraints (a job may start only after certain other jobs have finished), the problem is…

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

Approximation Techniques for Average Completion Time Scheduling III: From One Machine to Many with Delay ListResearch Paper

Minimizing the sum of weighted completion times ∑jwjCj\sum_j w_jC_j∑j​wj​Cj​ is one of the standard objectives of machine scheduling: it measures the average time a job spends in the system, weighted by its importance. With release dates or precedence constraints the problem is NP-hard already on one machine, and on mmm identical parallel machines it is harder still, so the…

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

Approximation Techniques for Average Completion Time Scheduling II: A 2.83-Approximation for Parallel Machines with Release DatesResearch Paper

Minimizing the average completion time of jobs that arrive over time is a basic objective in machine scheduling. It measures how long a job spends in the system on average. With several identical machines, release dates and no preemption (written P∣rj∣∑CjP|r_j|\sum C_jP∣rj​∣∑Cj​), the problem is strongly NP-hard already on one machine. Research has therefore looked for…

11 thms3 active usersReviewed
🏆Completed
Dynamic ProgrammingOperations ResearchOptimization·Captain: mikedeng1

Efficient Algorithms for Scheduling Semiconductor Burn-In Operations 2: Dynamic Program DP2 Finds a Minimum-Makespan On-Time Batch Schedule When Processing Times and Due Dates Are AgreeableResearch Paper

In semiconductor manufacturing, finished chips go through burn-in: they are loaded on boards and held in an oven at high temperature to expose early failures. An oven holds a bounded number of boards, a load cannot be interrupted once started, and a chip may stay in the oven longer than its specified burn-in time but not shorter. Lee, Uzsoy and Martin-Vega (…

7 thms2 active usersReviewed
🏆Completed
CombinatoricsOperations ResearchOptimization·Captain: mikedeng1

Application of the Branch and Bound Technique to Some Flow-Shop Scheduling Problems 1: Branch and Bound with the Three-Machine Lower Bound Finds a Minimum-Makespan SequenceResearch Paper

In a flow shop every job passes through the same machines in the same order. Choosing the order in which jobs enter the shop so that the last job finishes as early as possible (minimizing the makespan) is one of the oldest problems of scheduling theory. For two machines Johnson (1954) gave an exact sorting rule; for three machines his rule is exact only in…

13 thms2 active usersReviewed
🏆Completed
Control TheoryDynamical SystemsOperations Research·Captain: mikedeng1

Dynamic Instabilities and Stabilization Methods in Distributed Real-Time Scheduling of Manufacturing Systems 1: Clearing Policies Are Unstable on a Re-Entrant Two-Machine Line, Even Without Set-UpsResearch Paper

A flexible manufacturing system is a set of machines through which parts of several types travel along fixed routes; each machine serves several buffers and must pay a set-up time whenever it switches from one buffer to another. Real-time scheduling decides, as the system evolves, which buffer each machine works on. Perkins and Kumar (IEEE Trans. Automat.…

10 thms2 active usersReviewed
🏆Completed
Operations ResearchTheoretical Computer Science·Captain: mikedeng1

Flowshop and Jobshop Schedules: Complexity and Approximation 6: Concatenating Optimal Schedules of Processor Pairs Gives Finish Time within ⌈m/2⌉ Times the OptimumResearch Paper

A flow shop is the simplest model of a production line: every job passes through the same sequence of machines in the same order. Minimizing the time at which the last job leaves the last machine (the finish time, or makespan) is easy for two machines, where Johnson's rule gives an optimal schedule in time O(nlog⁡n)O(n\log n)O(nlogn) (Johnson 1954), and NP-hard from three…

7 thms2 active usersReviewed
🏆Completed
Operations ResearchTheoretical Computer Science·Captain: mikedeng1

Flowshop and Jobshop Schedules: Complexity and Approximation 5: Sequencing Jobs by Shortest Total Processing Time Gives Mean Flow Time within m Times the OptimumResearch Paper

Flow shops and job shops are the basic models of multi-stage production: every job passes through several machines, and each machine handles one task at a time. Gonzalez and Sahni (Operations Research 26(1), 1978) showed that minimizing the finish time of such shops is NP-complete even with preemption, and then asked how well simple heuristics do. One of…

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

Flowshop and Jobshop Schedules: Complexity and Approximation 4: The 3-Partition Job Shop on Two Machines Has a Schedule of Finish Time 2tB, Preemptive or Not, Iff a 3-Partition ExistsResearch Paper

In a job shop, each job has an ordered list of tasks, and each task must use a specified machine. A production planner may be able to interrupt a task and resume it later, yet still be unable to find a short schedule efficiently. Gonzalez and Sahni studied how the ability to preempt changes the difficulty of minimizing the time at which all jobs are…

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

Flowshop and Jobshop Schedules: Complexity and Approximation 1: The Partition Flow Shop on Three Machines Has a Schedule of Finish Time 2T, Preemptive or Not, Iff a Partition ExistsResearch Paper

Shop scheduling asks how to process a set of jobs, each a sequence of tasks on prescribed machines, so that all work is completed as early as possible. The flow shop, in which every job visits the machines in the same order, is the most studied of these models in operations research. For two machines, Johnson's rule (1954) computes a schedule of minimum…

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

Bounds on Multiprocessing Timing Anomalies 2: Scheduling the k Longest Independent Tasks Optimally First Gives ω(k)/ω₀ ≤ 1 + (1 − 1/n)/(1 + ⌊k/n⌋)Research Paper

Parallel processing poses a basic allocation question: given tasks of known lengths and several identical processors, how much time is lost when tasks are assigned by a simple list rule instead of an optimal allocation? The finishing time is the moment the last processor completes its work. For independent tasks, a list rule starts each next task on a…

8 thms2 active usersReviewed
🏆Completed
Operations ResearchOptimizationProbability·Captain: mikedeng1

Scheduling Deteriorating Jobs on a Single Processor II: If E(X_j)/α_j and α_j/[c_j(1+α_j)] Both Increase in j, the Order 1, …, N Minimizes the Weighted Expected Completion Time (Proposition 2)Research Paper

On one processor, the completion time of a job normally depends on how much work precedes it. In the model of Browne and Yechiali (1990), waiting also changes the job's own processing requirement: a job that starts later takes longer. The sequence therefore changes both when each job starts and how long subsequent jobs must wait. This matters when the goal…

6 thms2 active usersReviewed
🏆Completed
CombinatoricsOperations ResearchOptimization·Captain: mikedeng1

One-Processor Scheduling with Symmetric Earliness and Tardiness Penalties 3: For Maximum Discrepancy, Some Optimum Schedule Is in Standard Form and Has the Release Time PropertyResearch Paper

In just-in-time scheduling each job has a preferred time, and finishing it early is as undesirable as finishing it late. Garey, Tarjan and Wilfong (Math. Oper. Res. 13 (1988), 330–348) study the one-processor version in which task TiT_iTi​ has a length li≥0l_i \ge 0li​≥0 and a preferred starting time ai≥0a_i \ge 0ai​≥0, and the discrepancy of a task started at time sis_isi​ is …

7 thms2 active usersReviewed
🏆Completed
CombinatoricsOperations ResearchOptimization·Captain: mikedeng1

One-Processor Scheduling with Symmetric Earliness and Tardiness Penalties 2: For a Fixed Task Order, the Block-Shifting Algorithm Minimizes the Total DiscrepancyResearch Paper

A task may have a preferred execution time because a material delivery, external event, or downstream operation is timed to it. Starting early can be as costly as starting late. Garey, Tarjan, and Wilfong study this situation on one processor, where tasks cannot overlap but idle time between tasks is permitted. Their total-discrepancy problem is hard when…

6 thms2 active usersReviewed
🏆Completed
CombinatoricsOperations ResearchTheoretical Computer Science·Captain: mikedeng1

Approximation Algorithms for Scheduling Unrelated Parallel Machines 3: On the 3-Dimensional Matching Instances, a Schedule within ρ < 3/2 of Optimal Has Makespan ≤ 2 Iff a Matching ExistsResearch Paper

Minimum makespan scheduling on unrelated parallel machines, written R ∣∣ Cmax⁡R\,||\,C_{\max}R∣∣Cmax​, is one of the basic models of scheduling theory: nnn jobs must each be run on one of mmm machines, and the time a job takes depends arbitrarily on the machine. Lenstra, Shmoys and Tardos (CWI Report OS-R8714, 1987; journal version Math. Programming 46, 1990) gave a polynomial…

8 thms2 active usersReviewed
🏆Completed
CombinatoricsOperations ResearchTheoretical Computer Science·Captain: mikedeng1

Approximation Algorithms for Scheduling Unrelated Parallel Machines 4: With Times in {p, q} and gcd(p, q) = 1, a q-Dimensional Matching Exists Iff a Schedule Has Makespan ≤ pqResearch Paper

Minimum makespan scheduling on unrelated parallel machines asks for an assignment of nnn jobs to mmm machines, where job jjj takes pijp_{ij}pij​ time units on machine iii, so that the largest machine load is as small as possible. In the three-field notation of Graham, Lawler, Lenstra and Rinnooy Kan (1979) it is R ∥ Cmax⁡R\,\|\,C_{\max}R∥Cmax​. It models load balancing across…

7 thms2 active usersReviewed
🏆Completed
Operations ResearchOptimizationProbability·Captain: mikedeng1

Scheduling Deteriorating Jobs on a Single Processor I: Under Linear Deterioration, Sequencing by Increasing E(X_i)/α_i Minimizes the Expected MakespanResearch Paper

In classical single-machine stochastic scheduling, NNN jobs with independent random processing requirements XiX_iXi​ are processed one after another, and the makespan (the completion time of the last job) is the same for every schedule that never idles: it is X1+⋯+XNX_1+\dots+X_NX1​+⋯+XN​. Research therefore concentrated on weighted flow times and rewards. Browne and Yechiali (Ope…

6 thms2 active usersReviewed
PreviousPage 2 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