What Voicemail system and version do you have in the system?
Have you reviewed the Feature Reference guide? If you don't have a copy, one can be downloaded for free from: support.avaya.com.
Since you mention calls are delivered via PRI service, then each department has a DID number assigned for that purpose? You will need that information for programming. Even though the departments have different business hours, are they fixed? Please provide more detail so any of us can respond to your request.
....JIM....