Efficient algorithms for scheduling equal-length jobs with processing set restrictions on uniform parallel batch machines
Author:
Open Access
- 1 January 2022
- journal article
- research article
- Published by American Institute of Mathematical Sciences (AIMS) in Mathematical Biosciences and Engineering
- Vol. 19 (11) , 10731-10740
Abstract
We consider the problem of scheduling jobs with equal lengths on uniform parallel batch machines with non-identical capacities where each job can only be processed on a specified subset of machines called its processing set. For the case of equal release times, we give efficient exact algorithms for various objective functions. For the case of unequal release times, we give efficient exact algorithms for minimizing makespan.Keywords
All Related Versions
This publication has 41 references indexed in Scilit:
- Makespan minimisation on parallel batch processing machines with non-identical job sizes and release datesInternational Journal of Production Research, 2012
- Scheduling unit-length jobs with machine eligibility restrictionsEuropean Journal of Operational Research, 2006
- Semi-matchings for bipartite graphs and load balancingJournal of Algorithms, 2006
- Scheduling unit length jobs with parallel nested machine processing set restrictionsComputers & Operations Research, 2006
- Parallel machine scheduling of machine-dependent jobs with unit-lengthEuropean Journal of Operational Research, 2004
- An efficient retrieval selection algorithm for video servers with random duplicated assignment storage techniqueInformation Processing Letters, 2002
- Scheduling with batching: A reviewEuropean Journal of Operational Research, 2000
- Fibonacci heaps and their uses in improved network optimization algorithmsJournal of the ACM, 1987
- Computers and Intractability: A Guide to the Theory of NP-Completeness (Michael R. Garey and David S. Johnson)SIAM Review, 1982
- An $n^{5/2} $ Algorithm for Maximum Matchings in Bipartite GraphsSIAM Journal on Computing, 1973