First-Come-First-Serve Scheduling Is Often Optimal. Part I: Symmetry-Convexity

摘要

The paper develops the theory of 'symmetry-convex' functions, whose appearance in certain scheduling problems as delay-cost functions (of waiting times) guarantees that the 'first-come-first-serve' schedules will be optimal. These are the symmetric functions satisfying a mild convexity condition (which appears to hold in most if not practical scheduling situations). The conclusion of the present paper is that, for a rather special type of scheduling problem, the first-come-first-serve schedules are optimal, provided the waiting times of individual jobs affect delay cost symmetrically. Extensions of this conclusion (to be detailed in one or more subsequent papers) cover broad classes of scheduling problems of great practical significance, relating to both 'first-come-first-serve' and 'first-due-first-serve' scheduling. (Author)