Need help positioning algorithm/fill a fleet of vehicles. Any ideas?

Good day!
Write the system to assign orders on the basis of vehicles.
Condition: there are N identical vehicles. And there are X orders for them to rent. Rent daily, each in his own time, with your day beginning and end.
Task: to place the orders on the basis of transport so that the utilization of the fleet was the most effective. That is, the gaps between orders from each vehicle was minimal.

Now do a complete search (in php) all options and it turns out very long.
Maybe there is a ready efficient algorithms for this task? Or what side to approach?
March 19th 20 at 09:08
1 answer
March 19th 20 at 09:10
Solution
1. Sort the orders by start time.
2. Take the first order in the queue.
3. Find the car, which by this time, the minimum free time.
4. Appointed by ordering her to throw it from the queue.
5. Back to claim 2.

In section 3 takes the minimum time, if you want to load and not use more cars than is required for orders. Either max if you need to spread them "fairly" and to minimize simple each participant.
And how about the fact that if we, for example, put a third order on a specific machine with minimal downtime, but with all tutu orders that her situation is not optimal, in the calculation on the employment of the Park.
That is, for example, at the 101st order would be that it would be reasonable to rearrange. - Juvenal.Zboncak commented on March 19th 20 at 09:13
@Juvenal.Zboncakyou define what "employment Park".
You need as closely as possible to use each machine or as evenly as possible to spread the orders. This is the opposite requirement.
Why 101 order will be something worth the swap? We choose orders by order start, none of the following will not interfere with the previous one. - Rogelio.Yundt commented on March 19th 20 at 09:16
@Rogelio.Yundt, orders can be of different duration, and act as pre for a couple of months and for tomorrow. and full more optimal choice for the location of the order which will start in two weeks, will become not relevant in connection with new orders that came after it, but will start and end earlier - Layne_Brekke49 commented on March 19th 20 at 09:19
@Rogelio.Yundt, it is "as tightly as possible to use."

Let me illustrate with an example:
In the picture: on top of the orders on certain days, at the bottom - they are placed in the fleet.
Here we have placed the orders 1,2,3. All set for one car, which is logical.
But in order 4 okazyvatsya that the best would be to put it in place of the third. Then skip days between orders will be minimal.

5c9de669aae2e207316163.jpeg - Juvenal.Zboncak commented on March 19th 20 at 09:22
@Layne_Brekke49, and you can imagine an algorithm that, on the one hand, with minimal clearance equipment loads, and with another - ready to suddenly push a new order in the chart? Of course, when rescheduling orders all need to be changed. But the available set of orders built in sets for each machine with minimum clearances exactly as I wrote. The full search here just doesn't make sense, because we do not care which of the free machines will have the following order - we've already distributed those orders that start before him.
In fact, you can take a piece of paper to visualize how this algorithm would build Gantt chart in the set of orders - quite primitive, but more complex and not required. - Rogelio.Yundt commented on March 19th 20 at 09:25
@Juvenal.Zboncak, see item 1 of the algorithm. - Rogelio.Yundt commented on March 19th 20 at 09:28
@Rogelio.Yundt, it seems to really work. Much gratitude to you! - Juvenal.Zboncak commented on March 19th 20 at 09:31

Find more questions by tags Algorithms