Refining the boundary between P and NP for identical machine scheduling problems with preemption and release dates

Details Refining the boundary between P and NP for identical machine scheduling problems with preemption and release dates Refining the boundary between P and NP for identical machine scheduling problems with preemption and release dates

2011-12-19

arxiv.org/abs/1112.4400v1

Computer Science

Discrete Mathematics

Scientific paper

In this paper, we are interested in parallel identical machine scheduling problems with preemption and release dates in case of a regular criterion to be minimized. We show that solutions having a permutation flow shop structure are dominant if there exists an optimal solution with completion times scheduled in the same order as the release dates, or if there is no release date. We also prove that, for a subclass of these problems, the completion times of all jobs can be ordered in an optimal solution. Using these two results, we provide new results on polynomially-solvable problems and hence refine the boundary between P and NP for these problems.

Affiliated with

Also associated with

No associations

Rating

Refining the boundary between P and NP for identical machine scheduling problems with preemption and release dates does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Refining the boundary between P and NP for identical machine scheduling problems with preemption and release dates, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Refining the boundary between P and NP for identical machine scheduling problems with preemption and release dates will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-212887