Minimizing Makespan Scheduling on a Single Machine with General Positional Deterioration Effects

Abstract

This work studies single-machine scheduling with general position-dependent deterioration, where job processing times are general non-decreasing functions dependent on their positions in a sequence. The goal is to find a job sequence such that makespan is minimized. The problem can be extended to deal with green scheduling environment where processing time increases due to additional carbon-reduction procedure. Under some optimal properties, we prove that the problem is solved by the largest processing time (denoted by LPT) first rule.

Topics & Concepts