Zero-one quadratic programming algorithm for resources leveling of manufacturing process schedules

It is necessary in industrial plant construction scheduling to minimize fluctuation or the maximum peak value of daily resoruces amount which is calculated as the summation of daily resources for each process. Minimization of fluctuation or the maximum peak value corresponds to leveling the pile of resources. In order to perfrom this resource leveling, the authors need to decide an objective function which is a monotone function that simply increases with the degree of resources leveling, and then they need to solve the optimization problem by fixing processes’ start dates while minimizing the objective function. Industrial plant construction is, however, in many cases a large scale scheduling with a whole period of more than 1000 days and more than 100 processes, so it is very difficult to obtain a global optimization solution. In this research the authors have developed an algorithm which solves a large scale optimization problem to level necessary resources. This algorithm can quickly search for a good suboptimal solution near the global optimal solution of a 0-1 quadratic programming problem which we modeled the resources leveling as. The algorithm searches by repeating a pivot operation using variable selection rules for resources leveling. The authors applied this algorithm to large scale scheduling for an actual plant construction schedule and successfully obtained the practical suboptimal solution within a few minutes. The result suggested that the algorithm is practicable for resources leveling of large scale construction scheduling. [In Japanese.]