Scheduling concurrent production over a finite planning horizon: polynomially solvable cases

The paper analyzes a manufacturing system made up of one workstation which is able to produce concurrently a number of product types with controllable production rates in response to time-dependent product demands. Given a finite planning horizon, the objective is to minimize production cost, which is incurred when the workstation is not idle and inventory and backlog costs, which are incurred when the meeting of demand results in inventory surpluses and shortages. With the aid of the maximum principle, optimal production regimes are derived and continuous-time scheduling is reduced to a combinatorial problem of sequencing and timing the regimes. The problem is proved to be polynomially solvable if demand does not exceed the capacity of the workstation or it is steadily pressing and the costs are “agreeable”.

Scope and purpose

Efficient utilization of modern flexible manufacturing systems is heavily dependent on proper scheduling of products throughout the available facilities. Scheduling of a workstation which produces concurrently a number of product types with controllable production rates in response to continuous, time-dependent demand is under consideration. Similar to the systems considered by many authors in recent years, a buffer with unlimited capacity is placed after the workstation for each product type. The objective is to minimize inventory storage, backlog and production costs over a finite planning horizon. Numerical approaches are commonly used to approximate the optimal solution for similar problems. The key contribution of this work is that the continuous-time scheduling problem is reduced to a combinatorial problem, exactly solvable in polynomial time if demand does not exceed the capacity of the workstation or the manufacturing system is organized such that the early production and storage of a product to reduce later backlogs are justified.