The peak load minimization problem in cyclic production

The objective of this study is to determine a production schedule for a set of jobs so as to minimize the peak load for the entire planning horizon given the production duration and the cyclic frequencies of the jobs. We refer to this problem as the peak load minimization problem (PLMP). An efficient heuristic, viz. Proc. PLMP, is proposed to solve such class of problems. There are two parts for the Proc. PLMP: a greedy procedure that secures an initial production schedule and a schedule smoothing procedure that performs a local search to reduce the maximal load. Numerical experiments verify that Proc. PLMP is efficient, since its run time is of cubic order of the problem size, i.e., it is approximately an O(n3) algorithm. A major application of Proc. PLMP is to test the feasibility of a given set of a solution for the Economic Lot Scheduling Problem using the extended basic period approach.