Bibliographic Details
| Title: |
Scheduling reentrant jobs on parallel machines with a remote server |
| Authors: |
Chakhlevitch, K. Konstantin.Chakhlevitch.1@city.ac.uk, Glass, C.A.1 |
| Source: |
Computers & Operations Research. Sep2009, Vol. 36 Issue 9, p2580-2589. 10p. |
| Subjects: |
Heuristic programming, Web server software, Benchmarking (Management), Operations research, Microbiology, Problem solving, Remote access networks, Computer software, Computer network resources |
| Abstract: |
Abstract: This paper explores a specific combinatorial problem relating to reentrant jobs on parallel primary machines, with a remote server machine. A middle operation is required by each job on the server before it returns to its primary processing machine. The problem, which is new to the literature, is inspired by the logistics of a semi-automated microbiology laboratory. We establish the NP-hard nature of the problem, and demonstrate various structural properties. A heuristic is developed and tested on randomly generated benchmark data. No alternative heuristics are available in the literature for comparison, but results indicate solutions reliably within 1.5% of optimum. Moreover, tests of our heuristic on real-life data from the microbiology laboratory provide a 20% improvement in throughput relative to current practice. [Copyright &y& Elsevier] |
|
Copyright of Computers & Operations Research is the property of Pergamon Press - An Imprint of Elsevier Science and its content may not be copied or emailed to multiple sites without the copyright holder's express written permission. Additionally, content may not be used with any artificial intelligence tools or machine learning technologies. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.) |
| Database: |
Engineering Source |
