| Titre : | The unbounded parallel-batch scheduling with rejection (2012) |
| Auteurs : | L. Q. Zhang, Auteur ; L. F. Lu, Auteur ; C. T. Ng, Auteur |
| Type de document : | Article : texte imprimé |
| Dans : | Journal of the operational research society (JORS) (Vol. 63 N° 3, Mars 2012) |
| Article en page(s) : | pp. 293–298 |
| Note générale : | Recherche opérationnelle |
| Langues : | Anglais |
| Index. décimale : | 001.424 |
| Tags : | Parallel-batch scheduling Rejection penalty Polynomial-time algorithm |
| Résumé : | In this paper, we consider the unbounded parallel-batch scheduling with rejection. A job is either rejected, in which case a certain penalty has to be paid, or accepted and processed in batches on a machine. The processing time of a batch is defined as the longest processing time of the jobs contained in it. Four problems are considered: (1) to minimize the sum of the total completion time of the accepted jobs and the total rejection penalty of the rejected jobs; (2) to minimize the total completion time of the accepted jobs subject to an upper bound on the total rejection penalty of the rejected jobs; (3) to minimize the total rejection penalty of the rejected jobs subject to an upper bound on the total completion time of the accepted jobs; (4) to find the set of all the Pareto optimal schedules. We provide a polynomial-time algorithm for the first problem. Furthermore, we show that all the other three problems are binary NP-hard and present a pseudo-polynomial-time algorithm and a fully polynomial-time approximation scheme for them. |
| DEWEY : | 001.424 |
| ISSN : | 0160-5682 |
| En ligne : | http://www.palgrave-journals.com/jors/journal/v63/n3/abs/jors201131a.html |
