The unbounded parallel-batch scheduling with rejection / L. Q. Zhang in Journal of the operational research society (JORS), Vol. 63 N° 3 (Mars 2012)  

Public ISBD [article]  inJournal of the operational research society (JORS) > Vol. 63 N° 3 (Mars 2012) . - pp. 293–298 Titre : The unbounded parallel-batch scheduling with rejection Type de document : texte imprimé Auteurs : L. Q. Zhang, Auteur ; L. F. Lu, Auteur ; C. T. Ng, Auteur Année de publication : 2012 Article en page(s) : pp. 293–298 Note générale : Recherche opérationnelle Langues : Anglais (eng) Mots-clés : Parallel-batch scheduling Rejection penalty Polynomial-time algorithm Index. décimale : 001.424 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 [article] The unbounded parallel-batch scheduling with rejection [texte imprimé] / L. Q. Zhang, Auteur ; L. F. Lu, Auteur ; C. T. Ng, Auteur . - 2012 . - pp. 293–298. Recherche opérationnelle Langues : Anglais (eng) in Journal of the operational research society (JORS) > Vol. 63 N° 3 (Mars 2012) . - pp. 293–298 Mots-clés : Parallel-batch scheduling Rejection penalty Polynomial-time algorithm Index. décimale : 001.424 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

Exemplaires

Code-barres	Cote	Support	Localisation	Section	Disponibilité
aucun exemplaire