A combined approach for two-agent scheduling with sum-of-processing-times-based learning effect

Abstract

This paper considers a scheduling model involving two agents, job release times, and the sum-of-processing-times-based learning effect. The sum-of-processing-times-based learning effect means that the actual processing time of a job of either agent is a decreasing function of the sum of the processing times of the jobs already scheduled in a given schedule. The goal is to seek for an optimal schedule that minimizes the total weighted completion time of the first agent, subject to no tardy job for the second agent. We first provide a branch-and-bound method to solve the problem. We then develop an approach that combines genetic algorithm and simulated annealing to seek for approximate solutions for the problem. We carry on extensive computational tests to assess the performance of the proposed algorithms.

Keywords:

• agent scheduling
• genetic algorithm
• simulated annealing
• sum-of-processing- times-based learning effect
• branch-and-bound algorithm

Acknowledgments

We are grateful to the Editor, an AE, and two anonymous referees for their many helpful comments on earlier version of our paper. This paper was supported in part by the National Natural Science Foundation of China under grant numbers 11561036 and 71301022 and in part by the Ministry of Science Technology (MOST) of Taiwan under grant numbers NSC 102-2221-E-035-070-MY3 and MOST 103-2410-H- 035- 022-MY2. Cheng was supported in part by The Hong Kong Polytechnic University under the Fung Yiu King-Wing Hang Bank Endowed Professorship in Business Administration.