An exact approach to early/tardy scheduling with release dates |
| |
| Affiliation: | Faculdade de Economia, Universidade do Porto, Rua Dr. Roberto Frias, 4200-464 Porto, Portugal;Department of Mathematics, Huainan Normal University, Anhui, PR China;Département de mathématiques, Université de Sherbrooke, Sherbrooke, Québec J1K 2R1, Canada;Earthquake Research Center, Ferdowsi University of Mashhad, Iran;Instituto Federal do Rio Grande do Sul PPGMAp, Universidade Federal do Rio Grande do Sul Bento Gonçalves, P.O. Box 15080, Porto Alegre, RS, Brazil;Department of Mathematics, Tianshui Normal University, Tianshui, Gansu 741001, People’s Republic of China;Dept. of Mathematics, National Technical University of Athens, Zografou Campus, Athens 15780, Greece |
| |
| Abstract: | In this paper, we consider the single machine earliness/tardiness scheduling problem with different release dates and no unforced idle time. The problem is decomposed into weighted earliness and weighted tardiness subproblems. Lower bounding procedures are proposed for each of these subproblems, and the lower bound for the original problem is the sum of the lower bounds for the two subproblems. The lower bounds and several versions of a branch-and-bound algorithm are then tested on a set of randomly generated problems, and instances with up to 30 jobs are solved to optimality. To the best of our knowledge, this is the first exact approach for the early/tardy scheduling problem with release dates and no unforced idle time. |
| |
| Keywords: | |
| 本文献已被 ScienceDirect 等数据库收录！ |
|
