Two-machine shop scheduling with two agents and linear deteriorating jobs

We consider a two-machine shop scheduling problem in which the jobs are from two agents and each job has a time-dependent proportional deteriorating processing time. The two agents compete for a common two-machine shop setting to process their own jobs. Each agent has its own criterion to optimize. Three shop settings are investigated: flow-shop, open-shop and job-shop. For each setting, the goal is to find a schedule to process the jobs such that the makespan of one agent is minimized while the makespan of the other agent is no more than a given upper bound. We prove that all the problems are NP-hard. Moreover, we present efficient algorithms for two special cases of flow-shop scheduling problem.