Structural properties of time-dependent scheduling problems with the lp norm objective

• We study properties of a time-dependent scheduling problem with thelp norm objective.
• We prove that solutions to the problem are unique and possess a kind of convexity.
• We express time complexity of the problem as a function of index p of the lp norm.
• We show that optimal schedules for the problem are V-shaped for infinitely many p>1p>1 and symmetric only for some p≥1p≥1.
• We also show that optimal schedules for the problem are symmetric only for some p>1p>1.

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≥1p≥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∞p∞ and p1 such that p∞1p>1, while symmetricity of the schedules may hold only for some p≥1p≥1.