We found a match
Your institution may have access to this item. Find your institution then sign in to continue.
- Title
Two-agent single-machine scheduling with release dates and preemption to minimize the maximum lateness.
- Authors
Yuan, J.; Ng, C.; Cheng, T.
- Abstract
We consider two-agent scheduling on a single machine with release dates and preemption to minimize the maximum lateness. In this scheduling model, there are two agents $$A\hbox { and }B$$ each having his own job set $$\mathcal{J}_A= \{ J^a_1, \ldots , J^a_{n_a}\}\hbox { and }\mathcal{J}_B= \{ J^b_1, \ldots , J^b_{n_b}\}$$ , respectively. Each job $$J_j\in \mathcal{J}_A\cup \mathcal{J}_B$$ has a release date $$r_j$$ and the $$n=n_a+n_b$$ jobs need to be preemptively scheduled on a single machine. Leung et al. (Oper Res 58:458-469, ) present a comprehensive study of two-agent scheduling in various machine environments. They show that problem $$1|r_j,\; \text{ pmtn }| L^a_{\max }: f^b_{\max }\le Q$$ can be solved in $$O(n_a\log n_a+ n_b\log n_b)$$ time. They use the strategy that schedules the jobs of agent $$B$$ without preemption as late as possible under the restriction $$f^b_{\max }\le Q$$ . We show that the strategy fails to work even when $$n_a=n_b=1$$ , invalidating their result. We then study the minimization problem $$1|r_j,\; \text{ pmtn }| L^a_{\max }: f^b_{\max }\le Q$$ and the Pareto optimization problem $$1|r_j,\; \text{ pmtn }| (L^a_{\max }: L^b_{\max })$$ . We show that the two problems can be solved in $$O(n_an \log n)\hbox { and }O(n_an_bn \log n)$$ time, respectively.
- Subjects
EMPLOYEE tardiness; MACHINERY; SCHEDULING; TIME management; EMPLOYEES' workload
- Publication
Journal of Scheduling, 2015, Vol 18, Issue 2, p147
- ISSN
1094-6136
- Publication type
Article
- DOI
10.1007/s10951-013-0360-y