SINGLE-MACHINE BI-CRITERION SCHEDULING WITH RELEASE TIMES AND EXPONENTIALLY TIME-DEPENDENT LEARNING EFFECTS

摘要

This paper deals with a single machine bi-criterion scheduling problem with exponentially time-dependent learning effects and non-zero job release times. The goal is to minimize the weighted sum of the makespan and the total completion time. First, a branch-and-bound algorithm incorporating with some dominance properties and three lower bounds is developed for the optimal solutions. Then heuristic and particle swarm optimization algorithms are presented for near-optimal solutions. Finally, computational experiments are conducted to evaluate the performances of the proposed algorithms. Computational results indicate that the algorithms perform well in either solving the problem or efficiently generating near-optimal solutions.