Preemptive versus nonpreemptive scheduling of biprocessor tasks on dedicated processors

Article Abstract:

The problem of scheduling biprocessor tasks on dedicated processors was examined. Specifically, the computational complexity of minimizing the schedule length or makespan and the total completion times in preemptive and nonpreemptive scheduling cases were compared. In addition, the problem of scheduling under precedence constraints was considered. The results proved that the problem is 'NP-hard in the strong sense.'

Multiprocessing

---

On the complexity of scheduling with large communication delays

Article Abstract:

The computational complexity of scheduling tasks represented by a directed acyclic graph of length L with unit execution time and constant communication delays (c) greater than or equal to two was considered. Specifically, proof that it may be solved in polynomial time is given for the case of L equal to (c + 1), or (c + 2) for c = 2. In addition, it is proven to be NP-complete for (c + 3) for arbitrary values of c.

---

A note on the complexity of single-machine scheduling with a common due date, earliness-tardiness, and batch delivery costs

Article Abstract:

The problem of using a common due date to minimize earliness-tardiness and batch delivery costs in single-machine scheduling situations is considered. Specifically, the problem is shown to be NP-hard when the common due date is zero, the unit earliness penalty is zero and the processing time is equal to the unit tardiness penalty. To confirm this, the three-partition problem is reduced and shown to be NP-complete.

Similar abstracts:

• Abstracts: China: problem of succession. Jiang visit offers opportunities. Jiang wants to be his own man: after years of biding his time, he is now asserting authority
• Abstracts: Faith in the community. Adjusting space for changing times. David Chipperfield: buildings and projects
• Abstracts: Back in business. Move over Mao; hardline communist faction prepares to woo unions
• Abstracts: Oil sales in the pipeline. Airport auction in Bolivia
• Abstracts: Getting on with it. Soaring ambition

This website is not affiliated with document authors or copyright owners. This page is provided for informational purposes only. Unintentional errors are possible.