Split staff into weekly shifts (4 weeks) unique per weeks

Question

I have been struggling with a requirement for some days now, and i think i am making it harder than it is. I want to make some kind of fluid rota/shift system. This should be a wizard / randomizer function just to help the user to create a "one time" timetable (facility management). I'll like to make it as generic as possible.

X amount of staff

X amount of daily shifts (ex. morning, lunch, evening and night)

X amount of periods (ex. 4 weeks - a period is one week)

This will result in the following setup:

Week 1: Morning (*), Lunch, Evening and Night

Week 2: Morning, Lunch (*), Evening and Night

Week 3: Morning, Lunch, Evening (*) and Night

Week 4: Morning, Lunch, Evening and Night (*)

Each staff must take a shift each week, but the shift must not be the same the following weeks. I can make the requirement that there should be enough staff to fill every shift for all weeks. The result should be random on every execution.

Example:

If i have 8 employees and 4 shifts per week. There should be at least 2 employees per shift per week.

If i have 4 employees and 4 shifts per week. There should be at least 1 employee per shift per week.

The amount of employees must always be equal or more that the amount of shifts.

Is there any "leftovers" this is OK, when the amount of employees doesn't match with the amount of shifts, then the users either must defined more shifts or employees.

Example can be seen here: http://v2.iclean.dk/shifts

I have the following code:

Classes

[DebuggerDisplay("ID: {ID}, Name: {Name}")]
public class Staff
{
    public Staff(int id, string name)
    {
        ID = id;
        Name = name;
        Schedulers = new List<StaffScheduler>();
    }
    public int ID { get; set; }
    public string Name { get; set; }
    public List<StaffScheduler> Schedulers { get; set; }
}
public class StaffMap
{
    public StaffMap(Staff staff, StaffScheduler scheduler)
    {
        Staff = staff;
        Scheduler = scheduler;
    }
    public Staff Staff { get; set; }
    public StaffScheduler Scheduler { get; set; }
}

[DebuggerDisplay("ID: {ID}, Name: {Name}")]
public class StaffScheduler
{
    public StaffScheduler(int id, string name)
    {
        ID = id;
        Name = name;
    }

    public int ID { get; set; }
    public string Name { get; set; }
}

[DebuggerDisplay("Name: {Name}, Start: {DateStart}, End: {DateEnd}")]
public class DateRangeShift
{
    public DateRangeShift()
    {
        Staff = new List<StaffMap>();
    }
    public DateRangeShift(string name, DateTime start, DateTime end)
        : this()
    {
        Name = name;
        DateStart = start;
        DateEnd = new DateTime(end.Year, end.Month, end.Day, 23, 59, 59);
    }

    public string Name { get; set; }
    public DateTime DateStart { get; set; }
    public DateTime DateEnd { get; set; }

    public List<StaffMap> Staff { get; set; }
}

MVC Controller code

private readonly int SHIFTS_MAX_SHUFFLE_RETRIES = 50;

public ActionResult Index()
{
    var dailySchedules = new List<StaffScheduler>() { 
        new StaffScheduler(1, "Morning"), 
        new StaffScheduler(2, "Lunch"), 
        new StaffScheduler(3, "Evening"), 
        new StaffScheduler(4, "Night")
    };

    List<DateRangeShift> shiftList = new List<DateRangeShift>();
    shiftList.Add(new DateRangeShift("Week 1", new DateTime(2013, 3, 4), new DateTime(2013, 3, 10)));
    shiftList.Add(new DateRangeShift("Week 2", new DateTime(2013, 3, 11), new DateTime(2013, 3, 17)));
    shiftList.Add(new DateRangeShift("Week 3", new DateTime(2013, 3, 18), new DateTime(2013, 3, 24)));
    shiftList.Add(new DateRangeShift("Week 4", new DateTime(2013, 3, 25), new DateTime(2013, 3, 31)));

    List<Staff> staffList = new List<Staff>();
    staffList.Add(new Staff(1, "Fred Smith"));
    staffList.Add(new Staff(2, "Charlie Brown"));
    staffList.Add(new Staff(3, "Samantha Green"));
    staffList.Add(new Staff(4, "Bash Malik"));
    staffList.Add(new Staff(5, "Bryan Griffiths"));
    staffList.Add(new Staff(6, "Akaash Patel"));
    staffList.Add(new Staff(7, "Kang-Hyun Kim"));
    staffList.Add(new Staff(8, "Pedro Morales"));

    var shiftSegmentSize = (int)Math.Floor((double)staffList.Count / (double)dailySchedules.Count)

    int shuffleCount = 0;
    bool shuffleMatchedSize = true;
    do
    {
        shiftList.ForEach(e => e.Staff.Clear());
        shuffleMatchedSize = true;

        foreach (var shift in shiftList)
        {
            foreach (var scheduler in dailySchedules)
            {
                var schedulerEmployees = staffList.OrderByDescending(e => e.Schedulers.Count()).ThenBy(e => Guid.NewGuid()).Where(e => !shiftList.Any(sl => sl.Staff.Any(s => s.Scheduler.ID == scheduler.ID && s.Staff.ID == e.ID)) && !shift.Staff.Any(s => s.Staff.ID == e.ID)).Take(shiftSegmentSize).ToList();
                if (schedulerEmployees.Count < shiftSegmentSize)
                {
                    shuffleMatchedSize = false;
                    shuffleCount++;
                    break;
                }

                while (schedulerEmployees.Count > 0)
                {
                    var staffSelector = schedulerEmployees.FirstOrDefault();

                    var staff = staffList.FirstOrDefault(e => e.ID == staffSelector.ID);
                    staff.Schedulers.Add(scheduler);

                    shift.Staff.Add(new StaffMap(staff, scheduler));

                    schedulerEmployees.Remove(staffSelector);
                }
            }
            if (!shuffleMatchedSize)
                break;
        }

    } while (!shuffleMatchedSize && shuffleCount < SHIFTS_MAX_SHUFFLE_RETRIES);

    ViewData["Iterations"] = shuffleCount;

    return View(shiftList);
}

But since i order by the amount of shifts assigned to a staff, and order random afterwards .. i have a make retries until i get a min. match of staff / shift.

<h2>Week 1 <span>(04-03-2013 - 10-03-2013)</span></h2>
<table>
    <tr>
        <td>Morning</td>
        <td>Akaash Patel, Bash Malik</td>
    </tr>
    <tr>
        <td>Lunch</td>
        <td>Fred Smith, Kang-Hyun Kim</td>
    </tr>
    <tr>
        <td>Evening</td>
        <td>Charlie Brown, Samantha Green</td>
    </tr>
    <tr>
        <td>Night</td>
        <td>Bryan Griffiths, Pedro Morales</td>
    </tr>
</table>
<h2>Week 2 <span>(11-03-2013 - 17-03-2013)</span></h2>
<table>
    <tr>
        <td>Morning</td>
        <td>Fred Smith, Kang-Hyun Kim</td>
    </tr>
    <tr>
        <td>Lunch</td>
        <td>Akaash Patel, Bash Malik</td>
    </tr>
    <tr>
        <td>Evening</td>
        <td>Bryan Griffiths, Pedro Morales</td>
    </tr>
    <tr>
        <td>Night</td>
        <td>Charlie Brown, Samantha Green</td>
    </tr>
</table>
<h2>Week 3 <span>(18-03-2013 - 24-03-2013)</span></h2>
<table>
    <tr>
        <td>Morning</td>
        <td>Charlie Brown, Samantha Green</td>
    </tr>
    <tr>
        <td>Lunch</td>
        <td>Bryan Griffiths, Pedro Morales</td>
    </tr>
    <tr>
        <td>Evening</td>
        <td>Akaash Patel, Fred Smith</td>
    </tr>
    <tr>
        <td>Night</td>
        <td>Bash Malik, Kang-Hyun Kim</td>
    </tr>
</table>
<h2>Week 4 <span>(25-03-2013 - 31-03-2013)</span></h2>
<table>
    <tr>
        <td>Morning</td>
        <td>Bryan Griffiths, Pedro Morales</td>
    </tr>
    <tr>
        <td>Lunch</td>
        <td>Charlie Brown, Samantha Green</td>
    </tr>
    <tr>
        <td>Evening</td>
        <td>Bash Malik, Kang-Hyun Kim</td>
    </tr>
    <tr>
        <td>Night</td>
        <td>Akaash Patel, Fred Smith</td>
    </tr>
</table>

I can't get my head around how to do this. Hope someone can guide me.

Answer 1

I think this work for you:

        int maxLength = Math.Max(shiftList.Count, dailySchedules.Count);

        var shiftSegmentSize = staffList.Count / maxLength;

        var schedulerEmployees = staffList.OrderBy(e => Guid.NewGuid()) 
                                          .Take(shiftSegmentSize * maxLength) 
                                          .ToArray(); //

        for (int k = 0; k < shiftList.Count; k++)
        {
            for (int j = 0; j < dailySchedules.Count; j++)
            {
                int staffindex = (maxLength + j - k) % maxLength;

                for (int i = 0; i < shiftSegmentSize; i++)
                {
                    schedulerEmployees[staffindex + (i * maxLength)].Schedulers.Add(dailySchedules[j]);
                    shiftList[k].Staff.Add(new StaffMap(schedulerEmployees[staffindex + i * maxLength], dailySchedules[j]));
                }
            }
        }