Duty Scheduling

Ok so the OC made my fellow disruptee come up with a WITS project, and we thought it'd be cool to do an automated duty scheduler for guard duty and COS. Really not an easy problem as the guy who used to do the scheduling spent quite a bit of time juggling duties around.

So let's break down the problem:
We want an algorithm that takes in the monthly guard duty schedule, which is a list of the tuple (date, number of guards), and a list of the people in my company and their points (person, points), and outputs the guard duty assignment, which is a list of the tuple (date, guard1, guard2, ... guardn), subject to the following constraints:

1. Fairness be maintained between the people in the company, to be achieved by point equalisation, where Mon-Thurs duties are worth 1 point, Fridays 2, and weekends 3 points.
2. There needs to be one COS everyday.
3. No one is to serve consecutive weekends
4. No one is to serve duties on 2 consecutive days (COS and guard included)

So we have here a scheduling problem, which I guess could reduce to a constraint satisfaction problem. On googling, typical solutions involve genetic algos, taboo search, and various optimisation techniques to find the global minimum, which satisfies the constraints, Not sure if that's going to be doable.

So currently I've thought of an idea which might serve as a good starting point.
We have 2 sorted lists, one of the duties of the month, sorted highest to lowest by their point-values, and the other, of the people in my company sorted lowest to highest by their number of points.
So we simply iterate through the duties of the month, from the head of the list, assigning the guy at the head of the people list to the duty if it satisfies the constraints. Once the duty has been assigned, we recalculate his points and reinsert him back into the list. If the constraints aren't satisfied, we move on to the next guy.
A simple greedy algorithm, but one that I suspect will have problems satisfying all the constraints, while filling up all the guard duties.

Another thing I've considered is randomisation with iteratively improving swaps to iron out all the conflicting duties.

What I really need now is some algorithmic meat, or some simliar solution that has already been implemented, and to decide whether the algorithm will necessarily obtain the best solution, or just be best effort, leaving the human to sort out the possible conflicts.

Any suggestions out there?

And does anyone out there know if it's better to use VB or Java for this? I'm developing for camp use so perhaps being able to compile into an executable might be a better idea. But oh man VB's a bloody ugly language. Or is there some other option?