Please use this identifier to cite or link to this item:
Title: Deterministic and stochastic scheduling with teamwork tasks
Authors: Cai, X
Zhou, X
Keywords: General cost functions
Maximum cost
Stochastic criteria
Stochastic scheduling
Teamwork tasks
Total completion time
Issue Date: 2004
Publisher: John Wiley & Sons
Source: Naval research logistics, 2004, v. 51, no. 6, p. 818-840 How to cite?
Journal: Naval research logistics 
Abstract: We study a class of new scheduling problems which involve types of teamwork tasks. Each teamwork task consists of several components, and requires a team of processors to complete, with each team member to process a particular component of the task. Once the processor completes its work on the task, it will be available immediately to work on the next task regardless of whether the other components of the last task have been completed or not. Thus, the processors in a team neither have to start, nor have to finish, at the same time as they process a task. A task is completed only when all of its components have been processed. The problem is to find an optimal schedule to process all tasks, under a given objective measure. We consider both deterministic and stochastic models. For the deterministic model, we find that the optimal schedule exhibits the pattern that all processors must adopt the same sequence to process the tasks, even under a general objective function GC = F(f 1(C1), f2(C2),⋯ f n(Cn)), where fi(Ci) is a general, nondecreasing function of the completion time Ci of task i. We show that the optimal sequence to minimize the maximum cost MC = max f i(Ci) can be derived by a simple rule if there exists an order fl(t) ≤ ⋯ ≤ fn(t) for all t between the functions {fi(t)}. We further show that the optimal sequence to minimize the total cost TC = σ fi(Ci) can be constructed by a dynamic programming algorithm. For the stochastic model, we study three optimization criteria: (A) almost sure minimization; (B) stochastic ordering; and (C) expected cost minimization. For criterion (A), we show that the results for the corresponding deterministic model can be easily generalized. However, stochastic problems with criteria (B) and (C) become quite difficult. Conditions under which the optimal solutions can be found for these two criteria are derived.
ISSN: 0894-069X
EISSN: 1520-6750
DOI: 10.1002/nav.20021
Appears in Collections:Journal/Magazine Article

View full-text via PolyU eLinks SFX Query
Show full item record


Last Week
Last month
Citations as of Feb 8, 2019


Last Week
Last month
Citations as of Feb 11, 2019

Page view(s)

Last Week
Last month
Citations as of Feb 18, 2019

Google ScholarTM



Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.