Skip to Main Content
 

Global Search Box

 
 
 
 

Files

File List


case1057678953.pdf (6.38 MB)

ETD Abstract Container

Abstract Header

On interval scheduling problems: A contribution

Bouzina, Khalid Ibn El Walid
http://rave.ohiolink.edu/etdc/view?acc_num=case1057678953

Abstract Details

1994, Doctor of Philosophy, Case Western Reserve University, Operations Research.
In the theory of Scheduling we often encounter the situation where independent tasks have fixed start and end times. This variation of the general theme is called the Interval Scheduling Problem and we consider it in the parallel resource environment. However, we do admit the possibility that a resource is not able to process certain tasks because of their size or other special characteristic. Furthermore, we analyze situations where a resource may not be available at all times or where a bound is imposed on its total operating time. The two optimization criteria we focus on are the maximization of the number of completed tasks; and, when weights are associated with tasks, the schedule of a subset of tasks with maximum total weight. Our study of IS problems is threefold. We start with the analysis of the situation where all machines are assumed identical. In this case, we develop polynomial time algorithms when no machines' availability constraints are imposed. Next, we study the complexity of the problem where each machine has a fixed interval of operation (a shift), and solve the problem efficiently when job preemption is authorized. Also, when a bound is required on the operating time of any machine, we prove the problem intractable in general and provide polynomial solutions for some preemptive versions. The second part of this study addresses the situation where machines are no longer identical but where a special structure, namely a hierarchical assignment of machines to jobs, is investigated. For this case, computational complexity issues are examined and polynomial solutions are offered when jobs preemption is allowed. The final phase of this thesis is devoted to the study of IS problems when any job-machine mapping is considered. We show that even for restricted instances, this type of IS problems remains intractable. However, heuristics and/or integer programming formulations are proposed.
Hamilton Emmons (Advisor)
261 p.
Operations Research
interval scheduling problems

Recommended Citations

Citations

  • Bouzina, K. I. E. W. (1994). On interval scheduling problems: A contribution [Doctoral dissertation, Case Western Reserve University]. OhioLINK Electronic Theses and Dissertations Center. http://rave.ohiolink.edu/etdc/view?acc_num=case1057678953

    APA Style (7th edition)

  • Bouzina, Khalid. On interval scheduling problems: A contribution. 1994. Case Western Reserve University, Doctoral dissertation. OhioLINK Electronic Theses and Dissertations Center, http://rave.ohiolink.edu/etdc/view?acc_num=case1057678953.

    MLA Style (8th edition)

  • Bouzina, Khalid. "On interval scheduling problems: A contribution." Doctoral dissertation, Case Western Reserve University, 1994. http://rave.ohiolink.edu/etdc/view?acc_num=case1057678953

    Chicago Manual of Style (17th edition)

case1057678953
776
© 1994, all rights reserved.
This open access ETD is published by Case Western Reserve University School of Graduate Studies and OhioLINK.