A TIME-DEPENDENT SCHEDULING PROBLEM TO MINIMIZE THE SUM OF THE TOTAL WEIGHTED TARDINESS AMONG TWO AGENTS

摘要

The problem of scheduling with time-dependent processing times has been studied for more than two decades and significant advances have been made over the years. However, most work has paid more attention to the single-criterion models. Furthermore, most heuristics are constructed for the time-dependent scheduling problems in a step-by-step way. Motivated by the observations, this paper studies a two-agent scheduling model with increasing linear deterioration jobs in which the processing time of a job is modeled as an increasing linear function of its starting time. The objective function is to minimize the sum of the maximum weighted tardiness of the jobs of the first agent and the total weighted tardiness of the jobs of the second agent. This problem is known to be strongly NP-hard. Thus, as an alternative, the branch-and-bound, ant colony algorithm and simulated annealing algorithms are developed for the problem. Computational results are also presented to determine the performance of the proposed algorithms.