Makespan Scheduling Problem Generator
A pile of jobs and a few identical machines, and the question of when the last one finishes. Two bounds fall out immediately: nothing can finish before the total work divided among the machines, and nothing can finish before its own longest job. Scheduling the longest jobs first often hits one of those bounds exactly, and when it does the schedule is optimal with no search at all. When it does not, this says so rather than claiming a best answer it has not proved.
What this generator does
Draws job durations, assigns them to machines longest-first — each job going to whichever machine is currently least loaded — and reports the makespan against the higher of the two lower bounds. Where they match, the schedule is provably optimal.
How to use this tool
- Choose how many jobs and how many machines.
- Assign the jobs to machines so the last one finishes as early as you can.
- Reveal the schedule to compare with longest-processing-time-first.
- Check the bound — sometimes it proves the answer, sometimes it leaves a gap.
Understanding the controls
- How many jobs
- Between 4 and 14. More jobs make the bound easier to hit, so smaller instances are the interesting ones for teaching.
- How many machines
- Between 2 and 5, and always fewer than the number of jobs — otherwise every machine takes one job and there is nothing to decide.
- Seed
- Reproduces the same job durations, so the same instance can be attempted twice or compared between people.
- Show the answer
- Reveals which jobs went to which machine, each machine's load, and whether the bound proves the schedule optimal.
Common use cases
- Practice instances for a load-balancing or scheduling exercise
- Showing why sorting jobs longest-first beats taking them in order
- Demonstrating two different lower bounds and when each one binds
- Testing a scheduler against instances with a known bound
- Setting a group the same jobs and machines from a seed
How this generator works
Longest-processing-time-first sorts jobs by duration and gives each to the least loaded machine, which is the standard approximation for this problem. The lower bound is the larger of the total work divided by the machine count, rounded up, and the single longest job — neither can be beaten by any schedule. Both are recomputed from the finished schedule before it is shown.
Randomness and fairness
The job durations are random; the schedule and the bounds follow from them. Seeded instances reproduce exactly and are therefore explicitly not cryptographically secure. Unseeded ones draw from the browser's cryptographically secure generator.
For how randomness is produced across the whole site, see how Generate Random works.
Limitations and good to know
- Machines are identical, so this is not the case where some machines are faster than others.
- Jobs are independent, with no precedence constraints and no setup times between them.
- The schedule is a heuristic answer except where it meets the bound; no search for a better one is run.
- Jobs cannot be split across machines, which would make the problem trivial.
- Instances are not stored between visits; seed one you want again.
Privacy and your data
Job durations and schedules are generated in your browser. Nothing you set or generate is transmitted or kept between visits.
Related generators
- Bin Packing Problem GeneratorPacking instances with bins of one size or several at different prices, each with an answer, a lower bound, and a plain statement of when the two meet.
- Assembly Line Balancing GeneratorAssigns tasks with precedence rules to workstations under a fixed cycle time, and says how many stations the work alone would have needed.
- Job Sequencing With Deadlines GeneratorChooses which deadline-bound jobs to run, on one machine or several in parallel, for the highest total profit — proved against exhaustive search.
- Knapsack Problem Generator0/1 knapsack instances solved exactly by dynamic programming, with the value-per-weight answer shown alongside for comparison.
- Travelling Salesman Problem GeneratorTour instances on random coordinates, solved exactly by Held-Karp, with the nearest-neighbour tour shown for comparison.
- Task Allocation GeneratorShare tasks out across a team with real rules — must do, must not do, capacity limits — and a clear answer when the rules cannot all hold.