Some Single-Machine Scheduling Problems with Learning Effects and Two Competing Agents

Abstract EN

This study considers a scheduling environment in which there are two agents and a set of jobs, eachof which belongs to one of the two agents and its actual processing time is defined as a decreasing linearfunction of its starting time.

Each of the two agents competes to process its respective jobs on a singlemachine and has its own scheduling objective to optimize.

The objective is to assign the jobs so that theresulting schedule performs well with respect to the objectives of both agents.

The objective functionsaddressed in this study include the maximum cost, the total weighted completion time, and the discountedtotal weighted completion time.

We investigate three problems arising from different combinations of theobjectives of the two agents.

The computational complexity of the problems is discussed and solutionalgorithms where possible are presented.