[dandon]

I am triying to figure out how can i make a roster application in java.
I am not asking to give me code or something but i need some ideas on how shall i do this.
i am thinking as inputting the availability for each worker and then buildthe roster from the availabilities. i am not sure how the logic of the programm should be so i am trying to get help.

thanks

[Gloin]

This is more of an algorithmic question I guess. Much like scheduling processes.

It's like, you want every timeslot to be covered by k workers while one worker can only work for t hours per week and he cannot work in adjacent time slots, something like that?

Start by writing down the constraints, here as well so we know what we have to work with, maybe we can help you with ideas.

[dandon]

Gloin, on 15 Jan, 2009 - 07:47 AM, said:

This is more of an algorithmic question I guess. Much like scheduling processes.

It's like, you want every timeslot to be covered by k workers while one worker can only work for t hours per week and he cannot work in adjacent time slots, something like that?

Start by writing down the constraints, here as well so we know what we have to work with, maybe we can help you with ideas.

yes something like that, there are 2 shifts in every day morning and evening, in every shift there have to be k workers. every worker must atleast be given 4 shifts and the rest are spread randomly.

i dont know exactly the algorithm that i need to use inorder to fill the slots. i dont know exactly were to start from, and what do i need exactl in my hand. maby if i have this idea cleared i can run with my code then.

[Gloin]

Under the assumption that a worker can't work an evening shift if he worked the morning shift and also he can't work the morning shift if he worked the previous evening, this is a graph problem.
Let every shift be represented be a vertex and let an edge between two vertex represent that they would 'overlap'.

The way to solve the problem can depend on the resources.
1* Is any worker available for any timeslot?
2* Can one worker work any number of shifts (max: number of shifts / 2)
3* If there are k workers, are there more than 4*k shifts? (If not the problem can't be solved)

If you calculate the number of shifts divided by the number of workers, you can simple round the number down and start filling every shift with that many workers until every shift has equally many workers this way you won't get overlaps. Th remaining workers can be scattered among the shifts. Just see if a worker can work shift i (not working shift i-1 or i+1), if he can't you try with the next worker.

This is a greedy algorithm, it may not be optimal.

[dandon]

Gloin, on 15 Jan, 2009 - 08:40 AM, said:

Under the assumption that a worker can't work an evening shift if he worked the morning shift and also he can't work the morning shift if he worked the previous evening, this is a graph problem.
Let every shift be represented be a vertex and let an edge between two vertex represent that they would 'overlap'.

The way to solve the problem can depend on the resources.
1* Is any worker available for any timeslot?
2* Can one worker work any number of shifts (max: number of shifts / 2)
3* If there are k workers, are there more than 4*k shifts? (If not the problem can't be solved)

If you calculate the number of shifts divided by the number of workers, you can simple round the number down and start filling every shift with that many workers until every shift has equally many workers this way you won't get overlaps. Th remaining workers can be scattered among the shifts. Just see if a worker can work shift i (not working shift i-1 or i+1), if he can't you try with the next worker.

This is a greedy algorithm, it may not be optimal.

there are 14 shift in every week, 2 for everyday. i dont have the restriction as such just given this task to do, so i can make the restriction favourable for me to make it easy to code.

i am a beginer in java and dont know exactly how to work with vertex.

[Gloin]

In that case it's probably simpler than I'm describing.

If you have k workers, let half of them work the first shift, the other half works the second shift, first half works the third shift and so on.
If there are no restrictions you might as well make it easy on yourself.

or, if it has to be exactly k workers in a shift..

first k workers work the first shift, next k workers take the next shift, next k take the third and if you run out of workers you start over from the first worker. (Use modulo operation here)

This post has been edited by Gloin: 15 January 2009 - 10:09 AM

[dandon]

Gloin, on 15 Jan, 2009 - 09:05 AM, said:

In that case it's probably simpler than I'm describing.

If you have k workers, let half of them work the first shift, the other half works the second shift, first half works the third shift and so on.
If there are no restrictions you might as well make it easy on yourself.

or, if it has to be exactly k workers in a shift..

first k workers work the first shift, next k workers take the next shift, next k take the third and if you run out of workers you start over from the first worker. (Use modulo operation here)

can u give me an example on how CAn i begin the code?

[Gloin]

Well, I'll give you some Pseudo-code

Let there be m workers (ex, m = 8), every worker is represented by a number between 0 and m-1
So we got workers 0, 1, 2, 3, 4, 5, 6 & 7

Next, you have the roster which is represented by a 2-dimensional (int) array with 14 * k elements because you have 14 timeslots and every timeslot needs k workers. Call the array Roster[14][k]. (for the example, let k=3, I.e 3 workers per timeslot.

In Roster[0][0] you put worker 0.
In Roster[0][1] you put worker 1.
In Roster[0][2] you put worker 2.

Now you covered the first timeslot.. You continue with..

In Roster[1][0] you put worker 3.
In Roster[1][1] you put worker 4.
In Roster[1][2] you put worker 5.

Then

In Roster[2][0] you put worker 6.
In Roster[2][1] you put worker 7.
You just ran out of workers so you start over from 0 but instead of using if-statements and crap like that..
In Roster[2][2] you put worker (8%m). m=8 so 8%8 = 0, this is what you wanted.

Then

In Roster[3][0] you put worker (9%m). 9%8 = 1
In Roster[3][1] you put worker (10%m). 10%8 = 2
In Roster[3][2] you put worker (11%m). 11%8 = Well have a guess.

And so on..

You can find a mathematical formula to assign every position in the array using just one line of code inside a for-loop.

for (int i = 0; i < 14*k; i++)
  Roster[i / k][i % k] = i % m;

It's magic!

This post has been edited by Gloin: 15 January 2009 - 10:47 AM