?
Solved

spreadout evenly

Posted on 2004-12-01
60
Medium Priority
?
517 Views
Last Modified: 2011-10-03
Hi,

We have a column called required.
this required contains the number of person needed every half-hour
so required looks like this

time         people needed
000              10
030              9
100              8
130              8
200              8
230              7
300              6
330              6
400              4
430              4
500              3
530              2            <-----------------------start here
600              5
630              6
700              8
730              15
800              25
830              36
900              55
930              90
1000             120
1030              125
1100              130
1130              132
1200              131
1230              125
1300              130
1330              120
1400              125
1430              120
1500              100
1530              85
1600              75
1630              75
1700              65
1730              50
1800              40
1830              35
1900              35
1930              30
2000              30
2030              27
2100              25
2130              23
2200              21
2230              20
2300              20
2330              15

I started  at 530 since this is the lowest number in the column.
from there i added  the number of people still needed for the half-hour.              
_____________________________________________________________________
resulted in to much number of people in the end of the day.

i.e.
below shows the number of excess people i have created.

1700              40   <----------------excess of 40 people
1730              40   <----------------excess of 40 people
1800              35   <----------------excess of 35 people
1830              20          etc....
1900              25
1930              20
2000              18
2030              15
2100              15
2130              18
2200              15
2230              12
2300              12
2330              12

I know it is impossible to create without excess, since we are talking about schedules (9 hours per schedule).
1. How to evenly spread out this excess from 00:00 to 23:30?

Thanks,
Lynnton
0
Comment
Question by:lynnton
  • 39
  • 16
  • 5
60 Comments
 
LVL 16

Expert Comment

by:muzzy2003
ID: 12715500
Hi lynnton

Not sure what you mean by:

>>from there i added  the number of people still needed for the half-hour.

Can you explain?
0
 
LVL 5

Expert Comment

by:PaulKeating
ID: 12715772
Let me see if I understand the question:

You start at 0530 needing two people. They work a 9-hour shift so they will be there until 1430. At 0600 you need 5 people, so you need another 3 to start and they will work until 1500. At 0630 you need another one to start who will work until 1530. Peak demand is at 1130 withn 132 people.

Everyone works a 9-hour shift, and you want to know, for every timeslot, how many people you are paying that are excess to requirements, since the two people who started at 1130 will still be there until 2030.

Have I got this right?
0
 
LVL 1

Author Comment

by:lynnton
ID: 12716311
PaulKeating,

I wanted to know how to spread the excess evenly from 00:00 to 23:00. presently I have all the excess at 1700 (more or less) then it goes through the next day. which is not ideal. spreading the excess or creating something that can spread excess evenly would be more efficient.


Thanks,
Lynnton
0
Nothing ever in the clear!

This technical paper will help you implement VMware’s VM encryption as well as implement Veeam encryption which together will achieve the nothing ever in the clear goal. If a bad guy steals VMs, backups or traffic they get nothing.

 
LVL 1

Author Comment

by:lynnton
ID: 12716368
muzzy2003,

The approach i'm currently using is incrementing schedules (adding) as needed.
so this would push all the excess during the late periods,
how can we create an approach to spreadh the excess evenly or can we work with what I have done?

Thanks,
Lynnton
0
 
LVL 16

Expert Comment

by:muzzy2003
ID: 12716487
Are you basically trying to fill your schedule with 9 hour sessions so as to cover the minimum requirements above, but to also minimise the excess staffing levels?
0
 
LVL 16

Expert Comment

by:muzzy2003
ID: 12716511
I mean, to minimise and also spread as evenly as possible the excess staffing levels?
0
 
LVL 1

Author Comment

by:lynnton
ID: 12716512
muzzy2003,

Yes, that is correct.

Thanks,
Lynnton
0
 
LVL 16

Expert Comment

by:muzzy2003
ID: 12716661
You would be able to fill this much more efficiently with an eight hour shift or a twenty seven hour day I would imagine! Anyway, I shall go away and have a think about this one.
0
 
LVL 5

Expert Comment

by:PaulKeating
ID: 12717043
That is really an operations research question, not an SQL question. I'm no mathematician, but unless I'm mistaken, this problem is a relative of the knapsack problem, which is "How do I pack parcels of various weights into knapsacks that each will hold 10kg, minimizing the number of knapsacks used?"

To see why it is related to the knapsack problem, imagine a histogram of staffing requirements with time on the x-axis and people needed on the y-axis. This histogram will have steps down on the left from 10 people to 2 between midnight and 0530, then step up steadily to 1130, then step down again on the right all the way to 2330.

Your task is to cover this histogram with skinny horizontal bars, one person high and 9 hours wide (1 shift) with the minimum overlap. The unwanted overlap is comparable to the unfilled space in the knapsack.

Why am I keen to establish that it is related to the knapsack problem? Simply because we know a lot of things about knapsack problem and its cousins. We know, for example, that short of exhaustive search, in principle there is no way to find the optimal solution to such problems. And exhaustive search may take unacceptably long, which is why they are sometimes called non-computable problems, though complexity buffs prefer the term "NP-complete". There may of course be algorithms that will find good or very good solutions. But good is not optimal, although it may come close.

The simple approach to the knapsack problem, which gives quite good results, is to first pack the heaviest parcel that you have, then the heaviest that will still fit, and so on until all of the remaining parcels are too heavy and you have to leave some space in the knapsack and go on to the next one.

The fact that your shifts are 9 hours long rather than 8 makes the problem quite hard, as muzzy2003 points out. To see this, imagine the skinny horizontal bars covering the widest part of the histogram, representing the 2 people that are needed around the clock. If you lay a stack of 3x2 bars across this part, 3 wide and 2 high, then the bars on the right will "project" 3 hours into the next day, meaning that you will have 4 people, not 2, from 0000 to 0300. So you have to do all the arithmetic mod 24.

This winkle aside, the approach would be to cover the bottom step first (2 persons high and 24h wide). Then cover the next step (1 person high and 23h30 wide, in two pieces). Then the next step (1 person high and 22h wide, in two pieces). And so on. If you have trouble visualizing this then draw the histogram.

For this you're going to need a procedural language with arrays. In principle you can do it in SQL, because there's a proof that says you can do anything in a set-oriented language that you can do in a procedural language. But in practice I reckon it would be very hard indeed.
0
 
LVL 1

Author Comment

by:lynnton
ID: 12719098
PaulKeating,

How does it work for 24/7 required?

people needed will be different for monday,tueday,wednesday,thursday,friday,saturday,sunday

on sunday there will be some people crossing over to monday, basically people from today will crossover the next day.

Thanks,
Lynnton
0
 
LVL 5

Expert Comment

by:PaulKeating
ID: 12719159
I think you misunderstood me. The lowest number of people required is 2. That means that 2 people need to be there from 0000 to 2359. Not the same two for 24 hours. You will need 6 shifts, ie 6 different people for 9 hours each, to cover that, with a 3-hour overlap into the next day. That was what I meant by covering the histogram with a 3x2 stack of 6 bars.

It's very difficult to explain the approach to the problem without being able to draw diagrams. That is why I described them in such detail: you need to draw them for yourself to see what I'm getting at.
0
 
LVL 1

Author Comment

by:lynnton
ID: 12719280
PaulKeating,

Can I requrest for a simple MSword file or mspaint diagrams?
I'm kinda lost...

johntlee@mailcity.com

Thanks,
Lynnton
0
 
LVL 16

Expert Comment

by:muzzy2003
ID: 12724100
lynnton - Paul is bang on with his description, although it's not exactly the knapsack problem which is based on fitting different sized items most efficiently. If you imagine a histogram (bar chart for the statistically challenged) of your requirements, you are trying to cover it with thin horizontal rectangles as he describes. The other difference between this and the knapsack problem is that here you must cover the histogram completely, but can go outside it, whereas in the knapsack you can't go outside, and have to fill as completely as possible.

This is unlikely to be a SQL-based solution, as Paul also points out. He is right about the fundamental language differences, and also right that it has been proved to be possible. However, it won't be pretty. Your app is in VB I think, on an Access back end? I will aim for something in VB for you if that's OK.
0
 
LVL 1

Author Comment

by:lynnton
ID: 12724123
muzzy2003,

Yes that is correct, VB with MS access. Anything coming from you is _always_ a pleasure.
I've already created a sample finalize program that "fills-out as needed". I'm always open to new approaches.

Thanks,
Lynnton
0
 
LVL 5

Expert Comment

by:PaulKeating
ID: 12730020
Ok, sorry about the delay, but it took a bit of time to get off-EE storage arranged. There is an Excel spreadsheet with the diagrams at //80.94.196.34/wwwroot/experts-exchange/peopleneeded.xls which you can get via ftp. I think it needs to be PASV mode.

Once you have the diagram, this explanation may make sense. As muzzy2003 points out, it is not exactly the knapsack problem, but I'm pretty confident that some clever mathematician could prove it was equivalent. What makes it different is that all the knapsacks are different sizes, and that you are allowed (under very strong constraints) to break the parcels into pieces (ie at midnight).

Looking at the staffing problem as a variant of the knapsack problem
--------------------------------------------------------------------

Look at the histogram of your staffing requirements. It's a log scale because otherwise the bars at the bottom I am talking about are too narrow to see. If this bothers you, just consider it to be carelessly drawn in the upper reaches. (Imagine me as an academic carelessly sketching out the graph on a whiteboard, rather than as the banker I am with a relentlessly precise Powerpoint slide.)

Consider the histogram to be made up of HORIZONTAL rather than vertical blue bars. Why horizontal bars? Because the resources you have available to cover the requirement are one-person shifts of 9 hours. If you draw a single shift on this diagram, it will be a skinny horizontal stripe one person high and 9 hours wide. Your task is to cover the blue area completely with such stripes, while minimizing the area of grey that they cover.

The bottom bar of the histogram is 2 high because your requirement never drops below 2. The next bar is one high because your next lowest requirement is 3. There's a half-hour notch in this bar, at 0530. The next bar is also one high because your next lowest requirement is 4. There's a one-hour notch in this bar, at 0500. Consider the bar to extend from the leftmost blue to the rightmost blue, ignoring embedded notches. So these two bars both start at 0000 and run for 24h. Higher up the pyramid, 4 different bars start at 0930, ending at 1700, 1630, 1530 and 1500 respectively. There are 31 bars in total because there are 31 distinct staffing levels. My Excel charting isn't up to getting it to do the lines separating the bars for me, so I've only done one of them.

Packing the knapsack
--------------------

1. You start at the bottom of the diagram. The first bar is 2 people high and 24h wide. You cover it by laying out a block of 6 skinny horizontal stripes representing shifts, two up and three across. In the diagrem, these skinny stripes are yellow and labelled "Shift". The third shift, starting at 1800, will "project" off the diagram on the right, that is, into the next day, so draw the projecting part again on the left of your diagram. Your diagram should now have the bottom bar completely covered in yellow, 2 high. The first 3 hours of the day will be yellow 4 high, because two stripes will the overlap from the previous day.

2. Next you lay out a row of shifts 1 high to cover the second bar, which is your requirement for 3 persons. This bar is one person high and runs for 24h, with an idle time from 0530 to 0600 (the notch in the bar), so this is the first instance of idle time. The row of stripes will again be 3 wide and the shifts will begin at 0300 (because you had overlap in the previous step), 1200, 2100. That will cause an projection of 6 hours off to the right. So draw that in again on the left. This wraparound will be at level 5 (because levels 3 and 4 are taken up by the 3-hour wraparound from step 1).

3. Next you lay out a row of shifts 1 high to cover the third bar, which is your requirement for 4 persons. This bar is one person high and runs for 24h, with an idle time from 0500 to 0600 (the notch in the bar). The shift starting times will exactly match those in step 2, and will project the same amount (6h) into the left of the diagram on level 6.

4. If you look at the 3rd diagram, you can see that at the 4th bar, you will only need 2 shifts, and there will be no wraparound.

5. On the 5th bar, you will be allocating shifts starting at 0630, leaving a half-hour slot uncovered, and with a half-hour wraparound.

Continue in this way until the entire blue area is covered in yellow stripes, left to right and bottom to top, always laying out the leftmost yellow stripe to just cover the blue. You will have to cover 31 horizontal bars in all, of varying thicknesses. Some bars will be only 1 person high. The one from 1000 to 1500 will be 10 high, and will require 10 shifts to cover it. The one from 1000 to 1430 will be 20 high, and require 20 shifts to cover it.

That is your first solution.

Iterating to find the least idle time
--------------------------------------

Redraw the graph so that the time runs from 0030 on the left to 0000 on the right. Redo the covering exercise. If the idle time is less than the first iteration, discard the first and keep the second. You can tally the idle time as you build the solution, but you don't really need to, because the total wasted time is easy to compute: it is the number of shifts * 9, less the area under the graph. This area is sum(people needed) / 48.

Do this 46 more times, starting with each timeslot in turn. I am not sure you need to do this 48 times, but I have a suspicion that you do, because of the day not being evenly divisible into shifts. In your original question you indicated that you had an intuition that the best timeslot to start with is 0530. You may be right. My own hunch is that the key to the solution is making the best use of the overlap shifts, and that means shifting the historgram so the leftmost timeslot is the one that begins the steepest slope, 0700.

Once more with feeling...
-------------------------

Then repeat the whole exercise, but this time laying out the shifts from right to left, so that the extra time in a shift projects off the left of the graph, into the previous day, and wraps around on the right. You might think that this will give the same results, but it won't, because your histogram is not symmetrical.

How good is this?
-----------------

The approach above won't give you an optimal solution but it will be pretty good. To guarantee an optimal result you would have to try every possible combination of left-to-right and right-to-left layouts. What I have described is LLLLLL... 31 times, and then RRRRR.... 31 times.

To get the optimal solution you would also have to try LRLRLR... LLRLLR... LLLRLL... and so on and so on. There are 2^31 such combinations, or about 2,147 million. Remember what I said about exhaustive search taking too long? If each iteration took a millisecond to evaluate, exhaustive search would take about a month to compute. If you could get it down to a microsecond, which is conceivable, it would still take about 35 minutes.

I'm pretty sure, but I certainly can't prove, that it won't matter much what order you tackle the horizontal bars to be covered. I've said, Start at the bottom and work up. You could also start at the top and work down. But it's possible that some other order, neither bottom-up nor top-down, but some arbitrary sequence, would give better results. It's a moot question, though, because there are 31! such orders. That is 8.2 x 10^23. Quite impossible to compute, even in a dozen lifetimes.

Even spread
-----------

Only when you have a solution you like, should you attempt to get the starting times even. That is because it is a separate optimization step: _given_ the optimal allocation of shifts, what is the optimal allocation of slack time?

Some of your yellow stripes will extend into the grey. Mark each such yellow stripe with the amount of time it could slide to the left or right and still cover the blue under it. Ignore stripes that have other stripes to the left or right that would also have to slide (needlessly complex). The algorithm above will tend to have stripes that can slide in only one direction, because of the left-to-right or right-to-left way you laid them out. Your adjustment is a question of sliding the stripes so that the number of excess staff in any timeslot approximates the average over all the timeslots with excess staff.

This _can_ be done by exhaustive search. There will be 82 shifts with slack, and each will have (on average, at a guess) 6 possible starting timeslots. Any given stripe can have at most 17 possible timeslots. That gives you of the order of 1000 combinations to check.

How do I know that there will be 82? We are only talking about the part of the day when a single shift can fill one seat for the required number of hours, with some slack. That is between 0900 and 1730. There are 82 such seats (132 minus 50).

In any case, spreading the slack time evenly is not purely an optimization problem, because you will have to take account of what people regard as asocial starting/ending times. For example, if it's apparent that they are being paid to do nothing, they may object to being made to stay until what they view as unreasonably late, when they could just as easily turn up 2 hours earlier and leave 2 hours earlier. So, just as your original question was not really an SQL question but an OR question, this is at least as much an HR issue as it is an OR issue.

Speaking of HR issues, don't your people get lunch breaks? Or are you counting the lunch break as part of the shift? I know that representing the breaks properly would complicate the solution, but it could make a considerable difference to the outcome.

0
 
LVL 5

Expert Comment

by:PaulKeating
ID: 12730063
Sorry, that URI should be http://rocketcottage.com/experts-exchange/peopleneeded.xls 

You will get "connection refused" if you try ftp.
0
 
LVL 1

Author Comment

by:lynnton
ID: 12733921
PaulKeating,

I had to read everything four times inorder to absorb what you've just uncovered.

Yes there are breaks and lunch break, I didn't want to complicate thing for now, but since you've taken my breath away,

1 shedule has 5 working days and two days off - this can ba any day.
1 schedule has 2 short 15 minutes breaks and 1 full hour lunch break.

schedules doesn't matter what time they start or go home.
the longest time before assigning a break is 3 hours
the shortest time before assinging a break is 1 hour

-we can create split schedules, split meaning monday, friday they start at 10:00 and tuesday, wednesday, sunday they start at 7:00
-as long as there is 22 hours variance from both start schedules (muzzy2003 already solved this equation)

I'll go and read it up again, but I think this is way out of my leage in programming.

Thanks,
Lynnton

0
 
LVL 1

Author Comment

by:lynnton
ID: 12733932
the schema for a schedules is
start-break-lunch-break-stop
0
 
LVL 1

Author Comment

by:lynnton
ID: 12733978
PaulKeating,

Hold on just a minute, I think this is somewhat related to the approach I made.

I have a table called binary.
this binary has 96 columns
00:00     00:15     00:30      00:45      01:00      01:15 .....23:45

i place "1" if there is a person covering that specific time and null for breaks.

-this can be those blocks you are guiding me with.
-i sum those "1" and get the total number of persons i have for the specific time.

Since my theory was "add as needed" my histogram from the left would be perfect. this means near zero variance.
the variance i'm showing is to high on the right side.

Do we move those shift blocks to the left ?

Thanks,
Lynnton

 
0
 
LVL 16

Accepted Solution

by:
muzzy2003 earned 2000 total points
ID: 12734204
Hi Paul, lynnton

NB: I have been preparing this post in reply to Paul's, and haven't yet taken any breaks into account.

Interesting point about being able to prove whether or not this is the knapsack problem. I suspect that it actually can't, but would be interested to see an attempt nonetheless, and I am quite prepared to stand corrected. To me, the key differences are that all the pieces here are the same size, and overlap is allowed. This is more closely related to the classic resource levelling problem, another "old chestnut" of decision mathematics.

The problem with viewing this as a problem of filling the histogram with these fixed horizontal bars is that you introduce the fitting of bars onto the diagram as an extra factor. This is a useful visualisation in planning a way ahead, but a bar can effectively be split into pieces on multiple rows of the diagram as you picture it, as long as the start and end points of each piece are aligned horizontally. Have you ever come across a game called "Connect 4"? I think it is helpful to picture this as being a bit like an enormous game of Connect 4 in the shape of the histogram you mention. Each move involves dropping 18 pieces (9 hours in half hour chunks) into 18 adjacent columns, and repeating this in such a way as to fill the histogram with minimal overspill.

The strategy that I suspect can best achieve this does draw a little on the knapsack problem, which can be fairly efficiently solved using a "first fit descending" pattern - you put into the knapsack at each step the biggest piece that will fit. The analogous "move" in this algorithm is to drop the pieces into the 18 adjacent columns that, at the time, have the greatest combined capacity. This means that you would start by dropping fairly centrally into the peak of lynnton's histogram.

Of course, there is inevitable overallocation, as the peak is much narrower than the width of the nine hour shifts.

Here is a VB class that will perform this algorithm:

****************** Start of class *****************

Option Explicit

Private m_intShiftLength As Integer

Private m_intSlots As Integer
Private m_intCapacity() As Integer
Private m_intCombinedCapacity() As Integer
Private m_intDrops() As Integer

Public Property Get ShiftLength() As Integer
    ShiftLength = m_intShiftLength
End Property

Public Property Let ShiftLength(ByVal value As Integer)
    m_intShiftLength = value
End Property

Public Property Let Requirements(ByVal value As Variant)
   
    Dim intLoop As Integer
   
    m_intSlots = 1 + UBound(value)
    ReDim m_intCapacity(m_intSlots)
    ReDim m_intCombinedCapacity(m_intSlots)
    ReDim m_intDrops(m_intSlots)
    For intLoop = 0 To m_intSlots - 1
        m_intCapacity(intLoop) = value(intLoop)
    Next 'intLoop
   
End Property

Private Property Get HighestPriorityIndex() As Integer

    Dim intReturn As Integer
    Dim intMax As Integer
    Dim intLoop As Integer
   
    intMax = 0
    intReturn = -1
   
    For intLoop = 0 To m_intSlots - 1
        If m_intCombinedCapacity(intLoop) > intMax Then
            intMax = m_intCombinedCapacity(intLoop)
            intReturn = intLoop
        End If
    Next 'intLoop
   
    HighestPriorityIndex = intReturn

End Property

Private Sub AddShift(ByVal index As Integer)

    Dim intLoop As Integer
    Dim intLoop2 As Integer
   
    m_intDrops(index) = m_intDrops(index) + 1
    For intLoop = 0 To m_intShiftLength - 1
        m_intCapacity((index + intLoop) Mod m_intSlots) = m_intCapacity((index + intLoop) Mod m_intSlots) - 1
        If m_intCapacity((index + intLoop) Mod m_intSlots) >= 0 Then
            For intLoop2 = 1 - m_intShiftLength To 0
                m_intCombinedCapacity((index + intLoop + intLoop2 + m_intSlots) Mod m_intSlots) = m_intCombinedCapacity((index + intLoop + intLoop2 + m_intSlots) Mod m_intSlots) - 1
            Next 'intLoop2
        End If
    Next 'intLoop

End Sub

Private Sub TryRemoveShift(ByVal index As Integer)

    Dim intLoop As Integer
    Dim intLoop2 As Integer
   
    For intLoop = 0 To m_intShiftLength - 1
        If m_intCapacity((index + intLoop) Mod m_intSlots) >= 0 Then Exit Sub
    Next 'intLoop
   
    m_intDrops(index) = m_intDrops(index) - 1
    For intLoop = 0 To m_intShiftLength - 1
        m_intCapacity((index + intLoop) Mod m_intSlots) = m_intCapacity((index + intLoop) Mod m_intSlots) + 1
        If m_intCapacity((index + intLoop) Mod m_intSlots) >= 0 Then
            For intLoop2 = 1 - m_intShiftLength To 0
                m_intCombinedCapacity((index + intLoop + intLoop2 + m_intSlots) Mod m_intSlots) = m_intCombinedCapacity((index + intLoop + intLoop2 + m_intSlots) Mod m_intSlots) + 1
            Next 'intLoop2
        End If
    Next 'intLoop

End Sub

Public Sub Initialise()

    Dim intLoop As Integer
    Dim intLoop2 As Integer
   
    For intLoop = 0 To m_intSlots - 1
        m_intCombinedCapacity(intLoop) = 0
        For intLoop2 = 0 To m_intShiftLength - 1
            m_intCombinedCapacity(intLoop) = m_intCombinedCapacity(intLoop) + _
                m_intCapacity((intLoop + intLoop2) Mod m_intSlots)
        Next 'intLoop2
    Next 'intLoop

End Sub

Public Sub Process()

    Dim intIndex As Integer
    Dim intLoop As Integer
    Dim intLoop2 As Integer
    Dim intOverAllocation As Integer

    Call Initialise
   
    intIndex = HighestPriorityIndex
    Do While intIndex >= 0
        Call AddShift(intIndex)
        intIndex = HighestPriorityIndex
    Loop
   
    For intLoop = 0 To m_intSlots
        For intLoop2 = 1 To m_intDrops(intLoop)
            Call TryRemoveShift(intLoop)
        Next 'intLoop2
    Next 'intLoop

    intOverAllocation = 0
    For intLoop = 0 To m_intSlots - 1
        intOverAllocation = intOverAllocation - m_intCapacity(intLoop)
        Debug.Print "Slot " & intLoop & ": " & m_intDrops(intLoop) & " shifts start, overallocation this slot " & (-m_intCapacity(intLoop))
    Next 'intLoop
    Debug.Print "Total overallocation: " & intOverAllocation & " slots"

End Sub

****************** End of class *******************

At the moment, it just outputs to the debug window. I have also created a simple VB executable project that demonstrates the use of this class, with a nice graph showing the allocation in progress. You can download it from http://www.dave-m.com/Leveler.zip. Let me know what you think. You get two roughly symmetrical peaks of excess allocation either side of the peak in the requirements.
0
 
LVL 1

Author Comment

by:lynnton
ID: 12734607
muzzy2003,

Looks AMAZING !!!
What does "slot 0: 0 shifts start, overallocation this slot 3" means?

Thanks,
Lynnton
0
 
LVL 1

Author Comment

by:lynnton
ID: 12734639
muzzy2003,

Got it now, you're really amazing you've done that in less than a week.
slot 0 - this is the required tagging    0 = 00:00
0 shifts start - number of persons comming in
overallocation - excess

Please correct me if i'm wrong..

Thanks,
Lynnton
0
 
LVL 16

Expert Comment

by:muzzy2003
ID: 12734651
That's exactly right.
0
 
LVL 1

Author Comment

by:lynnton
ID: 12734675
muzzy2003,

Below is a sample of my variance..using add as needed

day-time-needed-created-variance
Monday 0000 6   27   21
Monday 0015 6   26   20
Monday 0030 5   27   22
Monday 0045 5   25   20
Monday 0100 4   25   21
Monday 0115 4   26   22
Monday 0130 3   27   24
Monday 0145 3   28   25
Monday 0200 2   28   26
Monday 0215 2   28   26
Monday 0230 1   29   28
Monday 0245 1   29   28
Monday 0300 1   25   24
Monday 0315 1   25   24
Monday 0330 1   15   14
Monday 0345 1   15   14
Monday 0400 1   1   0
Monday 0415 1   1   0
Monday 0430 1   1   0
Monday 0445 1   1   0
Monday 0500 1   1   0
Monday 0515 1   2   1
Monday 0530 1   2   1
Monday 0545 1   2   1
Monday 0600 2   2   0
Monday 0615 2   2   0
Monday 0630 4   4   0
Monday 0645 4   4   0
Monday 0700 9   9   0
Monday 0715 9   10   1
Monday 0730 17   18   1
Monday 0745 17   17   0
Monday 0800 35   35   0
Monday 0815 35   35   0
Monday 0830 58   58   0
Monday 0845 58   59   1
Monday 0900 90   90   0
Monday 0915 90   90   0
Monday 0930 114   114   0
Monday 0945 114   117   3
Monday 1000 131   131   0
Monday 1015 131   132   1
Monday 1030 136   136   0
Monday 1045 136   137   1
Monday 1100 135   135   0
Monday 1115 135   135   0
Monday 1130 140   141   1
Monday 1145 140   140   0
Monday 1200 149   149   0
Monday 1215 149   151   2
Monday 1230 151   155   4
Monday 1245 151   151   0
Monday 1300 144   154   10
Monday 1315 144   144   0
Monday 1330 145   157   12
Monday 1345 145   145   0
Monday 1400 145   150   5
Monday 1415 145   145   0
Monday 1430 152   152   0
Monday 1445 152   158   6
Monday 1500 148   157   9
Monday 1515 148   173   25
Monday 1530 148   160   12
Monday 1545 148   173   25
Monday 1600 140   163   23
Monday 1615 140   166   26
Monday 1630 132   159   27
Monday 1645 132   161   29
Monday 1700 111   149   38
Monday 1715 111   148   37
Monday 1730 95   132   37
Monday 1745 95   132   37
Monday 1800 75   103   28
Monday 1815 75   102   27
Monday 1830 68   72   4
Monday 1845 68   74   6
Monday 1900 67   67   0
Monday 1915 67   69   2
Monday 1930 59   64   5
Monday 1945 59   71   12
Monday 2000 48   65   17
Monday 2015 48   69   21
Monday 2030 40   52   12
Monday 2045 40   53   13
Monday 2100 34   43   9
Monday 2115 34   39   5
Monday 2130 27   45   18
Monday 2145 27   42   15
Monday 2200 21   40   19
Monday 2215 21   41   20
Monday 2230 17   24   7
Monday 2245 17   25   8
Monday 2300 12   16   4
Monday 2315 12   16   4
Monday 2330 9   9   0
Monday 2345 9   11   2
0
 
LVL 1

Author Comment

by:lynnton
ID: 12734693
this is every fifteen minute interval. so that I can see how many I currently have.

hope this helps..
0
 
LVL 1

Author Comment

by:lynnton
ID: 12734743
the stats above has breaks and lunch schedules.
Monday at 0000  those are people from sunday


Sunday 1330 29   32   3
Sunday 1345 29   30   1
Sunday 1400 30   34   4
Sunday 1415 30   30   0
Sunday 1430 31   32   1
Sunday 1445 31   36   5
Sunday 1500 31   35   4
Sunday 1515 31   37   6
Sunday 1530 31   35   4
Sunday 1545 31   37   6
Sunday 1600 30   33   3
Sunday 1615 30   32   2
Sunday 1630 31   31   0
Sunday 1645 31   32   1
Sunday 1700 31   32   1
Sunday 1715 31   31   0
Sunday 1730 30   30   0
Sunday 1745 30   32   2
Sunday 1800 30   30   0
Sunday 1815 30   32   2
Sunday 1830 29   36   7
Sunday 1845 29   35   6
Sunday 1900 27   42   15
Sunday 1915 27   42   15
Sunday 1930 26   39   13
Sunday 1945 26   45   19
Sunday 2000 26   38   12
Sunday 2015 26   39   13
Sunday 2030 22   39   17
Sunday 2045 22   32   10
Sunday 2100 21   33   12
Sunday 2115 21   28   7
Sunday 2130 17   28   11
Monday 0000 6   27   21         <-----------------continue
Monday 0015 6   26   20
Monday 0030 5   27   22
Monday 0045 5   25   20
Monday 0100 4   25   21
Monday 0115 4   26   22
Monday 0130 3   27   24
Monday 0145 3   28   25
Monday 0200 2   28   26
Monday 0215 2   28   26
Monday 0230 1   29   28
Monday 0245 1   29   28
Monday 0300 1   25   24
Monday 0315 1   25   24
Monday 0330 1   15   14
Monday 0345 1   15   14      <--------------hope we could come to a point on spreading these guys evenly
Monday 0400 1   1   0
Monday 0415 1   1   0
Monday 0430 1   1   0
Monday 0445 1   1   0
Monday 0500 1   1   0
Monday 0515 1   2   1
Monday 0530 1   2   1
Monday 0545 1   2   1
Monday 0600 2   2   0
Monday 0615 2   2   0
Monday 0630 4   4   0

Please advice.

Thanks,
Lynnton
0
 
LVL 1

Author Comment

by:lynnton
ID: 12735319
muzzy2003,

I've tried running it on the actual thing, it's amazing.

"6,5,4,3,2,1,1,1,1,1,1,1,2,4,9,17,35,58,90,114,131,136,135,140,149,151,144,145,145,152,148,
148,140,132,111,95,75,68,67,59,48,40,34,27,21,17,12,9,6,5,4,3,2,2,1,1,1,1,2,2,2,4,8,15,30,50,2,
104,120,128,137,143,138,133,132,130,128,136,136,132,124,114,104,87,75,64,57,50,42,35,29,24,
19,15,12,8"

data is monday-tuesday
Please run it and advice.

Thanks,
Lynnton
0
 
LVL 16

Expert Comment

by:muzzy2003
ID: 12735471
In the middle of these values you've got:

50,2,104

Is the 2 a mistake?
0
 
LVL 1

Author Comment

by:lynnton
ID: 12735580
muzzy2003,

My apology, it should show as 50,82,104

Thanks,
Lynnton
0
 
LVL 16

Expert Comment

by:muzzy2003
ID: 12735609
OK. I've run it on the same data (had to make the form a bit bigger, obviously. I think this is a pretty good allocation. You can't avoid the overallocation either side of the peak, as at the peak you needover 100 people for less than a full shift, and you have four periods of relatively flat overallocation.
0
 
LVL 1

Author Comment

by:lynnton
ID: 12736122
muzzy2003,

I don't think it pretty good, it's the best solution!!!
_________________________________________________
How can I incorporate that with what I've done?

I have a access db filled with predifiened time schedules.
-check the required number of people
-if greater than what I have
-get one from binary table
-place it to forecast table, this is the table i check every 15 minutes on how many persons login for the specific interval.
-loop
-until 24/7

when assigning days off, I look at the whole week
i.e.
monday 3:00 needed is 3
_____________________________
required
mon tue wed thu fri sat sun
  3     4     2    4    5  2    3
_____________________________

i bubble sort'em from lowest to highest, then i set the first two lowest as day off ( 2,2,3,3,4,4,5)
-this means the third value is the nubmer of complete schedules i can create.
-in this case 3 monday.
-inorder to get the remaining value, subtract all the value to (3) except the days off.
-loop
-until we reach zero for monday to sunday

Thanks,
Lynnton




Thanks,
Lynnton
0
 
LVL 1

Author Comment

by:lynnton
ID: 12743143
muzzy2003,

I'm trying to remove all the shapes coding to get a better understanding of the magnificent coding.

Below is what i've come up, please advice if I have left out something or anyother.


Option Explicit

Private m_intShiftLength As Integer
Private m_intSlots As Integer
Private m_intCapacity() As Integer
Private m_intCombinedCapacity() As Integer
Private m_intDrops() As Integer

Public Property Get ShiftLength() As Integer
    ShiftLength = m_intShiftLength
End Property

Public Property Let ShiftLength(ByVal value As Integer)
    m_intShiftLength = value
End Property

Public Property Let Requirements(ByVal value As Variant)
   
    Dim intLoop As Integer
   
    m_intSlots = 1 + UBound(value)
    ReDim m_intCapacity(m_intSlots)
    ReDim m_intCombinedCapacity(m_intSlots)
    ReDim m_intDrops(m_intSlots)
    For intLoop = 0 To m_intSlots - 1
        m_intCapacity(intLoop) = value(intLoop)
    Next 'intLoop
   
End Property

Private Property Get HighestPriorityIndex() As Integer

    Dim intReturn As Integer
    Dim intMax As Integer
    Dim intLoop As Integer
   
    intMax = 0
    intReturn = -1
   
    For intLoop = 0 To m_intSlots - 1
        If m_intCombinedCapacity(intLoop) > intMax Then
            intMax = m_intCombinedCapacity(intLoop)
            intReturn = intLoop
        End If
    Next 'intLoop
   
    HighestPriorityIndex = intReturn

End Property

Private Sub AddShift(ByVal index As Integer)

    Dim intLoop As Integer
    Dim intLoop2 As Integer
   
    m_intDrops(index) = m_intDrops(index) + 1
    For intLoop = 0 To m_intShiftLength - 1
        m_intCapacity((index + intLoop) Mod m_intSlots) = m_intCapacity((index + intLoop) Mod m_intSlots) - 1
        If m_intCapacity((index + intLoop) Mod m_intSlots) >= 0 Then
            For intLoop2 = 1 - m_intShiftLength To 0
                m_intCombinedCapacity((index + intLoop + intLoop2 + m_intSlots) Mod m_intSlots) = m_intCombinedCapacity((index + intLoop + intLoop2 + m_intSlots) Mod m_intSlots) - 1
            Next 'intLoop2
        End If
    Next 'intLoop

End Sub

Private Sub TryRemoveShift(ByVal index As Integer)

    Dim intLoop As Integer
    Dim intLoop2 As Integer
   
    For intLoop = 0 To m_intShiftLength - 1
        If m_intCapacity((index + intLoop) Mod m_intSlots) >= 0 Then Exit Sub
    Next 'intLoop
   
    m_intDrops(index) = m_intDrops(index) - 1
    For intLoop = 0 To m_intShiftLength - 1
        m_intCapacity((index + intLoop) Mod m_intSlots) = m_intCapacity((index + intLoop) Mod m_intSlots) + 1
        If m_intCapacity((index + intLoop) Mod m_intSlots) >= 0 Then
            For intLoop2 = 1 - m_intShiftLength To 0
                m_intCombinedCapacity((index + intLoop + intLoop2 + m_intSlots) Mod m_intSlots) = m_intCombinedCapacity((index + intLoop + intLoop2 + m_intSlots) Mod m_intSlots) + 1
            Next 'intLoop2
        End If
    Next 'intLoop

End Sub

Public Sub Initialise()

    Dim intLoop As Integer
    Dim intLoop2 As Integer
   
    For intLoop = 0 To m_intSlots - 1
        m_intCombinedCapacity(intLoop) = 0
        For intLoop2 = 0 To m_intShiftLength - 1
            m_intCombinedCapacity(intLoop) = m_intCombinedCapacity(intLoop) + _
                m_intCapacity((intLoop + intLoop2) Mod m_intSlots)
        Next 'intLoop2
    Next 'intLoop

End Sub

Public Sub Process()

    Dim intIndex As Integer
    Dim intLoop As Integer
    Dim intLoop2 As Integer
    Dim intOverAllocation As Integer

    Call Initialise
   
    intIndex = HighestPriorityIndex
    Do While intIndex >= 0
        Call AddShift(intIndex)
        intIndex = HighestPriorityIndex
    Loop
   
    For intLoop = 0 To m_intSlots
        For intLoop2 = 1 To m_intDrops(intLoop)
            Call TryRemoveShift(intLoop)
        Next 'intLoop2
    Next 'intLoop

    intOverAllocation = 0
    For intLoop = 0 To m_intSlots - 1
        intOverAllocation = intOverAllocation - m_intCapacity(intLoop)
        frmMain.lisMain.AddItem "Slot " & intLoop & ": " & m_intDrops(intLoop) & " shifts start, overallocation this slot " & (-m_intCapacity(intLoop))
        'Debug.Print "Slot " & intLoop & ": " & m_intDrops(intLoop) & " shifts start, overallocation this slot " & (-m_intCapacity(intLoop))
    Next 'intLoop
    Debug.Print "Total overallocation: " & intOverAllocation & " slots"

End Sub


Thanks,
Lynnton
0
 
LVL 1

Author Comment

by:lynnton
ID: 12743194
muzzy2003,

your feedback it filling up.

Thanks,
Lynnton
0
 
LVL 1

Author Comment

by:lynnton
ID: 12751542
muzzy2003,

It seems I can't sqeeze the complete logic from the coding.

Does your theory works like...

-it get's all the needed people
-it get's the highest value
-from there it adds a 9 hour block schedules.

-after filling the top what does it choose next?

Thanks,
Lynnton
0
 
LVL 1

Author Comment

by:lynnton
ID: 12751583
muzzy2003,

I was reading up, I guess I didn't really understand this part (I know I've been asking lot's of question, sorry for that, I'am not a genius when it comes to logic and programming)...

___________________________________________________________________________
"which can be fairly efficiently solved using a "first fit descending" pattern -
you put into the knapsack at each step the biggest piece that will fit.
The analogous "move" in this algorithm is to drop the pieces into the 18 adjacent columns that,
at the time, have the greatest combined capacity. This means that you would start by dropping fairly centrally into the peak of lynnton's histogram."
___________________________________________________________________________


I think it didn't say how to do the next step..

Thanks,
Lynnton
0
 
LVL 16

Expert Comment

by:muzzy2003
ID: 12752716
Snowed under at the moment - will try to knock up a proper reply to the above this afternoon.
0
 
LVL 1

Author Comment

by:lynnton
ID: 12780696
muzzy2003,

I know you haven't abandoned me. I'm still here.

Thanks,
Lynnton
0
 
LVL 1

Author Comment

by:lynnton
ID: 12781152
muzzy2003,

My apology if i've been a pain to you.
I won't disturb this post anymore.

Thanks,
Lynnton
0
 
LVL 1

Author Comment

by:lynnton
ID: 12782967
muzzy2003,

Wanted to inform you i've place all the variables you transfer thier value to a log file

Public Sub log_buf(LogLine As String, LogFile As String)
    Dim TimeStamp As String
    TimeStamp = Format$(Date$, "ddddd") + " --- " + Format$(Time$, "ttttt") + " --- "
    Open LogFile For Append As #1
    Print #1, TimeStamp + LogLine
    Close #1
    MousePointer = vbDefault
End Sub

After investigating the logfile, I was now really lost :-(

Thanks,
Lynnton
0
 
LVL 16

Expert Comment

by:muzzy2003
ID: 12783063
Hi lynnton

I'm still here, don't worry. Just been a bit busy. Post a small section of your log file, and I'll have a go at annotating it for you to help you understand what's going on.
0
 
LVL 1

Author Comment

by:lynnton
ID: 12783374
muzzy2003,

This is just a small sample of a huge file, only two subs were taken, I'm affraid it will all get messy here..
If I could just understand how your theory works,
diagram below

    l
  l   l
l       l     <-----this is the required
 
  __
 l    l
 l    l
l      l        <---this is your theory

M i correct ? how did you center everything?

Thanks,
Lynnton

12/9/2004 --- 10:11:41 --- _HighestPriorityIndex_ intLoop## 11 m_intslots## 95
12/9/2004 --- 10:11:41 --- _HighestPriorityIndex_ If m_intCombinedCapacity(intLoop) > intMax Then ## 1420intMax## 1293
12/9/2004 --- 10:11:41 --- _HighestPriorityIndex_ If m_intCombinedCapacity(intLoop) > intMax Then ## 1420intMax## 1293
12/9/2004 --- 10:11:41 --- _HighestPriorityIndex_ intMax = m_intCombinedCapacity(intLoop)## 1420
12/9/2004 --- 10:11:41 --- _HighestPriorityIndex_ intReturn = intLoop## 11
12/9/2004 --- 10:11:41 --- _HighestPriorityIndex_ intLoop## 12 m_intslots## 95
12/9/2004 --- 10:11:41 --- _HighestPriorityIndex_ If m_intCombinedCapacity(intLoop) > intMax Then ## 1554intMax## 1420
12/9/2004 --- 10:11:41 --- _HighestPriorityIndex_ If m_intCombinedCapacity(intLoop) > intMax Then ## 1554intMax## 1420
12/9/2004 --- 10:11:41 --- _HighestPriorityIndex_ intMax = m_intCombinedCapacity(intLoop)## 1554
12/9/2004 --- 10:11:41 --- _HighestPriorityIndex_ intReturn = intLoop## 12
12/9/2004 --- 10:11:41 --- _HighestPriorityIndex_ intLoop## 13 m_intslots## 95
12/9/2004 --- 10:17:48 --- _HighestPriorityIndex_ intmax = 1926 intReturn= 18 m_intslots= 96
12/9/2004 --- 10:17:48 --- _HighestPriorityIndex_ intmax = 1926 intReturn= 18 m_intslots= 96
12/9/2004 --- 10:17:48 --- _HighestPriorityIndex_ intmax = 1926 intReturn= 18 m_intslots= 96
12/9/2004 --- 10:17:48 --- _HighestPriorityIndex_ intmax = 1926 intReturn= 18 m_intslots= 96
12/9/2004 --- 10:17:48 --- _HighestPriorityIndex_ intmax = 1926 intReturn= 18 m_intslots= 96
12/9/2004 --- 10:17:48 --- _HighestPriorityIndex_ intmax = 1926 intReturn= 18 m_intslots= 96
12/9/2004 --- 10:17:48 --- _HighestPriorityIndex_ intmax = 1926 intReturn= 18 m_intslots= 96
12/9/2004 --- 10:17:48 --- _HighestPriorityIndex_ intmax = 1926 intReturn= 18 m_intslots= 96
12/9/2004 --- 10:17:48 --- _HighestPriorityIndex_ intmax = 1926 intReturn= 18 m_intslots= 96
0
 
LVL 1

Author Comment

by:lynnton
ID: 12784878
muzzy2003,

Five years from now, I wanna be just like you.
Wanted you to know this.

Thanks,
Lynnton
0
 
LVL 1

Author Comment

by:lynnton
ID: 12790410
muzzy2003,

Is it okay if I ask other experts to help me understand how your code works?

Thanks,
Lynnton
0
 
LVL 1

Author Comment

by:lynnton
ID: 12790999
muzzy2003,

Now I understand some of it..
but it's not very clear picture though...if you could enlighten some of the parts...

Thanks,
Lynnton

Public Sub Process()

    Dim intIndex As Integer
    Dim intLoop As Integer
    Dim intLoop2 As Integer
    Dim intOverAllocation As Integer

    Call Initialise          <---------------------------this one place the required into an array
   
    intIndex = HighestPriorityIndex <-------------------this one gets the highest value in the array
    Do While intIndex >= 0            <-----------loop thru all the values of the required   1,2,1,1,1
   
        Call AddShift(intIndex)        <--------------------not sure how you create schedules
        intIndex = HighestPriorityIndex       <-----------------------you check again for the highest
    Loop
   
    For intLoop = 0 To m_intSlots      <---------------m_intSlots is the number of items in required? so 48 for 1 day
        For intLoop2 = 1 To m_intDrops(intLoop)               <---------------------------what is intDrops ?
            Call TryRemoveShift(intLoop)                   <-----------------now try to remove shift ?? why ?
        Next 'intLoop2
    Next 'intLoop

intOverAllocation = 0
    For intLoop = 0 To m_intSlots - 1
        intOverAllocation = intOverAllocation - m_intCapacity(intLoop)
        frmMain.lisMain.AddItem "Slot " & intLoop & ": " & m_intDrops(intLoop) & " shifts start, overallocation this slot " & (-m_intCapacity(intLoop))
        Debug.Print "Slot " & intLoop & ": " & m_intDrops(intLoop) & " shifts start, overallocation this slot " & (-m_intCapacity(intLoop))
    Next 'intLoop
    Debug.Print "Total overallocation: " & intOverAllocation & " slots"

End Sub
0
 
LVL 16

Expert Comment

by:muzzy2003
ID: 12792474
First, here is the code with some comments:

    ' Create the arrays containing the initial shift requirements
    Call Initialise
   
    ' Retrieve the index of the start time which has the greatest combined
    ' requirement over the following nine hours - if everything is allocated,
    ' this function call will return -1 and the loop will exit.
    intIndex = HighestPriorityIndex
   
    ' Loop while there is still at least one slot still requiring a shift or
    ' more to be allocated.
    Do While intIndex >= 0
   
        ' Add one shift starting at this highest priority time. This function
        ' call recalculates the values in the arrays as well as allocating the
        ' shift, so that ...
        Call AddShift(intIndex)
       
        ' ... this function call will then retrieve the new highest priority
        ' time slot (might be the same time, might not).
        intIndex = HighestPriorityIndex
       
    Loop
   
    ' It is possible that there are some redundant shifts allocated, as the
    ' algorithm isn't perfect. To remove these, we loop through the starting
    ' times and just attempt to remove all the shifts. TryRemoveShift will
    ' only remove a shift if this doesn't lead to underallocation at any
    ' point during its duration. it is entirely possible that this code block
    ' won't achieve anything. So, for each start time ...
    For intLoop = 0 To m_intSlots
        ' ... and for each shift allocated at that time ...
        For intLoop2 = 1 To m_intDrops(intLoop)
            ' ... we try to remove that shift; the function will prevent this
            ' if it shouldn't happen.
            Call TryRemoveShift(intLoop)
        Next 'intLoop2
    Next 'intLoop

Next, here is an explanation of how it works. Here is a bar graph (on its side) of requirements. I have shrunk everything, and let's go for 4 slot shifts not 18 for clarity. The numbers in brackets are the required number of shifts for (a) that slot, and (b) all the slots starting there for one shift duration. Note that the last ones wrap round to include the first ones again. First, check you are OK with the values here.

00 xx (2, 11)
01 xx (2, 15)
02 xxx (3, 22)
03 xxxx (4, 35)
04 xxxxxx (6, 52)
05 xxxxxxxxx (9, 61)
06 xxxxxxxxxxxxxxxx (16, 61)
07 xxxxxxxxxxxxxxxxxxxxx (21, 49)
08 xxxxxxxxxxxxxxx (15, 30)
09 xxxxxxxxx (9, 16)
10 xxxx (4, 8)
11 xx (2, 6)
12 x (1, 6)
13 x (1, 8)

Now, the algorithm looks for the highest second number - this is 61, coming at two positions in the middle. In this case, it takes the first one, so the highest priority position is 05. We add a slot there - I'll indicate this by putting @ instead of x. Here is the new graph with the numbers adjusted - the effect of calling the AddShift method.

00 xx (2, 11)
01 xx (2, 15)
02 xxx (3, 22)
03 xxxx (4, 35)
04 xxxxxx (6, 52)
05 @xxxxxxxx (8, 57)
06 @xxxxxxxxxxxxxxx (15, 58)
07 @xxxxxxxxxxxxxxxxxxxx (20, 47)
08 @xxxxxxxxxxxxxx (14, 29)
09 xxxxxxxxx (9, 16)
10 xxxx (4, 8)
11 xx (2, 6)
12 x (1, 6)
13 x (1, 8)

Now, the highest priority is the 58 at slot 06, so we add another shift there:

00 xx (2, 11)
01 xx (2, 15)
02 xxx (3, 22)
03 xxxx (4, 35)
04 xxxxxx (6, 52)
05 @xxxxxxxx (8, 57)
06 @@xxxxxxxxxxxxxx (14, 54)
07 @@xxxxxxxxxxxxxxxxxxx (19, 44)
08 @@xxxxxxxxxxxxx (13, 27)
09 @xxxxxxxx (8, 15)
10 xxxx (4, 8)
11 xx (2, 6)
12 x (1, 6)
13 x (1, 8)

Then we add a shift at 05, since 57 is the highest:

00 xx (2, 11)
01 xx (2, 15)
02 xxx (3, 22)
03 xxxx (4, 35)
04 xxxxxx (6, 52)
05 @@xxxxxxx (7, 53)
06 @@@xxxxxxxxxxxxx (13, 51)
07 @@@xxxxxxxxxxxxxxxxxx (18, 42)
08 @@@xxxxxxxxxxxx (12, 26)
09 @xxxxxxxx (8, 15)
10 xxxx (4, 8)
11 xx (2, 6)
12 x (1, 6)
13 x (1, 8)

Then at 05 again for the 53:

00 xx (2, 11)
01 xx (2, 15)
02 xxx (3, 22)
03 xxxx (4, 35)
04 xxxxxx (6, 52)
05 @@@xxxxxx (6, 49)
06 @@@@xxxxxxxxxxxx (10, 48)
07 @@@@xxxxxxxxxxxxxxxxx (17, 40)
08 @@@@xxxxxxxxxxx (11, 25)
09 @xxxxxxxx (8, 15)
10 xxxx (4, 8)
11 xx (2, 6)
12 x (1, 6)
13 x (1, 8)

Then at 04 for the 52:

00 xx (2, 11)
01 xx (2, 15)
02 xxx (3, 22)
03 xxxx (4, 35)
04 @xxxxx (5, 48)
05 @@@@xxxxx (5, 46)
06 @@@@@xxxxxxxxxxx (9, 46)
07 @@@@@xxxxxxxxxxxxxxxx (16, 39)
08 @@@@xxxxxxxxxxx (11, 25)
09 @xxxxxxxx (8, 15)
10 xxxx (4, 8)
11 xx (2, 6)
12 x (1, 6)
13 x (1, 8)

And so on. You can see that the allocated shifts are following the same sort of shape as the requirements, growing quickest towards the peak.
0
 
LVL 1

Author Comment

by:lynnton
ID: 12792641
muzzy2003,

I admit I'm slow and dumb !!!
What is (b) ?
"and (b) all the slots starting there for one shift duration. Note that the last ones wrap round to include the first ones again. First, check you are OK with the values here."

I know (a) is the required number of persons needed.
I'm glad your back :-)

Thanks,
Lynnton
0
 
LVL 16

Expert Comment

by:muzzy2003
ID: 12792673
Look at the first bar graph, row numbered 05. If you start a four slot shift here, then it covers rows 05, 06, 07, 08 (think one hour slots, four hour shifts). That means it covers this bit:

05 xxxxxxxxx (9, 61)
06 xxxxxxxxxxxxxxxx (16, 61)
07 xxxxxxxxxxxxxxxxxxxxx (21, 49)
08 xxxxxxxxxxxxxxx (15, 30)

The 61 at the end of row 05 is the total of the (a) values for 05, 06, 07 and 08: 9 + 16 + 21 + 15 = 61. This means that it is the total requirement for the period that a shift starting there would cover. Make any more sense?
0
 
LVL 1

Author Comment

by:lynnton
ID: 12793068
muzzy2003,

I bit more than I can chew !!!

Are you a god of theory ??

Sad to say this is way out of my leage (coding and theory)..but i will see to it that i finish what you have started in the future(creating breaks, and everything)  and post the finish product here.

I can't thank you enough for openning this approach. I'll try to find a quick fix for my approach "add as needed".

Thank you very much for your time. When I get a change to goto London, I'll come and visit you.

Lynnton
0
 
LVL 1

Author Comment

by:lynnton
ID: 12793145
muzzy2003,

By the way, do you want additional points?
I'll post your name if that's okay with you?

Thanks,
Lynnton
0
 
LVL 16

Expert Comment

by:muzzy2003
ID: 12793165
No objections at all. Hope you get it all working, and keep asking when you get stuck.
0
 
LVL 1

Author Comment

by:lynnton
ID: 12799270
muzzy2003,

Why did we subtract 1 to the position where we got the highest priority? this is concerning the diagram.
And do we also subtract 1 if the shifts were 9 hours ?

Thanks,
Lynnton
0
 
LVL 16

Expert Comment

by:muzzy2003
ID: 12799574
Most of the -1s are because the arrays are 0 based - the first index in them is 0 and not 1, and so the last index is count - 1 not just count. It's not related to the lengths of the shifts or anything else.
0
 
LVL 1

Author Comment

by:lynnton
ID: 12849776
Hi muzzy2003,

Sorry to bother, but you're the only one I know who can crack this nut.

Finally finish the scheduling program. (add as needed theory)

Turns out to much excess.

I think, this is because of improper approach I made to handle incomplete schedules (this are schedules which has less than 5 working days).

after running the program there are schedules with only 2 working days, 3 working days etc....

We have fixed this problem by relating two schedules to form a complete schedule (5 working days)
( BETWEEN remember -6 and 6)

--Problem now there are still schedules that can't be related.
--so I used your code to relate 4 days out of the remainder.
--then relate 3 days, 2 days.

after relating those 4,3,2 days. I decided to add the missing days to complete those schedules.
hence I added a whole lot of unwanted days.

Please help me sort on how to handle incomplete schedules...

Thanks,
Lynnton

0
 
LVL 1

Author Comment

by:lynnton
ID: 12850367
muzzy2003,

the total incomplete schedules that I have is 207  (less than 5 days)
the total complete schedules that I have is 225   (5 days)

Thanks,
Lynnton
0
 
LVL 1

Author Comment

by:lynnton
ID: 12856630
muzzy2003,

I read-up, seems i'm really slow on catching what you've just unrevealed.

after reading, now I understand very clearly.

I'm dumping everything i've done and use your theory.

one thing that bothers me, I don't see any redundant shifts..what are redundant shifts?

--here the way I planed on finishing your KICK-ASS GENIUS and everything nice theory..

basically the result will show up like this.

day    start    break         stop
mon 10:00    12:30        14:00    
tue   11:00    13:00        15:00

this will be like 1000 records...

-then start creating complete schedules.  I'll get back to you in 2 days. (finishing this)


Thanks,
Lynnton
0
 
LVL 1

Author Comment

by:lynnton
ID: 12898262
muzzy2003,

One question, in your diagram, you recomputed for those shift that you have added, what about before the shift started?
logically those should also change...

diagram 1

00 xx (2, 11)
01 xx (2, 15)
02 xxx (3, 22)
03 xxxx (4, 35)
04 xxxxxx (6, 52)
05 xxxxxxxxx (9, 61)
06 xxxxxxxxxxxxxxxx (16, 61)
07 xxxxxxxxxxxxxxxxxxxxx (21, 49)
08 xxxxxxxxxxxxxxx (15, 30)
09 xxxxxxxxx (9, 16)
10 xxxx (4, 8)
11 xx (2, 6)
12 x (1, 6)
13 x (1, 8)

Now, the algorithm looks for the highest second number - this is 61, coming at two positions in the middle. In this case, it takes the first one, so the highest priority position is 05. We add a slot there - I'll indicate this by putting @ instead of x. Here is the new graph with the numbers adjusted - the effect of calling the AddShift method.


diagram 2

00 xx (2, 11)
01 xx (2, 15)           <-----------this should also be resomputed ?
02 xxx (3, 22)           <-----------this should also be resomputed ?
03 xxxx (4, 35)           <-----------this should also be resomputed ?
04 xxxxxx (6, 52)           <-----------this should also be resomputed ?
05 @xxxxxxxx (8, 57)
06 @xxxxxxxxxxxxxxx (15, 58)
07 @xxxxxxxxxxxxxxxxxxxx (20, 47)
08 @xxxxxxxxxxxxxx (14, 29)
09 xxxxxxxxx (9, 16)
10 xxxx (4, 8)
11 xx (2, 6)
12 x (1, 6)
13 x (1, 8)

Thanks,
Lynnton
0
 
LVL 16

Expert Comment

by:muzzy2003
ID: 12906296
Yes, the second number in each case should be recomputed - you're right.
0
 
LVL 1

Author Comment

by:lynnton
ID: 12907117
muzzy2003,

Wishing you a happy new year for 2005 !!!
____________________________________________

Amazing i've done what your theory is, generated only 16% of excess (that's like the lowest ever).
I've place the table to a multi dimentional array, just like what you did, the speed is outstanding, do you feel the need for speed?  :-)

Sadly, i'm stuck on how to handle the results. since we have create one schedule with only one day in mind.
This means we created single working day per record generated.

forecastsched table
___________________________________________________________________________________
requiredid      monday      tuesday      wednesday      thursday      friday      saturday      sunday
19      Y                                    
19      Y                                    
19      Y                                    
19      Y                                    
19      Y                                    
19      Y                                    
19      Y                                    
19            Y                              
19      Y                                    
19            Y                              
19      Y                                    
19            Y                              
19      Y                                    
19            Y                              
19            Y                              
19      Y                                    
19            Y                              
19      Y                                    
20      Y                                    
19            Y                              
19            Y                              
20      Y                                    
20      Y                                    
19            Y                              
19            Y                              
20      Y                                    
19                  Y                        
20      Y                                    
19            Y                              
19                  Y                        
19            Y                              
20      Y                                    
19                  Y                        
19            Y                              
20      Y                                    
19                  Y                        
19            Y                              
20      Y                                    
19                        Y                  
19                  Y                        
19            Y                              
20      Y                                    
19                        Y                  
_________________________________________________________________
Below is the total number per day that have tag as 'Y'
monday    284
tuesday    259
wenesday 251
thursday   249
friday       245
saturday   126
sunday       89

What would be the most efficient way to combined 5 of those record to get 1 complete schedule?
In the end we need to add some bogus schedules inorder to finish the result (hope the excess don't jump that high).
 
Thanks,
Lynnton
0
 
LVL 1

Author Comment

by:lynnton
ID: 12907228
muzzy2003,

Base on the stats per day, monday shows to be the highest, if we can group this first, we could limit adding of unneccessary schedules?
i.e.
get all records with monday, group those with same time schedules (same requiredid) in order to make 5 working days.
next
get all records with tuesday, group those with same time schedules (same requiredid) in order to make 5 working days.
next
.....
next
.....

is this the right approach? or this will just be going in circles?

Thanks,
Lynnton
0
 
LVL 1

Author Comment

by:lynnton
ID: 12911335
muzzy2003,

We have an array called "scheduleArr".

scheduleArr(47 x 7) - this is the big picture.   "shift starts at"   :-)
_____________________________________________________________________
ID     mo     tu     we     th     fr     sa     su
1     0     0     0     0     0     0     0
2     0     0     0     0     0     0     0
3     0     0     0     0     0     0     0
4     0     0     0     0     0     0     0
5     0     0     0     0     0     0     0
6     0     0     0     0     0     0     0
7     0     0     0     0     0     0     0
8     2     0     0     0     0     0     1
9     0     1     1     1     2     2     1
10     1     0     1     0     0     0     0
11     1     0     1     1     1     2     0
12     2     2     1     2     2     0     0
13     3     1     2     3     3     1     1
14     5     5     4     5     5     4     1
15     4     10     5     9     4     0     1
16     18     4     15     5     14     6     3
17     25     34     27     33     22     4     2
18     27     12     15     13     15     10     3
19     33     35     30     26     33     13     10
20     35     34     32     33     30     10     6
21     23     23     19     21     22     17     5
22     22     20     15     15     16     5     8
23     14     22     27     17     5     6     6
24     3     3     9     17     13     1     3
25     15     13     5     0     12     3     3
26     7     0     5     1     6     8     5
27     8     2     0     0     0     0     2
28     11     4     7     14     2     3     2
29     1     11     2     0     8     2     2
30     1     5     0     13     13     0     5
31     0     0     2     0     0     3     0
32     0     0     2     0     0     0     4
33     0     0     0     0     0     0     0
34     0     0     0     0     0     2     0
35     0     0     0     0     0     0     0
36     0     0     0     0     0     5     2
37     0     0     0     0     0     6     6
38     1     2     3     5     2     0     0
39     15     6     9     7     9     4     4
40     7     4     0     0     1     1     0
41     0     6     12     2     0     5     0
42     0     0     0     6     0     0     2
43     0     0     0     0     1     0     0
44     0     0     0     0     1     3     1
45     0     0     0     0     0     0     0
46     0     0     0     0     0     0     0
47     0     0     0     0     0     0     0
48     0     0     0     0     3     0     0

ID places a big role..i've use auto number representing the time.
1 = 00:00
2 = 00:30
3 = 01:00
4 = 01:30        
....every half hour until 48 = 23:30

hope this help.

Thanks,
Lynnton
0

Featured Post

NFR key for Veeam Agent for Linux

Veeam is happy to provide a free NFR license for one year.  It allows for the non‑production use and valid for five workstations and two servers. Veeam Agent for Linux is a simple backup tool for your Linux installations, both on‑premises and in the public cloud.

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

In part one, we reviewed the prerequisites required for installing SQL Server vNext. In this part we will explore how to install Microsoft's SQL Server on Ubuntu 16.04.
This shares a stored procedure to retrieve permissions for a given user on the current database or across all databases on a server.
This videos aims to give the viewer a basic demonstration of how a user can query current session information by using the SYS_CONTEXT function
Via a live example, show how to setup several different housekeeping processes for a SQL Server.
Suggested Courses

840 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question