Scheduling Two-Agents with a Time-Dependent Deterioration to Minimize the Minsum Earliness Measures

This paper considers a new scheduling model in which both two-agents and a time-dependent deterioration exist simultaneously. By the time-dependent deterioration, it means that the actual processing time of a job belonging to the two-agents is defined as a non-decreasing linear function of its starting time. Two-agents compete to perform their respective jobs on a common single-machine and each agent has his own criterion to be optimized. The aim is to focus on minimizing total (weighted) earliness cost of one agent, subject to an upper bound on the maximum earliness cost of the other agent. The main contribution of this paper is to propose the optimal properties and present the complexity results for the problems addressed here.