C# Distributing jobs fairly on accounts - distribution algorithm

[khaled ahmad]

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.

So, Let's say that we have the following accounts list:

_accounts = new List<string>{"Account-A", "Account-B", "Account-C", "Account-D", "Account-E"};

and the following sites list:

var sites = new List<string>{"Site-A", "Site-B", "Site-C", "Site-D", "Site-E"};

Each account can publish to a specific site according to the following dynamic dictionary:

Key: Is the 'site ID' and value is a list of accounts IDs that can publish to that 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"});

Publishing jobs are created as follows:

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

    // Get a random account from  _accounts that can post to a site
    // Lookup the entries in Dict and determine accounts that can publish to site
    var acct = GetAccountCanPost(Dict, site, _accounts);

    job.Site = site;
    job.Account = acct;

    jobs.Add(job);
}


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

    var selectedId = accountIdsAssoc.PickRandomAccount();
    var account = accounts.FirstOrDefault(s => s == selectedId);

    return account;
}

when the jobs are created it is something similar to (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, something like this

   > Account-A 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

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..

[Claude Moore]

khaled ahmad wrote:
Each account can publish to a specific site according to the following dynamic dictionary:

Key: Is the 'site ID' and value is a list of accounts IDs that can publish to that 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"});

khaled ahmad wrote:

Publishing jobs are created as follows:

var jobs = new List<Job>();
foreach (var site in sites)
{        
    var job = new Job();
 
    // Get a random account from  _accounts that can post to a site
    // Lookup the entries in Dict and determine accounts that can publish to site
    var acct = GetAccountCanPost(Dict, site, _accounts);
 
    job.Site = site;
    job.Account = acct;
 
    jobs.Add(job);
}
 
 
public static string GetAccountCanPost(Dictionary<string, List<string>> dict, string targetSite, List<string> accounts)
{
    var accountIdsAssoc = GetAccountsIdsAssociatedWithSite(dict, targetSite);
 
    var selectedId = accountIdsAssoc.PickRandomAccount();
    var account = accounts.FirstOrDefault(s => s == selectedId);
 
    return account;
}

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:

It's not completely clear - at least to me - what accountIdsAssoc.PickRandomAccount(); does really, but as a first glance looks like that since grants to publish on a server are not fairly distributed too,  given a site is more likely to draw Account A than the others.
Indeed A could publish on each server - with the sole exception of site C - while account E and D can also use server B and C, respectively. So i would guess to have more jobs assigned to A.
If you want to be fair with respect to the number of jobs associated with accounts, you should iterate over accounts and assign a job for each account, in a round-robin way. You could also be fair with servers workload, for example when it's Account A turn, you should pick the less loaded server where A can publish works.
For E or D accounts you have no choice.

[Claude Moore]

And welcome to the ranch !

[Bill Crim]

You could also think of it like this...

Determine how capable each sender is. By counting the number of sites they can each send too. you want to keep all senders busy, so the senders with the lowest number of sites they can publish to, should come first. Your pickiest workers should get the first crack at any jobs. You're least picky workers will pick up any remainder.

I would recommend you rearrange your data to be like this...

enum State { Unpublished, Publishing, Published}
class Sender
{
    public string Name;
    public bool IsPublishing;
    public List<string> Sites; //Who can I publish to?
    public void PublishOnThread(Site site){}
}
class Sites
{
    public string Name;
    public State State;
    public List<string> Publishers; //Who can publish to me?
}

var sites = GetSites() //Put into order of LEAST number of publishers.
    .OrderBy(s=>s.Publishers.Count)
    .ToList();
var senders = GetSenders()   //Put sender is order of LEAST capable first. 
    .OrderBy(s=>s.Sites.Count)
    .ToList();
while(sites.Any(s=>!s.IsPublished))
{
    var unassignedSenders = senders.Where(s=>!s.IsPublishing);  //Everyone who isn't publishing, 
    var unassignedSites = sites.Where(s=>s.State == State.Unpublished);  //All sites who haven't been published.
   
    foreach(var sender in unassignedSenders) 
    {
        foreach(var site in unassignedSites) 
        {
            sender.PublishOnThread(site);
        }
    }
}

Annotate-then-Execute is usually a better model than Loop-and-Calculate. Mostly because you can use the debugger to expect the system easily in this model.