<p>We have a system in which we have n number of process and m number of resources.The resources are boolean valued that is they can either have value 0 or 1(in brief suppose the resources as single way roads of network in which vehicle can travel in one direction at a time).Now each process requires certain number  of resources in some particular order for some units of time.</p>

<p>For example process number 1 requires resource number 3 for 5 units of time and resource value should be 1 in that interval of time.In that particular time no other process can use that resource with the resource having value 0.This is analogous to a vehicle using a particular road for 5 units of time in a particular direction and no other vehicle can travel in that road for that 5 units of time in opposite to the direction the former vehicle is travelling.</p>

<p>Now each vehicle need to start from a source and reach its destination following the constraints.
1.No two vehicle can collide ,that is no two vehicles can use the same resource(road in this case) in the opposite direction at any instant of time.Either the vehicle need to wait till the road is completely clear or take some other path (use some other resource which is available to reach destination).</p>

<p>Now we can compute the shortest path of the all the source -destination pair and in ideal condition each car can travel via the respective shortest path to reach its destination.</p>

<p>The objective of the problem is that without having collsions all the cars should reach to their destinations in minimum time.This leads to the question of scheduling the n process such that they are completed with minimum lateness.</p>

<p>Any ideas of solving this problem  </p>

CC BY-SA 3.0
2017-03-20T17:22:29.400Z
[Cross-posted to CS](http://cs.stackexchange.com/q/71812/9550).
David Richerby
CC BY-SA 3.0
2017-03-20T17:42:32.947Z
Cross-posted: http://stackoverflow.com/q/42731095/781723, http://cs.stackexchange.com/q/71812/755, http://cstheory.stackexchange.com/q/37802/5038.  Please [do not post the same question on multiple sites](https://meta.stackexchange.com/q/64068). Each community should have an honest shot at answering without anybody's time being wasted.
D.W.
CC BY-SA 3.0
2017-03-21T14:52:44.497Z
Modified the question
Ankit
CC BY-SA 3.0
2017-03-22T20:53:00.063Z
Some resource to solve this problem?
Ankit
<ds.algorithms><scheduling>
Prove np-hard with reduction from scheduling resources
Ankit
# Prove np-hard with reduction from scheduling resources

(Asked by: username_0 on 2017-03-20)

We have a system in which we have n number of process and m number of resources.The resources are boolean valued that is they can either have value 0 or 1(in brief suppose the resources as single way roads of network in which vehicle can travel in one direction at a time).Now each process requires certain number of resources in some particular order for some units of time.

For example process number 1 requires resource number 3 for 5 units of time and resource value should be 1 in that interval of time.In that particular time no other process can use that resource with the resource having value 0.This is analogous to a vehicle using a particular road for 5 units of time in a particular direction and no other vehicle can travel in that road for that 5 units of time in opposite to the direction the former vehicle is travelling.

Now each vehicle need to start from a source and reach its destination following the constraints.
1.No two vehicle can collide ,that is no two vehicles can use the same resource(road in this case) in the opposite direction at any instant of time.Either the vehicle need to wait till the road is completely clear or take some other path (use some other resource which is available to reach destination).

Now we can compute the shortest path of the all the source -destination pair and in ideal condition each car can travel via the respective shortest path to reach its destination.

The objective of the problem is that without having collsions all the cars should reach to their destinations in minimum time.This leads to the question of scheduling the n process such that they are completed with minimum lateness.

Any ideas of solving this problem

**Tags:** ds.algorithms, scheduling
> **Comments:**
> **username_1**: [Cross-posted to CS](http://cs.stackexchange.com/q/71812/9550).  
> **username_2**: Cross-posted: http://stackoverflow.com/q/42731095/781723, http://cs.stackexchange.com/q/71812/755, http://cstheory.stackexchange.com/q/37802/5038.  Please [do not post the same question on multiple sites](https://meta.stackexchange.com/q/64068). Each community should have an honest shot at answering without anybody's time being wasted.  
> **username_0**: Modified the question  
> **username_0**: Some resource to solve this problem?  

---

## 0 answers

