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-hardNP-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.