I am running a small office for a while and need to do some scheduling. Employees have widely varying availability (part time environment), and there are certain times of the day where I need certain numbers of people there. I also want to impose constraints as far as how many hours each person works. I have looked, and perhaps I haven't been searching well, but I haven't found anything for free.
Which program(s) can perform this task?
You may want to investigate phpScheduleIt.
What is phpScheduleIt?
phpScheduleIt is a web application that attempts to solve the problem of scheduling and managing resource utilization. It provides a permissions-based calendar that allows users to self-register and reserve resources and the tools to manage those reservations.
Some typical applications are conference room, equipment, or work shift scheduling.
This type of modelling is an Operations Research domain. You could construct your model and solve it for example the Solver in excel (provided your problem was small enough). Larger problems (depending on number of variables in them) are harder to solve and I wouldn't expect there to be a free solver anywhere.
These situations tend to be very client specific and are generally solved using customized models so you might have a hard time finding one. (I am working on a commercional one right now to be completely honest).