Parallel Machine Scheduling Problems
This chapter, presents some results on scheduling jobs on parallel machines in the Competitive and the Interfering scenarios. First, we study the case where job preemption is allowed, i.e. when the processing of a job can be interrupted and resumed later,
- PDF / 502,269 Bytes
- 27 Pages / 439.36 x 666.15 pts Page_size
- 85 Downloads / 235 Views
Parallel Machine Scheduling Problems
This chapter presents some results on scheduling jobs on parallel machines with the COMPETITIVE and the INTERFERING scenario. First, we study the case where job preemption is allowed, i.e. when the processing of a job can be interrupted and resumed later, eventually on another machine. Next, we study the case without job preemption. The chapter is composed of five sections. In Sect. 5.1, we consider parallel machine scheduling problems without job preemption. In Sects. 5.2 and 5.3, we consider preemptable parallel machine scheduling problems with arbitrary and equal job processing times, respectively. We end the chapter with Sects. 5.4 and 5.5 including, respectively, complexity tables and bibliographic remarks.
5.1 Preemptive Jobs In this section, we assume that preemption is allowed, i.e., a job processing can be interrupted and resumed later, possibly on another machine. Scheduling jobs on parallel machines when preemption is allowed has attracted researchers’ attention for a long time (Brucker 2007; Pinedo 2008). Mc Naughton studied preemptive independent job scheduling problems with various objective functions (Mc Naughton 1959). In particular, the author proposes a polynomial time algorithm for solving problem PmjpmtnjCmax . Mc Naughton’s algorithm can be described as follows: select the jobs one by one in any order and fill up the machines M1 ; M2 ; : : : ; Mm within the time interval Œ0; LB, where LB is a lower bound for the makespan. We have: LB D max
n n1 X
m j D1
n
pj I max pj
o
j D1
A. Agnetis et al., Multiagent Scheduling, DOI 10.1007/978-3-642-41880-8__5, © Springer-Verlag Berlin Heidelberg 2014
189
190
5 Parallel Machine Scheduling Problems
For a given machine Mi that performs job Jj , if time LB is reached before the end of Jj , this job is preempted and its remaining processing time is performed at time 0 on the next machine MiC1 . Most of the classical multicriteria parallel machine scheduling problems deal with two criteria (see T’Kindt and Billaut 2006). For example, in Mohri et al. (1999), the authors study the PmjBI; pmtn; Cmax QjLmax problem for m D 2 or m D 3 machines. In the following, we focus on the COMPETING and INTERFERING scenarios.
5.1.1 Functions fmax ; fmax 5.1.1.1
B A Problem RmjIN; pmtn; Cmax QjCmax
We start by considering the case of unrelated machines in the INTERFERING scenario (in which we recall that J D J A J B ). In this section, a set M of m unrelated parallel machines is shared between two agents in order to schedule their sets of jobs, when they both want to minimize the makespan. B A While we illustrate how to solve problem RmjIN; pmtn; Cmax QjCmax , the whole procedure, with minor adjustments, can be applied to problem RmjIN; B A pmtn; fmax Qjfmax in which all jobs in Jj 2 J A hold the same linear, monotonically nondecreasing function of the jobs completion times fjA .Cj / D f A Cj and similarly fjB .Cj / D f B Cj for Jj 2 J B . Following the two-phase exact approach proposed for solving the classical B A
Data Loading...
