Single machine batch scheduling with release times and delivery costs |
| |
Authors: | Esaignani Selvarajah George Steiner Rui Zhang |
| |
Affiliation: | 1. Odette School of Business, University of Windsor, Windsor, ON, Canada 2. DeGroote School of Business, McMaster University, Hamilton, ON, Canada
|
| |
Abstract: | We study single machine batch scheduling with release times. Our goal is to minimize the sum of weighted flow times (or completion times) and delivery costs. Since the problem is strongly $mathcal{NP}$ -hard even with no delivery cost and identical weights for all jobs, an approximation algorithm is presented for the problem with identical weights. This uses the polynomial time solution we give for the preemptive version of the problem. We also present an evolutionary metaheuristic algorithm for the general case. Computational results show very small gaps between the results of the metaheuristic and the lower bound. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|