Math/programming question: Given a set of weekday/hour numbers, how would one have a program create schedules from those numbers (with little waste/overlap)?

[SineSwiper]

<div style='font: 11pt "EngraversGothic BT", "Copperplate Gothic Light"; text-align: left; '>I'm trying to figure out a process, but it's racking my brain. This would allow 10-hour days (plus lunch), 8-hour days (plus lunch), and 4-hour days (no lunch), based on a hr/wd map of how many employees per hour. Obviously, you're going to have some overlap, but how do you minimize it? Where would you begin?

Come on...pretend this is college credit for computer programming class :)</div>

[Kupek]

<div style='font: 10pt verdana; text-align: left; padding: 0% 10% 0% 10%; '>Can you give some sample input and output? I'm not sure what you're given, and what you want to produce.</div>

[Zhuge Liang]

<div style='font: ; text-align: left; '>greedy algorithm</div>

[SineSwiper]

<div style='font: 11pt "EngraversGothic BT", "Copperplate Gothic Light"; text-align: left; '>Input: 7 by 24 matrix of how many employees needed per hour per weekday.
Output: A list of work schedules like Sunday-Thursday 8-5, etc., based on the matrix, with as little waste as possible.

Sample input:
<font type="Courier New">
S M T W T F S
12AM 1 3 2 2 2 1 1
1AM 1 2 1 1 1 1 1
2AM 1 1 1 1 1 1 1
3AM 1 1 1 1 1 1 1
4AM 1 1 1 1 1 1 1
5AM 1 1 1 1 1 1 1
6AM 1 1 1 1 1 1 1
7AM 3 5 4 7 2 3 3
8AM 7 9 5 6 5 4 3
Etc.</div>

[SineSwiper]

<div style='font: 11pt "EngraversGothic BT", "Copperplate Gothic Light"; text-align: left; '>Eh?</div>

[SineSwiper]

<div style='font: 11pt "EngraversGothic BT", "Copperplate Gothic Light"; text-align: left; '>Of course, but how would it be implemented?</div>

[Ishamael]

<div style='font: 14pt "Sans Serif"; text-align: justify; padding: 0% 15% 0% 15%; '>You also need to know total number of possible employees in order to assign schedules to them at the end as well as total number of hours they are allowed to work. Also, you should indicate whether work schedules can be continuous or broken up over the same day...</div>

[Kupek]

<div style='font: 10pt verdana; text-align: left; padding: 0% 10% 0% 10%; '>Instead, you could make it a minimization problem. What's the <i>minimum</i> number of employees that need to work during a given period? Of course, if the number of employees is fixed, then you'd need to have the solution reflect that.

But that is certainly missing: how long is a shift?

A few thoughts... you don't want to start creating your schedule at 12am Sunday. You want to start creating it at a "normal" time, like 8am Monday. Do all of the "normal" times first - all of the 8 - 5, M - F times. Then go back and do all of the odd times. Or maybe go through the matrix x times, where x is the largest number of people that are ever needed at one time. Every pass, you create schedules for that day. You'll have to keep track, of course, of how many people you've assigned already to a particular day and time.

I have a suspicion that trying to find the optimal schedules - minimum number of workers and minimum overlap - is NP-Complete, so you'll have to make some assumptions. But I could be wrong.</div>

[Ishamael]

<div style='font: 14pt "Sans Serif"; text-align: justify; padding: 0% 15% 0% 15%; '>Well, judging by the input it looks like they already know how many people need to work at any given point in time (and thus know exactly how many workers they need). So the problem reduces to matching raw numbers in the matrix to real employees (along with schedules).</div>

[Kupek]

<div style='font: 10pt verdana; text-align: left; padding: 0% 10% 0% 10%; '>Hmm. In this case, yes, but it would be possible to have an input that you'd need more employees than the maximum number working at the same time, if you constrained the amount of time an employee can work a week.</div>

[SineSwiper]

<div style='font: 11pt "EngraversGothic BT", "Copperplate Gothic Light"; text-align: left; '>Uhhh...no. We might know how many employee we need AT ANY GIVEN HOUR, but not the total number of employees.</div>

[SineSwiper]

<div style='font: 11pt "EngraversGothic BT", "Copperplate Gothic Light"; text-align: left; '>Is either 11-hours in four days, 9-hours in five days, or 4-hours in five days (might be less days on part-time). The lunches are already included as "work hours", because the hr/wd matrix already accounts for that.</div>

[ManaMan]

<div style='font: 12pt Arial; text-align: left; '>No Zhuge, he wants you to do it for him! :)</div>

[SineSwiper]

<div style='font: 11pt "EngraversGothic BT", "Copperplate Gothic Light"; text-align: left; '>Heh...after several days of brooding over it, I completed it. Pretty much uses a brute force method.</div>