摘要
We consider a scheduling problem involving a single processor utilized by two customers with constant deteriorating jobs, i.e., jobs whose processing times are an increasing function of their starting times. Traditionally, such scenarios are modeled by assuming that each customer has the same criterion. In practice, this assumption may not hold. Instead of using a single criterion, we examine the implications of minimizing an aggregate scheduling objective function in which jobs belonging to different customers are evaluated with their individual criteria. We examine three basic scheduling criteria： minimizing makespan, minimizing maximum lateness, and minimizing total weighted completion time. We demonstrate all the scheduling problems considered are polynomially solvable.
We consider a scheduling problem involving a single processor utilized by two customers with constant deteriorating jobs, i.e., jobs whose processing times are an increasing function of their starting times. Traditionally, such scenarios are modeled by assuming that each customer has the same criterion. In practice, this assumption may not hold. Instead of using a single criterion, we examine the implications of minimizing an aggregate scheduling objective function in which jobs belonging to different customers are evaluated with their individual criteria. We examine three basic scheduling criteria： minimizing makespan, minimizing maximum lateness, and minimizing total weighted completion time. We demonstrate all the scheduling problems considered are polynomially solvable.
