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.
Citation
To appear in Parallel Processing Letters, 2004.