Distributing jobs fairly on accounts - distribution algorithm

Question

I'm working on a project that publish to a multiple websites using a multiple accounts. each account can publish to a specific website. as shown in the 'Dict' below. The problem is I'm trying to distribute the publishing jobs on accounts fairly and making a distance between accounts that has more than 1 job.

using System;
using System.Collections.Generic;
using System.Linq;

public class Program
{
    public struct Job
    {
        public string Site { get; set; }
        public string Account { get; set; }
    }


    private  static readonly Dictionary<string, List<string>> Dict = new Dictionary<string, List<string>>();
    private  static List<string> _accounts;


    public static void Main()
    {
        var sites = new List<string>{"Site-A", "Site-B", "Site-C", "Site-D", "Site-E"};
         _accounts = new List<string>{"Account-A", "Account-B", "Account-C", "Account-D", "Account-E"};

        // Permissions dictionary. specify accounts that has a permessions to  publish on a particular Site
        Dict.Add("Site-A", new List<string>{"Account-A", "Account-C"});
        Dict.Add("Site-B", new List<string>{"Account-A", "Account-E"});
        Dict.Add("Site-C", new List<string>{"Account-C", "Account-D"});
        Dict.Add("Site-D", new List<string>{"Account-A"});
        Dict.Add("Site-E", new List<string>{"Account-A"});

            var jobs = new List<Job>();
            foreach (var site in sites)
            {
                var job = new Job();

                // Get an account that has a permissions to publish on 'site'
                // checking against the permissions dictionary Dict
                var account = GetAccountCanPost(Dict, site, _accounts);

                job.Site = site;
                job.Account = account;

                jobs.Add(job);
            }


            var jobsCountForEachAccountDict = CalculateJobsCountForEachAccounts(jobs);

            //////#### Now.. We need to re Order Jobs and swipe it here before send it to processing ####.....//////

            foreach (var job in jobs)
            {
                Console.WriteLine(job.Account + " publish on " + job.Site);
            }

    }

     public static Dictionary<string, int> CalculateJobsCountForEachAccounts(List<Job> jobs)
        {
            var dict = new Dictionary<string, int>();

            foreach (var job in jobs)
            {
                if (dict.ContainsKey(job.Account))
                    dict[job.Account]++;
                else
                    dict.Add(job.Account, 1);
            }

            return dict;
        }


     public static string GetAccountCanPost(Dictionary<string, List<string>> dict, string targetSite, List<string> accounts)
        {
            var accountIdsAssoc = GetAccountsIdsAssociatedWithCommunity(dict, targetSite);

            var selectedId = PickRandom(accountIdsAssoc, new Random());
            var account = accounts.FirstOrDefault(s => s == selectedId);

            return account;
        }

     private static List<string> GetAccountsIdsAssociatedWithCommunity(Dictionary<string, List<string>> communitiesAccountsAssociationsDict, string communityId)
        {
            if (communitiesAccountsAssociationsDict.ContainsKey(communityId))
                return communitiesAccountsAssociationsDict[communityId];

            return null;
        }

         private static T PickRandom<T>(IList<T> list, Random random)
        {
            var index = random.Next(0, list.Count);
            return list[(int) index];
        }

}

when the jobs are created it is something similar to this: (Before re-adjusting the jobs distribution)

> Account-A Publish on Site-A 
> Account-E Publish on Site-B
> Account-D Publish on Site-C
> Account-A Publish on Site-D
> Account-A Publish on Site-E

The publishing jobs created above are not fairly distributed to accounts, as you can see 'Account-A' has 3 jobs assigned while there's an other accounts can publish to the 'sites' as defined in 'Dict' so it should look something like:

> Account-C Publish on Site-A
> Account-E Publish on Site-B
> Account-A Publish on Site-D
> Account-D Publish on Site-C
> Account-A Publish on Site-E

In the output above the jobs are distributed fairly on accounts and also there's a distance between accounts that has more than 1 job

An example on distance between jobs:

    > Account-A Publish on Site-A 
    > Account-E Publish on Site-B
    > Account-D Publish on Site-C
    > Account-A Publish on Site-D
    > Account-A Publish on Site-E

Job 4 and 5 are being processed by Account-A. An account should not process two jobs sequentially, so it could be swapped with another job.

It will be highly appreciated if you could help. I need an algorithm that do the job distribution to get similar output. Performance is not important.

Thank you..

Answer 1

It can be improved, but this will do what you need:

using System;
using System.Collections.Generic;
using System.Linq;

namespace ConsoleApp1
{
    public struct Job
    {
        public string Site { get; set; }
        public string Account { get; set; }
    }

    public class Program
    {
        public static void Main(string[] args)
        {
            Dictionary<string, List<string>> permissionsDict = new Dictionary<string, List<string>>();
            permissionsDict.Add("Site-A", new List<string> { "Account-A", "Account-C" });
            permissionsDict.Add("Site-B", new List<string> { "Account-A", "Account-E" });
            permissionsDict.Add("Site-C", new List<string> { "Account-C", "Account-D" });
            permissionsDict.Add("Site-D", new List<string> { "Account-A" });
            permissionsDict.Add("Site-E", new List<string> { "Account-A" });

            // get responsibilities rate for each account

            Dictionary<string, int> responsibilitiesRate = GetResponsibilitiesRate(permissionsDict);

            List<Job> jobs = new List<Job>();

            // building jobs list

            foreach (var permission in permissionsDict)
            {
                var job = new Job();
                job.Site = permission.Key;

                // for the current site, see what account has lower responsibility rate
                int minResponsibilities = permission.Value.Min(x => responsibilitiesRate[x]);
                string account = permission.Value.First(x => responsibilitiesRate[x] == minResponsibilities);
                responsibilitiesRate[account]++;

                job.Account = account;
                jobs.Add(job);
            }

            // order jobs making sure distance between accounts has more than 1 job

            jobs = RandomOrderResponsibilities(jobs);

            foreach (var job in jobs)
            {
                Console.WriteLine(job.Account + " publish on " + job.Site);
            }

            Console.ReadLine();
        }

        private static Dictionary<string, int> GetResponsibilitiesRate(Dictionary<string, List<string>> dict)
        {
            Dictionary<string, int> responsibilitiesCount = new Dictionary<string, int>();

            foreach (var kvp in dict)
            {
                foreach (var account in kvp.Value)
                {
                    if (responsibilitiesCount.ContainsKey(account))
                    {
                        responsibilitiesCount[account]++;
                    }
                    else
                    {
                        responsibilitiesCount.Add(account, 1);
                    }
                }
            }

            return responsibilitiesCount.OrderBy(x => x.Value).ToDictionary(x => x.Key, x => x.Value);
        }

        private static List<Job> RandomOrderResponsibilities(List<Job> jobs)
        {
            bool couldComplete = true;
            var maxIterations = 1000;
            var iterationCount = 0;

            do
            {
                // shuffle
                jobs = jobs.OrderBy(a => Guid.NewGuid()).ToList();

                for (int i = 1; i < jobs.Count; i++)
                {
                    if (jobs[i].Account == jobs[i - 1].Account)
                    {
                        couldComplete = false;

                        for (int j = i + 1; j < jobs.Count; j++)
                        {
                            if (jobs[j].Account != jobs[i].Account)
                            {
                                // swipe
                                var temp = jobs[i];
                                jobs[i] = jobs[j];
                                jobs[j] = temp;
                                couldComplete = true;
                                break;
                            }
                        }
                    }
                }

                iterationCount++;
            } while (!couldComplete && iterationCount < maxIterations);

            return jobs;
        }
    }
}

Output (random solution):

Account-A publish on Site-D
Account-C publish on Site-A
Account-A publish on Site-E
Account-D publish on Site-C
Account-E publish on Site-B