FIRST-COME-FIRST-SERVE SCHEDULING IS OFTEN OPTIMAL. PART 1: SYMMETRY- CONVEXITY

Abstract

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.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Sep 01, 1967
Accession Number
AD0661470

Entities

People

  • James R. Jackson

Organizations

  • University of California, Los Angeles

Tags

Communities of Interest

  • Air Platforms

DTIC Thesaurus Topics

  • Abstracts
  • Buildings And Structures
  • Classification
  • Contractors
  • Contracts
  • Convex Sets
  • Customer Services
  • Governments
  • Guarantees
  • Notation
  • Permutations
  • Scheduling (Production)
  • Security
  • Standards
  • Symmetry
  • Theorems
  • United States Government

Readers

  • Mathematical Modeling and Probability Theory.
  • Operations Research