City Research Online

Scheduling reentrant jobs on parallel machines with a remote server

Chakhlevitch, K. & Glass, C. (2008). Scheduling reentrant jobs on parallel machines with a remote server (Statistical Research Paper No. 30). London, UK: Faculty of Actuarial Science & Insurance, City University London.

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.

Publication Type: Monograph (Working Paper)
Publisher Keywords: scheduling, parallel identical machines, remote server, reentrant jobs
Subjects: H Social Sciences > HG Finance
Departments: Bayes Business School > Actuarial Science & Insurance > Statistical Research Reports
SWORD Depositor:
[thumbnail of 30-StatResRep.pdf]
Preview
PDF
Download (674kB) | Preview

Export

Add to AnyAdd to TwitterAdd to FacebookAdd to LinkedinAdd to PinterestAdd to Email

Downloads

Downloads per month over past year

View more statistics

Actions (login required)

Admin Login Admin Login