Scheduling arrivals to queues

https://doi.org/10.1016/0305-0548(90)90012-VGet rights and content

Abstract

An algorithm is developed to determine the schedule for n arrivals to a single server exponential first come, first served service which will minimize the sum of customer waiting and server availability costs. The algorithm results in a n − 1 dimensional objective function which has been shown to be convex for n ⩽ 4 and is suspected to be convex for n ⩾ 5. The difficulty in demonstrating convexity for n ⩾ 5 is indicated.

References (5)

  • P. Naor

    The regulation of queue size by levying tolls

    Econometrica

    (1969)
  • U. Yechiali

    On optimal balking rules and toll changes in the GI/M/1 queuing process

    Opns Res.

    (1971)
There are more references available in the full text version of this article.

Cited by (53)

  • Adaptive appointment scheduling with periodic updates

    2024, Computers and Operations Research
  • Evaluation of appointment scheduling rules: A multi-performance measurement approach

    2021, Omega (United Kingdom)
    Citation Excerpt :

    Variable block sizes and fixed intervals have been studied in Fries and Marathe [28], Rising et al. [61], Liao et al. [48], and Liu and Liu [49,50]. Fixed block sizes and variable intervals are analyzed in Pegden and Rosenshine [59], Wang [77], and Vanden Bosch and Dietz [72]. As mentioned earlier, appointment systems may focus on the sequencing of customers during a single service session based on their individual characteristics.

  • Simulation modelling and analysis of appointment system performance for multiple classes of patients in a hospital: A case study

    2016, Operations Research for Health Care
    Citation Excerpt :

    Alternatively, for non-Markovian arrivals and service times, an embedded Markov chain is to be defined at some specific points in time. On the other hand, transient analysis of performance has also been presented by many authors [20,15,10]. For transient analysis, the methodology is analytically complex and characteristics like non-punctuality, no-shows and multiple classes of patients makes the analysis even more difficult (see e.g., [4]).

  • Equilibrium arrival times to a queue with order penalties

    2014, European Journal of Operational Research
    Citation Excerpt :

    For a general number of customers, finding an optimal schedule for this problem is a hard global optimization problem, and typically can only be solved using heuristic or approximation algorithms. Examples of such algorithms can be found in Pegden and Rosenshine (1990) or Stein and Côté (1994). More recently Hassin and Mendel (2008) presented an optimization procedure in the context of patient scheduling, when some proportion of the customers do not show up.

View all citing articles on Scopus

Claude Dennis Pegden received his Bachelors in aeronautics, astronautics, and engineering sciences and his PhD in mathematical optimization from Purdue University. He worked at the National Aeronautics and Space Administration and the Matrix Corporation. He taught at the University of Alabama in Huntsville where he led in the development of the SLAM simulation language. In 1979, he joined the faculty at the Pennsylvania State University where he completed the development of the SIMAN simulation language. He is currently the President of Systems Modeling Corporation.

Matthew Rosenshine is currently a Professor of Industrial Engineering and Chairman of the Intercollege Graduate Program in Operations Research at The Pennsylvania State University. Prior to that he was involved in operations research at the Cornell Aeronautical Laboratories of Cornell University. He earned his PhD in operations research engineering from the State University of New York at Buffalo. He holds an AB and MA from Columbia University and an MS from the University of Illinois.

View full text