0
$\begingroup$

At work I stumbled across this problem of allocating resources:

We are given a set of objects belonging to one of seven possible classes (multiple objects per class are allowed). We distinguish between classes A, B, ... G, because they have 3 possible attributes (weight, interest, size). We also have four boxes X, Y, W, Z. The boxes have three characteristics on their own: importance, strength, size. We want to put the objects into the boxes in order to maximize a metric based on the properties of the classes and the boxes. We are also wondering if, given enough pairs "set of objects"-"allocation in boxes" tweak the characteristics of the classes in order to minimize a cost function representing the difference between the desired assignment and the one computed.

I tried checking standard methods of resource allocation or cost minimization (definitely not my expertise), but I couldn't manage to apply them to this specific problem. Any ideas on how to proceed, or on where could I find info related to this problem?

EDIT: This is the definition of the metric used that must be maximized. After that a simple example.

Let's just define $W_{obj}$, $I_{obj}$, $S_{obj}$ as the characteristics of an object and $I_box$, $St_box$, $Si_box$ as the characteristics of the box. The metric is the sum, over all the boxes, of this measure:

$I_{box} * \sum{I_{obj}} + 1/(St_{box} - \sum{W_{obj}}) + 1/(Si_{box} - \sum{S_{obj}})$

If you have multiple objects you just some over all of them.

As an example, suppose we have Box 1 and Box 2, with properties:

  • $St_{b1} = 10$, $I_{b1} = 3$, $Si_{b1} = 9$;
  • $St_{b2} = 20$, $I_{b2} = 1$, $Si_{b2} = 10$;

and three objects with properties:

  • $I_{o1} = 1$, $W_{o1} = 3$, $S_{o1} = 4$;
  • $I_{o2} = 1$, $W_{o2} = 3$, $S_{o2} = 4$;
  • $I_{o3} = 3$, $W_{o3} = 8$, $S_{o3} = 1$;

If we put all the objects in Box 2, our score will be:

$I_{b2} * (I_{o1} + I_{o2} + I_{o3}) + 1/(St_{b2} - (W_{o1} + W_{o2} + W_{o3})) + 1/(Si_{b2} - (S_{o1} + S_{o2} + S_{o3}))$ $= (1 * 5) + 1/(20-14) + 1/(10-9)$ $= 6.16$

Since no objects goes in Box 1, its score will be:

$1/St_{b1} + 1/Si_{b1} = 1/10 + 1/9 = 0.21$

Hence the score for this particular configuration is $6.16 + 0.21 = 6.37$

The aim is to find the configuration (i.e. the object distribution) maximising such score.

Hope it's a bit clearer now.

|cite|improve this question
$\endgroup$
  • $\begingroup$ "We want to put the objects into the boxes in order to maximize a metric based on the properties of the classes and the boxes". Can you develop ? And give a simple exemple. $\endgroup$ – Vince Feb 5 at 14:36
  • $\begingroup$ Sure, apologies for not explaining it well enough. I added an example in the question. $\endgroup$ – Fasteno Feb 6 at 8:32
  • $\begingroup$ So you have to maximize this metric ? I don't understand the weight part ... In your example, the score of box 1 is not zero. Is it normal ? $\endgroup$ – Vince Feb 6 at 16:40
  • $\begingroup$ Well, in the example I posted I decided to put all the objects in Box 2. That led to a score of 6.16 for Box 2 and score 0.21 for Box 1, with a total score of 6.37. The aim is to distribute the objects in the boxes as to maximise this score. Apologies for not clarifying it, but when if a box receives no objects at all its score is usually negligible, that's why I didn't consider it. Will update the questions for more clarity. $\endgroup$ – Fasteno Feb 6 at 20:50
  • $\begingroup$ Ok and when sum of weights in a box is equal to the strength of the box, what happens ? 1 / 0 ? When sum of weights is bigger ? Your metric seems a little weird from a physical point of view and with a lot of singularities from a mathematical point of view. $\endgroup$ – Vince Feb 6 at 22:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.