Fundamental lemmas for the determination of optimal control strategies for a class of single machine family scheduling problems
This work provides theoretical tools for solving a specific class of scheduling problems, but it is incremental as it extends existing dynamic programming methods to a particular problem setting.
The paper presents four lemmas that form the theoretical foundation for determining optimal control strategies in single machine family scheduling problems with sequence-dependent batch setup, controllable processing times, and generalized due-dates. The lemmas are used in a dynamic programming-based constructive procedure to derive optimal decisions as functions of system state, with two examples illustrating the approach.
Four lemmas, which constitute the theoretical foundation necessary to determine optimal control strategies for a class of single machine family scheduling problems, are presented in this technical report. The scheduling problem is characterized by the presence of sequence-dependent batch setup and controllable processing times; moreover, the generalized due-date model is adopted in the problem. The lemmas are employed within a constructive procedure (proposed by the Author and based on the application of dynamic programming) that allows determining the decisions which optimally solve the scheduling problem as functions of the system state. Two complete examples of single machine family scheduling problem are included in the technical report with the aim of illustrating the application of the fundamental lemmas in the proposed approach.