Scheduling multiclass queueing networks and job shops using fluid and semidefinite relaxations
Thesis (Ph.D.)--Massachusetts Institute of Technology, Sloan School of Management, Operations Research Center, 1999.
| Main Author: | |
|---|---|
| Other Authors: | |
| Format: | Thesis |
| Language: | eng |
| Published: |
Massachusetts Institute of Technology
2005
|
| Subjects: | |
| Online Access: | http://hdl.handle.net/1721.1/17482 |
| _version_ | 1811082077195468800 |
|---|---|
| author | Sethuraman, Jayachandran, 1970- |
| author2 | Dimitris J. Bertsimas. |
| author_facet | Dimitris J. Bertsimas. Sethuraman, Jayachandran, 1970- |
| author_sort | Sethuraman, Jayachandran, 1970- |
| collection | MIT |
| description | Thesis (Ph.D.)--Massachusetts Institute of Technology, Sloan School of Management, Operations Research Center, 1999. |
| first_indexed | 2024-09-23T11:57:12Z |
| format | Thesis |
| id | mit-1721.1/17482 |
| institution | Massachusetts Institute of Technology |
| language | eng |
| last_indexed | 2024-09-23T11:57:12Z |
| publishDate | 2005 |
| publisher | Massachusetts Institute of Technology |
| record_format | dspace |
| spelling | mit-1721.1/174822019-04-12T08:51:27Z Scheduling multiclass queueing networks and job shops using fluid and semidefinite relaxations Sethuraman, Jayachandran, 1970- Dimitris J. Bertsimas. Massachusetts Institute of Technology. Operations Research Center. Massachusetts Institute of Technology. Operations Research Center. Operations Research Center. Thesis (Ph.D.)--Massachusetts Institute of Technology, Sloan School of Management, Operations Research Center, 1999. Includes bibliographical references (p. 152-158). Queueing networks serve a& useful models for a variety of problems arising in modern communications, computer, and manufacturing systems. Since the optimal control problem for queueing networks is well-known to be intractable, an important theme of research during the last two decades has been the development of tractable approximations, and the use of these approximations to determine optimal controls. Fluid relaxations are an important class of such approximations that have received much attention in recent years. The central aim of this dissertation is to demonstrate the usefulness of fluid relaxations in solving a variety of scheduling problems. In the first part of this dissertation, we explore the role of fluid relaxations in solving traditional job shop problems. For the job shop problem with the objective of minimizing makespan, we construct a schedule that is guaranteed to be within a constant of the optimal. In particular, our schedule is asymptotically optimal. We prove an analogous asymptoticoptimality result for the objective of minimizing holding costs. For both objectives, we report impressive computational results on benchmark instances chosen from the OR library. Our algorithms use fluid relaxations in two different ways: first, the optimal fluid cost is used as a lower bound for the original problem; and second, a discrete schedule is constructed by appropriately rounding an optimal fluid solution. In the second part of this dissertation we study the optimal control problem for multiclass queueing networks in steady-state. A key difficulty is that the fluid relaxation, being transient in nature, does not readily yield a lower bound for the steady-state problem. For this reason, we use a class of lower bounds, based on semidefinite relaxations, first proposed by Bertsimas and Niiio-Mora. Interestingly, one of the shortcomings of these relaxations is that there is no natural way to derive policies based on them. Thus, while our lower bounds are based on semidefinite relaxations, our policies are based on a heuristic interpretation of optimal fluid solutions. We consider objective functions involving both first and second moments of queue-lengths (equivalently, delays). Our computational results show the effectiveness of this approach in obtaining good policies for multiclass queueing networks. Finally, we turn our attention to the problem of computing the optimal fluid solution efficiently. We develop a general method to solve the optimal control problem for fluid tandem networks, and identify ... solvable special cases. by Jayachandran Sethuraman. Ph.D. 2005-06-02T15:25:00Z 2005-06-02T15:25:00Z 1999 1999 Thesis http://hdl.handle.net/1721.1/17482 44815350 eng M.I.T. theses are protected by copyright. They may be viewed from this source for any purpose, but reproduction or distribution in any format is prohibited without written permission. See provided URL for inquiries about permission. http://dspace.mit.edu/handle/1721.1/7582 158 p. 6712587 bytes 6712394 bytes application/pdf application/pdf application/pdf Massachusetts Institute of Technology |
| spellingShingle | Operations Research Center. Sethuraman, Jayachandran, 1970- Scheduling multiclass queueing networks and job shops using fluid and semidefinite relaxations |
| title | Scheduling multiclass queueing networks and job shops using fluid and semidefinite relaxations |
| title_full | Scheduling multiclass queueing networks and job shops using fluid and semidefinite relaxations |
| title_fullStr | Scheduling multiclass queueing networks and job shops using fluid and semidefinite relaxations |
| title_full_unstemmed | Scheduling multiclass queueing networks and job shops using fluid and semidefinite relaxations |
| title_short | Scheduling multiclass queueing networks and job shops using fluid and semidefinite relaxations |
| title_sort | scheduling multiclass queueing networks and job shops using fluid and semidefinite relaxations |
| topic | Operations Research Center. |
| url | http://hdl.handle.net/1721.1/17482 |
| work_keys_str_mv | AT sethuramanjayachandran1970 schedulingmulticlassqueueingnetworksandjobshopsusingfluidandsemidefiniterelaxations |