Structural properties of time-dependent scheduling problems with the l<inf>p</inf> norm objective

Authors:

• Stanisław Gawiejnowicz,
• Wiesław Kurc

Abstract

We consider general properties which describe the structure of schedules for a single machine scheduling problem with linearly deteriorating jobs and the objective to minimize the lp norm. Applying a matrix formulation of the problem, we show that it has unique solutions and for p≥1 it possesses a kind of convexity. We also express the time complexity of the problem as a function of index p of the lp norm and prove that there exist thresholds p∞ and p1 such that p∞1 and the case 1≤p≤p∞ is at least as difficult as the case p=1, while the case p1≤p≤+∞ is as easy as the case p=+∞ These results imply that the V-shapeness of optimal schedules for the problem, previously known only for p=1, still holds for infinite many p>1, while symmetricity of the schedules may hold only for some p≥1.