Scheduling linearly deteriorating jobs by two agents to minimize the weighted sum of two criteria
We consider scheduling jobs by two agents on a single machine. Each job is defined by a common release date, a deteriorating processing time that is a linear function of the job starting time and a weight or a due-date. Every agent constructs a partial schedule that includes only the agent?s jobs and is evaluated by the agent?s optimality criterion: the total weighted completion time or the maximum lateness. The aim is to find a complete schedule minimizing a weighted sum of the two criteria. We prove that the problem is NP-hard NP - hard and show several properties that describe the structure of schedules for the problem. We also propose an exact algorithm and a meta-heuristic for the problem. Finally, we report the results of evaluation of the proposed algorithms by computational experiments.
deteriorating jobs total weighted completion time maximum lateness algorithms agent scheduling np-hardness np - hardness np-hardness np - hardness np-hardness np - hardness np - hardness