FIRST-COME-FIRST-SERVE SCHEDULING IS OFTEN OPTIMAL. PART 1: SYMMETRY- CONVEXITY
CALIFORNIA UNIV LOS ANGELES WESTERN MANAGEMENT SCIENCE INST
Pagination or Media Count:
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.
- Operations Research