Research Reports from the Department of Operations
Document Type
Dissertation
Publication Date
5-1-1986
Abstract
In resource allocation and scheduling problems, we frequently come across situations wherein the tasks, although similar in nature, require resources of different capacities. An example is the assignment of airplanes to different flights. In this case, the basic task is the same, but depending on the expected load of a flight, we would assign a plane of larger or smaller capacity to that flight. The essential feature of this type of problem is that not only the tasks require resources of different capacities, but also a resource with a higher capacity can, if necessary, undertake a task which requires a resource of lower capacity, but not vice versa. In other words, there is a hierarchical capacity structure associated with the tasks and resources, and we refer to problems of this type as hierarchical scheduling problems. Given a start time sj, processing time pj, and the minimal capacity of the processor required Rj, for each job j, the objective of the hierarchical scheduling problem (HSP) is to determine the optimal mix of processors, available in m different sizes, required to complete all jobs on schedule. In this dissertation, optimization algorithms are presented for solving the preemptive and non-preemptive cases of the HSP. A simple greedy algorithm is developed to solve the preemptive HSP. In the non-preemptive case, a special network called the HSP network is constructed. An optimization algorithm, based on the max-flow algorithm, that exploits the special structure of the HSP network, is developed to solve the two-level (m=2) non-preemptive HSP. For the higher level (m>2) non-preemptive HSP, it is proved that though the problem is essentially combinatorial (0-1 variables) in nature, the corresponding Linear Program has at least one integer optimal solution, among several possible alternative optimal solutions. A procedure, involving simple perturbation of the objective function coefficients of the LP, is described for obtaining the integer optimal solution. Also, a formulation approach that aggregates the jobs and makes the actual number of jobs an irrelevant factor in solving the non-preemptive HSP is discussed.
Keywords
Operations research, Scheduling--Mathematical models, Resource allocation--Mathematical models, Mathematical optimization, Linear programming, Algorithms, Combinatorial analysis, Production scheduling
Publication Title
Dissertation/Technical Memorandums from the Department of Operations, School of Management, Case Western Reserve University
Issue
Technical memorandum no. 575 ; Submitted in partial fulfillment of the requirements for the Degree of Doctor of Philosophy.
Rights
This work is in the public domain and may be freely downloaded for personal or academic use
Recommended Citation
Dondeti, Venkateswara Reddy, "Minimal Resources for Fixed Job Schedules with Defferent Processor Size Requirements and a Hierarchical Structure" (1986). Research Reports from the Department of Operations. 308.
https://commons.case.edu/wsom-ops-reports/308