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


closed as off-topic by D.W., Mohammad Al-Turkistany, Kaveh, Jan Johannsen, Marzio De Biasi Mar 21 '17 at 13:09

This question appears to be off-topic. The users who voted to close gave this specific reason:

  • "Our site policy prohibits simultaneous crossposting: it duplicates effort and fractures discussion. Crossposting is permitted after a week has passed without a satisfying answer elsewhere. When crossposting please summarize the relevant discussions from other sites in your question and link between the copies in both directions." – D.W., Mohammad Al-Turkistany, Kaveh, Jan Johannsen, Marzio De Biasi
If this question can be reworded to fit the rules in the help center, please edit the question.