Personnel planning problem (Clark and Hastings [1977]). A construction company's work schedule on a certain site requires the following number of skilled personnel, called steel erectors, in the months of March through August:
Personnel work at the site on the monthly basis. Suppose that three steel erectors are on the site in February and three steel erectors must be on site in September. The problem is to determine how many workers to have on site in each month in order to minimize costs, subject to the following conditions:
Transfer costs. Adding a worker to this site costs $100 per worker and redeploying a worker to another site costs $160.
Transfer rules. The company can transfer no more than three workers at the start of any month, and under a union agreement, it can redeploy no more than one-third of the current workers in any trade from a site at the end of any month.
Shortage time and overtime. The company incurs a cost of $200 per worker per month for having a surplus of steel erectors on site and a cost of $200 per worker per month for having a shortage of workers at the site (which must be made up in overtime).
Overtime cannot exceed 25 percent of the regular work time.
Formulate this problem as a shortest path problem and solve it. (Hint: Give a dynamic programming-based formulation and use as many nodes for each month as the maximum possible number of steel erectors.)