Journal
DISCRETE APPLIED MATHEMATICS
Volume 103, Issue 1-3, Pages 259-269Publisher
ELSEVIER
DOI: 10.1016/S0166-218X(00)00176-1
Keywords
parallel machine scheduling; setup times; worst case analysis
Categories
Ask authors/readers for more resources
To schedule n jobs on m parallel machines with the minimum total cost is the parallel machine scheduling (PMS) problem. Generally, there is a hypothesis: a job cannot be processed on two machines simultaneously if preemption is allowed. When the processing requirement of a job is considered as the demand of a product, jobs can be split arbitrarily to continuous sublets and processed independently on m machines. So, we can discuss PMS under a hypothesis: any part of a job can be processed on two different machines at the same time, and we call it PMS with splitting jobs. In this paper, we first present some simple cases which are polynomial solvable. Furthermore, a heuristic ML and its worst-case analysis are shown for P/split/C-max with independent job setup times. The worst-case performance ratio of ML is within 7/4 - 1/m (m greater than or equal to 2). (C) 2000 Elsevier Science B.V. All rights reserved.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available