0
$\begingroup$

Simplified question: I have a dataset of how well certain agents perform on certain tasks, and based on this I've trained a model that can make predictions for newly incoming tasks. I'd like to make an algorithm that distributes tasks amongst agents to maximise performance.

One way would be to make a prediction for each scenario - each agent assigned to each new set of tasks (note that one agent can work on more than one task at a time) -, thus iterating through all possible solutions, and summing performance and finding the max.

This, however, would be very complex - to iterate through every possible combination an finding a maximum.

Is there a better way to optimise (maximise performance) without having to iterate through all possible solutions? How could I do that?

Original question:

Let's take a look at the following setup:

  • There are a number of "agents"
  • Agents work on "jobs"
  • Each agent might be better at certain jobs, but the jobs get assigned by random, and not based on performance (good performance = the least amount of time spent working)

I'd like to know if there's any ML algorithm that can learn how to assign jobs to agents as to minimise time spent working (maximise performance).

I know that with methods like regression or classification, or even deep learning you can teach the algorithm to predict a target variable, but in this case I do not want to reach a target variable, but want to increase performance (minimise time spent working). Is there such an algorithm/method that could "learn" from past performance reviews and assign new jobs to agents to maximize performance?

Edit:

A bit more formalised:

I teach an SVM (or a regressor, or a neural net), that will be able to predict how well a certain agent A1 performs on a certain (type of) task T1 (call this performance P1). So when a new task comes in, I'll be able to predict P1 based on A1 and T1. BUT! And here comes the question. Now that I can predict P1 based on A1 and T1, how do I use this knowledge to actually assign ALL the tasks - T1...Tn amongst all the agents A1...Am as to maximise the performance: sum(P1, P2, ..., Pi)?

Improve this question
$\endgroup$
10
  • 2
    $\begingroup$This question still does not define maximise performance and that is not some trivial after-thought, but key to having an answerable question. You need a well-defined metric for "performance" before it can be optimised. Your "A bit more formalised" section fails to do this adequately, because it is trivially maximised by assigning tasks based on best performing agent (potentially assigning all tasks to one agent). Perhaps your question could be changed to be about creating such a metric if you can explain what you mean by "maximise performance" in a less formal way.$\endgroup$
    – Neil Slater
    CommentedOct 30, 2017 at 16:52
  • $\begingroup$By "maximising performance" I meant keeping the sum of the resolution time amongst all agents minimised.$\endgroup$
    – lte__
    CommentedOct 31, 2017 at 13:21
  • $\begingroup$The point is exactly to NOT maximise by assigning tasks based on best performing agent (potentially assigning all tasks to one agent). It is to maximise OVERALL performance of the team. So the sum of the time spent on tasks should be minimal.$\endgroup$
    – lte__
    CommentedOct 31, 2017 at 13:25
  • $\begingroup$Let performance be measured by time - the quicker we get the resolution to all tasks, the higher our performance.$\endgroup$
    – lte__
    CommentedOct 31, 2017 at 13:34
  • 1
    $\begingroup$I'm missing any constraints, couldn't you just assign each task to the agent with the best predicted performance?$\endgroup$
    – Jan van der Vegt
    CommentedMar 30, 2018 at 13:47

4 Answers 4

Reset to default
0
$\begingroup$

Now that I can predict P1 based on A1 and T1, how do I use this knowledge to actually assign ALL the tasks - T1...Tn amongst all the agents A1...Am as to maximise the performance: sum(P1, P2, ..., Pi)?

In general Genetic algorithms can deal with this kind of optimization problems. The tricky part is to define the population with this particular assignment problem. Assuming a given set of tasks T1...Tn to achieve, an "individual" in the population would probably be an assignment A1...An, that is a possible assignment of the tasks to a (subset of) the agents. Thus the tasks play the role of the "genes":

  • a mutation consists in replacing an agent with another for a particular task/gene
  • a crossover consists in randomly combining the pairs (task,agent) from two assignments/individuals

The rest is straightforward genetic learning:

  • the fitness function of an assignment/individual is the sum of the performances for this assignment
  • at each generation the best assignments/individuals are selected to generate the next generation by cross-over

After a few generations the population will converge to a set of optimal assignments. Mind that it might end up in a local optimum, you can tune the hyper-parameters to minimize this risk.

Improve this answer
$\endgroup$
    0
    $\begingroup$

    Some ideas:1. Could you assign features for jobs and assignments? Performance would be the labels. Then you could simply use an SVM for example. 2. Given a user representation matrix X, each row i is an agent, and a job representation matrix Y, each j is a job representation, and a matrix of performance P, where every row stands for a user and every column how well the agent performed on that job, you could learn X and Y through optimization. Check this: https://en.wikipedia.org/wiki/Non-negative_matrix_factorization I hope this helps.

    Improve this answer
    $\endgroup$
    8
    • $\begingroup$Yes I agree, just that the question is more about using what the model learned. So from your example, I teach an SVM, which will be able to predict how well agent A1 performs on task T1 (call this performance P1). So when a new task comes in, I'll be able to predict P1 from A1 and T1. BUT! And here comes the question. Now that I can predict P1 from A1 and T1, how do I use this knowledge to actually assign ALL the tasks - T1...Tn amongst all the agents A1...Am as to maximize the performance sum(P1, P2, ..., Pi)?$\endgroup$
      – lte__
      CommentedAug 28, 2017 at 13:17
    • 1
      $\begingroup$Approach 1. For your problem, we need a feature representation. The standard way would be to assign features right, so for agents it might be where he lived and so on, previous experiences... For a job it might be how tough it is, social and so on. You could concatenate the agent and job vectors for input. Then you train with performance as predictions on the given job/agent. Approac2. This approach will learn features by itself as it optimizes. As an example, see section 3, "Weighted matrix factorization" in the paper "Deep content-based recommendation" for an example for when it can be used.$\endgroup$
      – Carl Rynegardh
      CommentedAug 28, 2017 at 13:34
    • $\begingroup$For approach 1: I still don't see, how this performs the optimal task assignments. I'm looking for something like this: inputs = [ [task1, task2, task3, task4], [agent1, agent2] ] output = [agent1 should work on task1 and task4] [agent2 should work on task2 and task3] And all this so that the performance is maximised. So I'm looking for an algorithm that makes "output" from the "input" which are defined above.$\endgroup$
      – lte__
      CommentedAug 28, 2017 at 14:08
    • $\begingroup$Because I get it, I can teach the algorithm to PREDICT the performance of an agent working on a certain task. But how can I ASSIGN ALL the tasks to ALL the agents so that the performance among ALL the agents is maximised?$\endgroup$
      – lte__
      CommentedAug 28, 2017 at 14:09
    • $\begingroup$So, I don't want to predict performance, I know how to do that. I want to automatise task assignment based on said prediction, systemwide.$\endgroup$
      – lte__
      CommentedAug 28, 2017 at 14:11
    0
    $\begingroup$

    I just had another idea.

    Why don't you uniformly randomize the assignments. For each randomization of assignments, calculate the cost.

    Run this, for I don't know how many times. Pick the configuration with the least cost.

    Because of linearity of expectation, this should give you a good enough answer, might not be the optimal, but more efficient.

    Improve this answer
    $\endgroup$
      0
      $\begingroup$

      I think no-one can solve this analytically, and I cannot model this easily with ML algorithms. Furthermore I think your problem specification is not clear enough. For instance, there are not enough constraints, and you don't say how many types of agents there are.

      In any regard, this seems to be a job for the Netlogo agent-based-modeling software.

      Answer part 1: You could reframe your question, assign it a "NetLogo" tag, ask again on stackoverflow.com. I happen to know that the Netlogo developers and other experts hang out there. You could get a much better answer than I could provide here.

      Maybe someone has developed a NetLogo Model that is similar to your problem, and you can adapt and study it. (Netlogo has an internal grid-search tool called "BehaviourSpace"), you can export data, and there are APIs for connecting Netlogo with other tools such as R.

      Answer part 2: In any case, this reminds me of the "El Farol" model included in the Netlogo agent-based-modeling software.

      El Farol is a bar in Santa Fe, New Mexico. The bar is popular — especially on Thursday nights when they offer Irish music — but sometimes becomes overcrowded and unpleasant. In fact, if the patrons of the bar think it will be overcrowded they stay home; otherwise they go enjoy themselves at El Farol. This model explores what happens to the overall attendance at the bar on these popular Thursday evenings, as the patrons use different strategies for determining how crowded they think the bar will be. ... El Farol was originally put forth by Brian Arthur (1994) as an example of how one might model economic systems of boundedly rational agents who use inductive reasoning.

      I have included a screeenshot so you'll get an impression what I'm talking about.

      In the screenshot, replace

      • The Blue square (The bar) with "Your System"
      • "Crowded" with "Capacity Utilization: high",
      • "Bar Attendance" with "General Performance" and
      • "number-strategies" with "agent-types"

      netlogo-screenshot

      Improve this answer
      $\endgroup$

        Start asking to get answers

        Find the answer to your question by asking.

        Ask question

        Explore related questions

        See similar questions with these tags.