PRODUCTION SCHEDULING ON PARALLEL MACHINES SUBJECT TO STAIRCASE DEMANDS

Given is a set of m unrelated machines working in parallel and a set of n independent products which have to be produced on these machines using p additional resources. A machine cannot work on more than one product at a time but a product can simultaneously be produced on different machines. For each triple (machine, product, resource) productivity per time unit is given. The objective is to minimize the total penalty following from deviations above and below production plans. The sum of machine setup costs is considered as a secondary performance measure. The problem is solved by an extension of the two phase method, Phase 1 consists in solving an LP problem and Phase 2 is the construction of the schedule which reduces to a sequence of compatible flow problems.