Presenter: Girish A. Ramachandra
Advisor(s): Dr. S. E. Elmaghraby
Author(s): Girish A. Ramachandra and S. E. Elmaghraby
Graduate Program: Industrial Engineering
Title: Problems in scheduling:1) Sequencing precedence related jobs on identical parallel machines to minimize the sum of weighted completion times, and 2) Optimal resource allocation in activity networks.
Abstract: We discuss two problems in the area of scheduling: 1) Sequencing precedence related jobs on identical parallel machines to minimize the sum of weighted completion times, and 2) Optimal resource allocation in activity networks.
For the first problem we present a new dynamic programming (DP) algorithm that extends the approach taken to solve a similar problem, but on a single machine. We briefly allude to an integer programming model used to solve small- to medium-sized problems to optimality, and the related linear programming relaxations used to obtain lower bounds. Finally we outline a genetic algorithm-based approach and present some results.
For the second problem we describe a new approach to optimally allocate resources in projects to minimize an economic objective function. The underlying hypothesis of our approach is that the work content of an activity is the uncertain parameter, and that the duration of the activity is the consequence of the amount of resources allocated to it. We look at both deterministic and stochastic versions of the problem. For the deterministic case, we present a nonlinear programming formulation and a binary integer program to handle the continuous and discrete levels of resource availabilities, respectively. For the stochastic case, we present an analytical approach for solving the problem when the work content of the activities is exponentially distributed random variable. We also discuss a simulation-based optimization approach to handle the case when the work content is sampled from a general probability distribution. We demonstrate the effectiveness of good sampling and variance-reduction techniques in our model.