Task: Prove NP-Completeness of a Scheduling Problem
Task: Prove NP-Completeness of a Scheduling Problem: a task in Terminal-Lego-15k (Harbor dataset). Weighted Job Scheduling with Deadline (WJSD): - Given a set of n jobs, each job i has: - Processing time: p i - Deadline: d i - Penalty: w i (incurred if job is not completed by deadline) - Question…
The task
**Weighted Job Scheduling with Deadline (WJSD):** - Given a set of n jobs, each job i has: - Processing time: p_i - Deadline: d_i - Penalty: w_i (incurred if job is not completed by deadline) - Question: Is there a schedule of all jobs on a single machine such that the total penalty is at most k?
Part of PrimeIntellect/Terminal-Lego-15k.