CODEWITHSUNDEEP
algorithmoptimizationmodelresourcesschedule
Darko Vukoje
Darko Vukoje

Reputation: 31

Resources Schedule Optimisation

Here is my problem:

  1. How many matches can play that week

Monday 8h, courts 1,2 and 3 Tuesday 10h court 2 etc

I need to build the algorithm to create optimized schedule:

Hi,

What kind of algorithm I need here? Is it a linear programing model or something else?

In an ideal world - I would build the model in json and send it to some Cloud optimisation engine like Gurabi to get the solution back. Or any other tool that you suggest.

Thanks Darko

Upvotes: 2

Views: 63

Answers (1)

ravenspoint
ravenspoint

Reputation: 20596

The first thing to do is to check if there is a feasible solution. You need to check if the possible opponents of every player share times when they can play at a time when there is a court available.

Now you have an agent to task assignment problem which can be solved using the maximum flow algorithm ( https://en.wikipedia.org/wiki/Maximum_flow_problem ).

The "tasks" are the opponent pair and time combinations found by the feasibility check

The "agents" are the court times.

Of course, the application of the max flow algorithm must be adjusted to include the special constraints of your problem.

Each player to play at least once

Out of the box, the algorithm will optimize the total number of games played, even if some players do not get to play. Suggestion: Run the algorithm without this constraint and check for players without a game. Brute force those players to play a games and remove the players and the court time used from the problem and re-run the algorithm

prioritize certain players by different criteria

I do not know what this means. If Player A is "prioritized" and Player B is not, what is the difference in how A and B are handled?

prioritize certain times

I do not know what this means. If Wednesday morning is "prioritized" but not Wednesday afternoon, what difference does this make?

Here is a setup that tests code is working for a simple sanity test

void generate1()
{
    // generate players
    thePlayers.emplace_back("pA");
    thePlayers.emplace_back("pB");

    // add possible opponents
    thePlayers[0].addOpp("pB");
    thePlayers[1].addOpp("pA");

    // add available times
    thePlayers[0].addTime(1);
    thePlayers[0].addTime(3);
    thePlayers[0].addTime(2);
    thePlayers[1].addTime(2);
    thePlayers[1].addTime(3);

    // generate court times
    theCourts.emplace_back(1);
    theCourts.emplace_back(2);
    theCourts.emplace_back(3);
}

Here is the C++ code that checks the setup is feasible and generates the tasks for the maximum flow algorithm

/**
 * @brief Check for feasibility
 *
 * i.e. every player has at least one opponent with a matching available time and possible court time
 */
void check()
{
    // loop over players
    int pi = -1;
    for (auto &p : thePlayers)
    {
        pi++;

        // assume that player has no possible opponent with matching time
        bool ok = false;

        // loop over player available times
        for (int t : p.myTimes)
        {
            // loop over player possible opponents
            for (auto &os : p.myOpps)
            {
                // loop over opponents available times
                int oi = findPlayer(os);
                for (int ot : thePlayers[oi].myTimes)
                {
                    if (t == ot)
                    {
                        // loop over court times
                        for (auto &c : theCourts)
                        {
                            if (t == c.myTime)
                            {
                                // found a match with opponent and court

                                ok = true;

                                // create a task for each feasible pair
                                // only record task when player 1 index less than player 2
                                if (pi < oi) {
                                    theTasks.emplace_back(p, thePlayers[oi], t);
                                }
                            }
                        }
                    }
                }
            }
        }
        if (!ok)
        {
            std::cout << "Cannot find opponent for " << p.myName << "\n";
            exit(1);
        }
    }
    std::cout << "found feasible opponents for all players\n";
    cTask::displayAll();
}

here is the output

found feasible opponents for all players
pA v pB at 3
pA v pB at 2

Here is the C++ code to apply the maximum flow algorithm. It uses the method from the pathfinder graph theory library https://github.com/JamesBremner/PathFinder

void maxflow()
{
    // setup the flow graph
    raven::graph::sGraphData gd;
    gd.g.directed();
    for (auto &c : theCourts)
        for (auto &t : theTasks)
            if (t.myt == c.myTime)
            {
                // Game can be played on this court
                gd.g.add(c.myName, t.myName);
            }

    // apply the maxflow algorithm, allocating games to courts
    auto ga = raven::graph::alloc(gd);

    // display game schedule
    std::cout << "\nGame Schedule\n";
    for (int ei = 0; ei < ga.edgeCount(); ei++)
    {
            auto t = gd.g.userName(gd.g.dest(ei));
            theTasks[atoi(t.substr(4).c_str())].display();
    }
}

Output is

Game Schedule
pA v pB at 2 on cA

Complete application code at https://github.com/JamesBremner/so78357533

You have not answered my questions about the priorities :-(

Time Priorities

My best guess for the time priorities is that when two players have a choice of court times, they will be scheduled at the time with the highest priority. Something like this can be implemented easily by presorting the "tasks" before doing the allocation in order of decreasing priority.

Like this:

Same priority for all times

found feasible opponents for all players
pA v pB at 1 on cA
pA v pB at 2 on cA

Game Schedule
pA v pB at 1 on cA

Time 2 at high priority

found feasible opponents for all players
pA v pB at 1 on cA
pA v pB at 2 on cA

Game Schedule
pA v pB at 2 on cA

Player Priority

I cannot guess what you require for the player priority feature. Please edit you question to clarify this.

Upvotes: 1

Related Questions