Chakhlevitch, K. & Glass, C. (2008). Scheduling reentrant jobs on parallel machines with a remote server (Report No. Statistical Research Paper No. 30). London, UK: Faculty of Actuarial Science & Insurance, City University London.
![]()
|
PDF
Download (674kB) | Preview |
Abstract
This paper explores a specific combinatorial problem relating to re-entrant 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 is inspired by the logistics of a semi-automated micro-biology laboratory. The testing programme in the laboratory corresponds roughly to a hybrid flowshop, whose bottleneck stage is the subject of study. We demonstrate the NP-hard nature of the problem, and provide various structural features. A heuristic is developed and tested on randomly generated benchmark data. Results indicate solutions reliably within 1.5% of optimum. We also provide a greedy 2-approximation algorithm. Test on real-life data from the microbiology laboratory indicate a 20% saving relative to current practice, which is more than can be achieved currently with 3 instead of 2 people staffing the primary machines.
Item Type: | Monograph (Working Paper) |
---|---|
Uncontrolled Keywords: | scheduling, parallel identical machines, remote server, reentrant jobs |
Subjects: | H Social Sciences > HG Finance |
Divisions: | Cass Business School > Faculty of Actuarial Science & Insurance > Faculty of Actuarial Science & Insurance Statistical Research Reports |
URI: | http://openaccess.city.ac.uk/id/eprint/2374 |
Actions (login required)
![]() |
View Item |
Downloads
Downloads per month over past year