Two-agent scheduling with linear deteriorating jobs on a single machine. (English) Zbl 1148.90324
Hu, Xiaodong (ed.) et al., Computing and combinatorics. 14th annual international conference, COCOON 2008, Dalian, China, June 27--29, 2008. Proceedings. Berlin: Springer (ISBN 978-3-540-69732-9/pbk). Lecture Notes in Computer Science 5092, 642-650 (2008).
Summary: This paper considers the two-agent scheduling problems with linear deteriorating jobs to be processed on a single machine. By a deteriorating job we mean that the processing time of the job is a function of its starting time. Two agents compete for the usage of a common single machine and each agent has his own criterion to optimize. There are four objective functions: makespan, maximum lateness, maximum cost, and total completion time. Some basic properties of two different scheduling problems to minimize the objective function for one agent with a constraint on the other agent’s objective function are proved. Based on these properties, the optimal algorithms with polynomial time are presented for two different scheduling problems, respectively. For the entire collection see [Zbl 1139.68006
|90B35||Scheduling theory, deterministic|