Approximate Solutions for Deterministic and Stochastic Multi-Dimensional Sequencing

Chandra Poojari(chandra.poojaribrunel.ac.uk)
Sachin Patkar(patkarmath.iitb.ac.in)
B Jothi(bjothimath.iitb.ac.in)
Janak Porwal(janakcse.iitb.ac.in)

Abstract: We investigate the problem of sequencing jobs that have multiple components. Each component of the job needs to be processed independently on a specified machine. We derive approximate algorithms for the problem of scheduling such vector jobs to minimize their total completion time in the deterministic as well as stochastic setting. In particular, we propose a Linear Programming and a Greedy heuristic based strategy to derive approximate solutions for deterministic and stochastic formulation of the problem.

Keywords: Multi-dimensional scheduling, Approximate algorithms, Linear Programming, Greedy approach, Stochastic formulation

Category 1: Combinatorial Optimization (Approximation Algorithms )

Category 2: Applications -- OR and Management Sciences (Scheduling )

Citation:

Download: [PDF]

Entry Submitted: 07/16/2007
Entry Accepted: 07/17/2007
Entry Last Modified: 07/16/2007

Modify/Update this entry