Single machine scheduling problem with two synergetic agents and piece-rate maintenance

This paper attempts to study on the single machine scheduling problems with two synergetic agents, each has a set of nonpreemptive jobs and a regular objective function depending on the completion times of its jobs only. It is not only necessary to satisfy the constraints of each agents objective function, it is necessary to minimize an aggregate increasing objective function of two agents’ objective function. Furthermore, this paper proposes a new kind of machine maintenance: piece-rate maintenance, which depicts the scenario that machine maintenance is implemented once every a fixed number of jobs is completed. Hence, it explores into the single machine scheduling problems with two synergetic agents and piece-rate maintenance. If the regular objective function of each job is polynomial, it can be observed that these problems are all polynomially solvable.