Authors: Stanisław Gawiejnowicz Alexander Kononov
Publish Date: 2012/09/19
Volume: 213, Issue: 1, Pages: 131-145
Abstract
We consider general properties of isomorphic scheduling problems that constitute a new class of pairs of mutually related scheduling problems Any such a pair is composed of a scheduling problem with fixed job processing times and its timedependent counterpart with processing times that are proportionallinear functions of the job starting times In order to introduce the class formally first we formulate a generic scheduling problem with fixed job processing times and define isomorphic problems by a onetoone transformation of instances of the generic problem into instances of timedependent scheduling problems with proportionallinear job processing times Next we prove basic properties of isomorphic scheduling problems and show how to convert polynomial algorithms for scheduling problems with fixed job processing times into polynomial algorithms for proportionallinear counterparts of the original problems Finally we show how are related approximation algorithms for isomorphic problems Applying the results we establish new worstcase results for timedependent parallelmachine scheduling problems and prove that many single and dedicatedmachine timedependent scheduling problems with proportionallinear job processing times are polynomially solvable
Keywords: