S
S
Sergey Sokolov2014-11-12 03:01:11
Algorithms
Sergey Sokolov, 2014-11-12 03:01:11

How to distribute cargo among wagons evenly?

There are many loads of different weights from 1 to 1E7. Most are closer to 1E3.
And there are N identical wagons, among which these goods must be distributed so that the wagon loading by weight varies minimally .
I thought we should strive for the arithmetic mean (total mass / N) for each car. But how close to actually get closer with the existing set - then I came to a dead end.
It looks like a one-dimensional packing problem . Cargo/wagons are just for illustration purposes. Actually tasks and threads. Help with the algorithm.
Upd. clarification / complication, which is not the path to the truth. My question is above. But in general, the task is a little different. This task occurs twice on my system:

  1. the first is a one-time launch of a multi-threaded executor. Here it is desirable to load it so that all streams end as soon as possible - for this you need to scatter the goods along the streams as evenly as possible, without separate "tails" in one stream and idle others.
  2. the second is the general schedule. These "cars" are regular launches of the performer from the previous point on the time axis. The whole train is a cycle during which each "load" must be sent. Here I pursue two goals: to observe an approximately regular interval in the launch of each load, and to evenly distribute the load throughout the train.

More on the second point. The load has three parameters: the already mentioned mass; start – time (“wagon number”) when it can already be sent; and the target is the time (“wagon number”) when it should ideally be sent.
The sent cargo updates its schedule: after T hours it must be sent again.
Firewood is sometimes “thrown” into a number of cargoes: load peaks arise, which over time should be spread over time so that the cars again become evenly loaded. Such a "live" auto-balancing system.
Surely the task is relatively typical, I just don’t know where to look for a description of such an algorithm.

Answer the question

In order to leave comments, you need to log in

5 answer(s)
M
Mrrl, 2014-11-12
@sergiks

(About the original problem)
After we sent the heaviest loads (which are more than the average load of the car), we recalculate the arithmetic mean, and start stacking the goods in the cars, starting with the heaviest. Three strategies are possible.
1) We put the next (heaviest of the remaining) cargo in the emptyest car
2) We put the next cargo in the busiest of the cars in which this cargo is still placed (i.e. the total weight of the car and cargo does not exceed the arithmetic mean)
3) The next We put the cargo in a random of the wagons in which the cargo is placed.
In strategies (2,3), sometimes the situation "there is no place to put the load" will arise. Then we put it in the most empty car, and send it.
Then you need to experiment to choose the most suitable of these strategies. Intuition is not very helpful here.
If the car has a load limit L, then the cargo that does not fit even in the empty car is left until the next train. When loading it, we first scatter very heavy loads, then - left from the previous train, then - all new ones.

3
386DX, 2014-11-12
@386DX

make a visualization and see.
In general, you take the largest task and throw it in the smallest ones to the arithmetic mean.
To be precise, divide the number of all tasks by the number of threads, you get N groups of tasks. take the largest problem and throw it in the smallest of each N group to the arithmetic mean..

E
Evgeny Kumanin, 2014-11-12
@jackkum

Calculate the average weight per wagon (+- error)
Sort the loads in descending order
We take the largest one in order, if it is within the error limits, load it into the wagon and remove it from the queue, if not, skip the next load, take the next one a little less and so on.
If the first load for the wagon is greater than the average, then add one of it to the next wagon.
And so on until the goods run out.

M
mamkaololosha, 2014-11-12
@mamkaololosha

1) Sort in ascending order
2) Divide the cargo by the number of wagons
3) Load one wagon with 1 product from the beginning, 1 from the end, etc.

D
DancingOnWater, 2014-11-12
@DancingOnWater

If the input is a rather long random sequence, then the problem is solved similarly to the voting procedure:
Randomly scatter loads over the cars. We choose which lies closest to the expectation mat. And we will throw out from the initial sequence those goods that lie in this car. Repeat recursively.
UPD: Although it all depends on the task. I minimized the RMS. At the same time, some wagon can be practically empty
. However, the task can be set differently: the mass of any wagon should not go beyond a certain corridor. Here is a completely different task.

Didn't find what you were looking for?

Ask your question

Ask a Question

731 491 924 answers to any question