We have done something similar but with the LSF scheduler. I do not see why this wouldn't work for the OS Scheduler. All departments are associated to a group in metadata. We have set up ACT's for each. Then we created multiple scheduling servers, each with their own authentication domain and protected by an ACT to limit visibility to that one department. Now when one creates a flow the drop-down for scheduling server will only show the one for his or her department.
Using groups we are also able to assign a specific batch user to each department. That batch user has an account specified for the authentication domain belonging to the specific departmental scheduling server.
In case one would ask, we have chosen not to employ separate logical server contexts for each department. It's a grid install and grid option sets, constructs as above, ACT's (and corresponding ACL's on file system) allow us to do without.
Hope this helps,
-- Jan.