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 acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Browse other questions tagged or ask your own question.