This problem is concerned with the NP-completeness of deadline scheduling on two identical processors. The input...

 

Transcribed Image Text:

This problem is concerned with the NP-completeness of deadline scheduling on two identical processors. The input to the problem is a set of n jobs, all released at time 0. Each job is associated with a processing time and a deadline. There are two identical processors. A job can be executed on any one processor, but one it is assigned to a processor, it cannot be migrated to another processor. Preemption (and later resumption at the preemption point) has zero overhead. The aim is to determine whether there exists a schedule to meet the deadlines of all jobs. Prove that the problem is NP-complete. This problem is concerned with the NP-completeness of deadline scheduling on two identical processors. The input to the problem is a set of n jobs, all released at time 0. Each job is associated with a processing time and a deadline. There are two identical processors. A job can be executed on any one processor, but one it is assigned to a processor, it cannot be migrated to another processor. Preemption (and later resumption at the preemption point) has zero overhead. The aim is to determine whether there exists a schedule to meet the deadlines of all jobs. Prove that the problem is NP-complete.

Answer rating: 100% (QA)

Ans To prove that the deadline scheduling problem on two identical processors is NPcomplete we need to show two things The problem is in NP The proble... View the full answer