Job Sequencing With Deadlines Generator

What this generator does

Generates unit-length jobs with profits and deadlines, then accepts them most valuable first, placing each in the latest slot before its deadline that still has a free machine. Every accepted job is re-checked against its deadline, and no slot may hold more jobs than there are machines.

How to use this tool

1. Choose how many jobs, and how many machines run in parallel.
2. Generate and read which jobs were accepted and which were rejected.
3. Compare the profit against the earliest-deadline figure in the notes.
4. Look at where each job sits: none is earlier in the queue than it needs to be.

Understanding the controls

How many jobs

Between 3 and 20. Deadlines are drawn against the available capacity, so there are always more jobs than slots and something must be rejected.

Machines running in parallel

One is the classic single-machine problem. Two to six means that many jobs share each slot — a workshop with three benches rather than one.

Common use cases

• Practising the job sequencing problem on instances you did not pick
• Showing that urgency and value are different scheduling keys
• Producing worked examples with a provably optimal answer
• Generating test cases for a task-acceptance routine
• Teaching why a greedy rule needs the right ordering to be optimal

How this generator works

Jobs are sorted by profit, highest first, and each is placed in the latest free slot that still meets its deadline. Placing late rather than early is the crucial half of the rule: it keeps the early slots free for jobs whose deadlines are tight, and it is what makes most-valuable-first genuinely optimal here rather than just a reasonable heuristic. The same instance is also solved earliest-deadline-first for comparison. Before display every accepted job is checked to finish on or before its deadline, no slot may hold two jobs, and the naive rule is confirmed never to beat the optimal one. With several machines the rule is unchanged and so is its optimality: a set of jobs fits m machines exactly when, for every time t, no more than m × t of them are due by t — which is the condition the checker applies, and it knows nothing about how the schedule was built.

Randomness and fairness

Uses your browser's cryptographic random source for profits and deadlines by default. Deadlines tighten as capacity rises, so the instance stays interesting rather than fitting everything. A seed reproduces the same instance, which is deterministic and not cryptographically secure.

For how randomness is produced across the whole site, see how Generate Random works.

Limitations and good to know

• Every job takes exactly one unit of time, which is what makes the greedy rule optimal — jobs of differing lengths are a much harder problem.
• Deadlines are hard: a job that misses its deadline is worth nothing rather than less, so no partial credit or lateness penalty is modelled.
• Machines are identical: two benches are interchangeable here, and a shop where only one machine can do a particular job is a different problem.
• Profits are independent, so bundles, dependencies between jobs and cancellation costs are outside the model.

Privacy and your data

Instances and schedules are computed in your browser, with nothing transmitted, stored or included in analytics.