-

 

 

 




Optimization Online





 

Automatic Scheduling of Hypermedia Documents with Elastic Times]

Maira Medina (maira***at***inf.puc-rio.br)
Celso Ribeiro (celso***at***inf.puc-rio.br)
Luiz Fernando Soares (lfgs***at***inf.puc-rio.br)

Abstract: The problem of automatic scheduling hypermedia documents consists in finding the optimal starting times and durations of objects to be presented, to ensure spatial and temporal consistency of a presentation while respecting limits on shrinking and stretching the ideal duration of each object. The combinatorial nature of the minimization of the number of objects whose duration is modified makes it the most difficult objective to be tackled by optimization algorithms. We formulate this scheduling problem as a mixed integer programming problem and report some preliminary investigations. We propose an original approach to the minimization of the number of objects which are shrinked or stretched. A simple primal heuristic based on variable fixations along the solution of a sequence of linear relaxations of the mixed integer programming formulation is described. Computational experiments on realistic size problems are reported. The effectiveness of the heuristic in finding good approximate solutions within very small processing times makes of it a quite promising approach to be integrated within existing document formatters to perform compile time scheduling or even run time adjustments. We also discuss results obtained by Lagrangean relaxation and propose a dual heuristic using the modified costs, which consistently improves the solutions found by the primal heuristic.

Keywords: Scheduling, hypermedia documents, elastic times

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

Category 2: Integer Programming (0-1 Programming )

Category 3: Linear, Cone and Semidefinite Programming (Linear Programming )

Citation: To appear in Parallel Processing Letters, 2004.

Download: [Postscript]

Entry Submitted: 10/12/2003
Entry Accepted: 10/12/2003
Entry Last Modified: 10/12/2003

Modify/Update this entry


  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository

 

Submit
Update
Policies
Coordinator's Board
Classification Scheme
Credits
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Programming Society