Minimizing the number of tardy jobs in two-machine settings with common due date |
| |
Authors: | Federico Della Croce Christos Koulamas Vincent T’kindt |
| |
Affiliation: | 1.D.A.I., Politecnico di Torino,Torino,Italy;2.CNR, IEIIT,Torino,Italy;3.College of Business,Florida International University,Miami,USA;4.Université Francois-Rabelais, CNRS, LI EA 6300, OC ERL CNRS 6305,Tours,France |
| |
Abstract: | We consider two-machine scheduling problems with job selection. We analyze first the two-machine open shop problem and provide a best possible linear time algorithm. Then, a best possible linear time algorithm is derived for the job selection problem on two unrelated parallel machines. We also show that an exact approach can be derived for both problems with complexity (O(p(n) times sqrt{2}^n)), p being a polynomial function of n. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|