On a New Class of Combinatoric Optimizers for Multi-Product Single-Machine Scheduling

Many people have proposed objective functions, or optimizers, which guide one to schedule a multi-product single stage production system. In this paper we present a whole new class of optimizers, or solution concepts, which generalizes most of the well-known optimizers to date. Our combinatoric formulations are related to a new class of solution concepts for n-person games developed by Charnes-Kortanek [Charnes, A., K. O. Kortanek. 1967. On a class of convex and non-archimedean solution concepts for n-person games. Technical Report No. 22, Department of Operations Research, Cornell University, and Systems Research Memo No. 172, Northwestern University, Evanston, Illinois, March.]. By constructing a combinatoric linear programming problem, where some of the variables are determined by an arbitrary set of permutations, we encompass classical optimizers in one formulation including such concepts as (1) minimizing maximum lateness or tardiness, (2) maximizing minimum lateness or tardiness, (3) minimizing mean lateness or flow time, and (4) random sequencing. More generally, we characterize a new class of optimizers as optimal solutions to specially constructed combinatoric programming problems, including optimizers which are integer in character.