Hard to say what to do for such a general question.
In general I want to start with what outputs will be required - schedule yes, but also staff hours for pay, and staff information for statistics such as average hours per staff member per week, max and min hours, sickness hours etc.
For the sites - invoice information - number of satff supplied - number of hours worked on each shift, extra hours provided, overhead/management cost if invoiced separately.
Then look at the input data - staff-location-shift-hours-vacation-sickness - rates of pay. Input data should be as continuous as possible, so that it can easily be summarized - so one input for scheduling - one column per day throughout the year. Date in first row to allow summarizing by period. In this case day of week in second row to allow calculations of rates based on weekends.
A second input worksheet might hold common data such as staff names, rates of pay, site names, site requirements. Shift start and finish times.
Finally create summary sheets that draw on the input data and deliver the outputs required.
AND - don't forget to have a data backup plan that everyone follows - the cost to the business of losing this information will likely be significant.
Remember that off-site storage may be appropriate - if there is a fire or a flood and the data including backups is lost, then it's just as bad as not having any backups.