A common framework and taxonomy for multicriteria scheduling problems with Interfering and competing Jobs: Multi-agent scheduling problems

A Common Framework and Taxonomy for Multicriteria Scheduling Problems with Interfering and Competing Jobs: Multi-agent Scheduling Problems∗ Paz Perez-Gonzalez†Jose M. Framinan Industrial Management, School of Engineering, University of Seville. Camino de los descubrimientos s/n. 41092 Seville, Spain Abstract Most classical scheduling research assumes that the objectives sought are common to all jobs to be scheduled. However, many real-life applications can be modeled by considering different sets of jobs, each one with its own objective(s), and an increasing number of papers addressing these problems has appeared over the last few years. Since so far the area lacks a unified view, the studied problems have received different names (such as interfering jobs, multi-agent scheduling, mixed-criteria, etc), some authors do not seem to be aware of important contributions in related problems, and solution procedures are often developed without taking into account existing ones. Therefore, the topic is in need of a common framework that allows for a systematic recollection of existing contributions, as well as a clear definition of the main research avenues. In this paper we review multicriteria scheduling problems involving two or more sets of jobs and propose an unified framework providing a common definition, name and notation for these problems. Moreover, we systematically review and classify the existing contributions in terms of the complexity of the problems and the proposed solution procedures, discuss the main advances, and point out future research lines in the topic. Keywords: Scheduling; interfering jobs; multi-customer; multi-agent scheduling problems; sets of jobs; multicriteria. ∗This is an Accepted Manuscript of an article published by Elsevier in European Journal of Operational Research Volume 235, Issue 1, 16 May 2014, Pages 1–16, available online: http://dx.doi.org/10.1016/j.ejor.2013.09.017 †Corresponding author. Tel. +3495 448 7212; fax: +3495 448 7329. E-mail address: pazp[email protected] 1 1 Introduction The existence of several objectives is consubstantial to scheduling problems, as it can be seen from different definitions of the field, such as Pinedo (1995), where scheduling is defined as a decision-making process that has as a goal the optimization of one or more objectives. Therefore, it is not surprising that multicriteria scheduling problems have been widely studied in the scheduling literature (see e.g. the reviews by T’kindt and Billaut, 2001, 2002; Hoogeveen, 2005 and Minella et al., 2008). In all the problems analyzed in these surveys the criteria considered affect all jobs to be scheduled. Only Hoogeveen (2005) mentions the case of multicriteria scheduling problems with two or more sets of jobs. In these problems, two or more sets of jobs (not necessarily disjoint) have to be scheduled, each one with its own objective(s). Although this is a special case of multicriteria scheduling problems, the existence of several sets makes the problems rather different than their one-set counterpart as, in general, the complexity of these problems changes even if the objective functions are the same (Agnetis et al., 2004). As discussed later in this paper, this type of scheduling problems arise in a number of real-life applications and therefore have been subject of interest by researchers and practitioners in the last few years. However, the lack of a unified framework has been a major deterrent for research advances in the field. There is not even a common name which has caused some contributions to ignore past works on the topic, as the keywords and title of the existing results make it difficult to conduct an extensive search (for instance, the same conclusion regarding a specific problem is independently shown by Agnetis et al., 2007a and Nong et al., 2011). Without a common definition and name, the notation and limits for this kind of problems are not clear, which may have hidden valuable contributions and makes the comparison among similar problems very difficult. In addition, this has caused that some scheduling problems dealing with two types of jobs, but with no interference among them, were considered part of the topic. For instance, in some problems described in Leung et al. (2010), the jobs in one set have their due date to be equal to their release date plus their processing times. Therefore, these jobs have to be processed in a specific (fixed) time interval and the remaining scheduling problem is how to schedule the jobs in the other set, which can be assimilated to a traditional scheduling problem with machine unavailability. In this paper we will try to move towards an unified view on the topic that allows overcoming the above problems. More specifically, we 1) discuss the different definitions and approaches for the problem and provide a framework consisting of a single definition and notation, 2) give some complexity results and general properties, 3) review and classify the different contributions and results on the topic based on the aforementioned framework, and 4) point out the main research avenues in the field. By doing so, we expect to foster the research in this interesting and challenging scheduling area. The remainder of the paper is structured as follows: Section 2 discusses the problems, their applications and the different names used in the literature. In Section 3 we present the notation and adapt the taxonomy presented by T’kindt and Billaut (2002) for multicriteria scheduling problems. The relationship among the complexities, single criteria and multicriteria scheduling problems is outlined in Section 4, where some general properties are presented as well. Literature is reviewed by classifying the problems into basic problems (discussed in Section 5) if there are no conditions for the machines or jobs, i.e. the most general case 2 indicating only the machine environment and the objectives considered for each set of jobs; and extended problems (discussed in Section 6), where specific conditions are imposed. Finally, Section 7 contains the conclusions and future research lines. 2 Fields of application and problem definition We consider two or more set of jobs –not necessarily disjoint– competing or using common processing resources (machines). Each set of jobs has one objective, which may or may not be the same for each set. The objectives of some sets have to be optimized while others have to satisfy one or more constraints. This type of scheduling problems arise from many real-life fields of application (see Mor and Mosheiov, 2010): •Supply chain scheduling: In a supply chain, a classical problem is to minimize overall manufacturing and distribution costs integrating production and delivery. If the customers are competing for a common processing resource then the problem implies interfering jobs. Fan (2010) presents a scheduling problem where the customers are placed at different locations such that delivery times are given. The objective is to minimize the sum of time between job’s release and the delivery to the corresponding customer. •Rescheduling: Rescheduling can be defined as the process of updating an existing production schedule in response to disruptions or other changes (Herrmann, 2006), such as the arrival of new jobs to be processed. Rescheduling usually implies more than one set of jobs, so a standard rescheduling problem can be formulated as a two-agent scheduling problem (Leung et al., 2010). In this problem there are usually two sets of jobs: existing jobs which have been already scheduled and new jobs to be scheduled. In this problem, two cases may be distinguished (Pinedo, 1995): –The starting times of the existing jobs cannot be modified (‘frozen’ jobs), so the problem can be considered as a single criteria problem subject to machine/job availability constraints (see e.g. Perez-Gonzalez and Framinan, 2009, 2010a; Perez-Gonzalez et al., 2011). –The starting times of the existing jobs can be modified (existing jobs can be rescheduled). If the same objective is considered both for existing and incoming jobs, the problem is again a scheduling problem with one set of jobs. However, in many situations it makes sense to employ different objectives for each set: Some performance measure is minimized for incoming jobs in order to obtain a short completion time for this set of jobs (e.g. minimizing their makespan or flowtime), while the objective for the existing jobs aims to minimize the disruption from their initial schedule. The usual way to achieve the latter objective is either to minimize their tardiness or impose that these jobs cannot be tardy (see e.g. Unal et al., 1997; Perez-Gonzalez and Framinan, 2010b); or to consider special disruption measures as the differences between the completion times of the old jobs in the sequence before rescheduling and the new sequence (such as in e.g. Hall and Potts, 2004; Yuan and Mu, 2007; Yuan et al., 2007; Mu and Gu, 2010). •Telecommunications: Packet-switching networks usually support different applications, each one requiring the transmission of data packages that must reach their destination within some time limit. 3 The most important performance objective for some applications (such as file transfer or interprocess communication) is not to exceed certain mean delay, while for other applications (such as voice or video) is to achieve a specific loss rate. Therefore, the idea of several sets of jobs (packets belonging to applications) that must compete for the use of the same resource (the bandwidth) arises naturally. This problems have been addressed by Peha and Tobagi (1990); Peha (1995) and Meiners and Torng (2007). A similar problem is found in Arbib et al. (2004) for internet protocols, where one user wants to maximize the on-time packets transmitted to other user, while guaranteeing certain amounts of on-time packets to a third user. •Maintenance scheduling: Some references in the literature address problems about scheduling jobs and preventive maintenance simultaneously (see e.g. Cassady and Kutanoglu, 2003; Ruiz et al., 2007), considering only one criteria for the jobs. However, since production and maintenance have common resources (the machines) and their activities are actually often conflicting, integrated production and maintenance cooperative scheduling is an example of interfering job problems when we consider a multiobjective approach. Khelifati and Bouzid-Sitayeb (2011a) simultaneously address the problem of scheduling production and preventive maintenance operations, taking into account both production and maintenance criteria. Since most machines have to be maintained at regular intervals (i.e. they require given periods of time on each machine), maintenance tasks can be modelled as maintenance jobs to be scheduled along with production jobs. Since maintenance tasks have to be performed within a time window, each maintenance job has both a release date and a due date (representing the earliest and latest time for the task, respectively). The natural objective for scheduling the set of maintenance jobs is thus to minimize a function of the deviation from their release and due dates, while production jobs are scheduled to minimize some performance measure. This approach is adopted by Wan et al. (2010). Kellerer and Strusevich (2010) give an interpretation of their specific interfering job problem where machine(s) is(are) subject to a compulsory maintenance during the planning period, the length and the deadline of the maintenance operations are given, and the Decision Maker has to decide when to start the maintenance period, while an objective related to the jobs has to be minimized. It is to note that, there are several papers focusing on game theory aspects of the problems and its applications in industrial management, project scheduling, queuing setting, telecommunication services, economic markets, scheduling of trains, etc . . . These papers are originally cited in Agnetis et al., 2000, 2004, 2007a,b), and they are subsequently cited often by authors dealing with interfering jobs scheduling problems, but it is to note that problems addressed there are not interfering jobs problems, at least in view of the definition given here. This is (another) side effect of the lack of a common framework for the topic. Regarding the name employed to denote this type of problems, different authors have used different denominations: •Peha (1995) call heterogenous-criteria scheduling to the problems where jobs are divided in two classes, and the performance measure differs from class to class. Earlier, Peha and Tobagi (1990) call heterogeneous performance objectives to the same problem, but without an explicit definition. 4 •The term interfering job sets first appeared in the review about multicriteria scheduling by Hoogeveen (2005), defined as a scheduling problem with two sets of jobs competing for processing on a single machine. Interfering job sets or Interfering jobs were later used by Balasubramanian et al. (2009); Elvikis et al. (2009, 2010b); Huynh-Tuong and Soukhal (2009a,b, 2010) in the multi-machine context. Their definitions are not homogeneous: In the first reference, the definition expresses that the jobs belong to disjoint classes or sets with a criterion associated with each set, while for the latter authors the sets are not disjoint, and there is an objective function for all jobs subject to minimizing another objective function for a subset of jobs, calling this case global objective function (Huynh-Tuong et al., 2011; Sadi et al., 2012). •The most extended name is two agent or multi agent scheduling problems. In some cases it is called competing agents (Agnetis et al., 2004, 2009a; Fan, 2010; Huynh-Tuong et al., 2010; Kellerer and Strusevich, 2010; Mor and Mosheiov, 2010, 2011; Ding and Sun, 2011), being the main keyword agent. This concept was introduced by Agnetis et al. (2004) when addressing a scheduling problem in which two agents compete to perform their respective jobs on a common processing resource, each agent minimizing an objective function depending exclusively on the completion times of its jobs. In addition, other –less employed– names have been suggested, such as ‘competing users’ (Shen, 1998; Agnetis et al., 2000), ‘customers’ (Baker and Smith, 2003), ‘multiple job classes’ (Soltani et al., 2010), ‘multi-users’ (Saule and Trystram, 2009), ‘two families of jobs’ (Yuan et al., 2005), ‘mixed criteria scheduling problem’ (Meiners and Torng, 2007), or even ‘scheduling problem with a floating machine non-availability interval’ (Kellerer and Strusevich, 2010), motivated by the fact that there is a machine maintenance interval which is not fixed. Finally, Arbib et al. (2004) do not give a name for the problem. When trying to consolidate a name for the problem, it does not sound logic to choose one of these aforementioned less-employed names. Besides, multi-customer or multi-users do not imply a multicriteria problem, and ‘class’ or ‘family’ of jobs are terms used generally for batch scheduling which may be confusing. Similarly, ‘heterogeneous criteria’ and ‘mixed criteria scheduling problem’ imply different criteria for each set of jobs, so the case when the sets have the same objective is not considered. While agent is the most extended name, we think that it could also be confusing, as there is an extensive literature on scheduling with multi-agent systems without relationship with our problem (see e.g. Coudert et al., 2002; Shen et al., 2006). Multi-agent system is a subfield of Distributed Artificial Intelligence where a network of individual agents share knowledge and communicate with each other to solve a problem beyond the scope of a single agent (Balaji and Srinivasan, 2010). This approach can be applied to scheduling in order to solve problems with competitive and negotiating algorithms controlled by agents (see e.g. Khelifati and Bouzid-Sitayeb, 2011a), but many references do not consider two or more set of jobs to be scheduled. Finally, the term sets (or classes, or families) of jobs could be adopted, but it must be taken into account that there may be problems with several sets of jobs that do not necessarily compete for a resource, even if they have different objectives, and that these scheduling problem could be disaggregated into two singlecriterion scheduling sub-problems. 5 Regardless if each job belongs to an agent, is a part of a customer order, an operation of a department or user, belongs to disjoint sets or not, etc. the key feature is that the job interferes with other jobs for the same resources. Although we think that interfering jobs is the most suitable term to name our problem, the most employed is multi-agent scheduling problem (MASP) so it is the term selected. In the next section, we provide a common notation and taxonomy for these problems. 3 Notation and Taxonomy Multi-agent Scheduling Problems (MASPs) consider k= 2, . . . , K sets of nkjobs denoted J1, . . . , JK. We define n=∑K k=1 nkand J=J1∪· · · ∪JK. Each set Jkhas assigned a criterion fk. If Jk=Jfor some k, then fkis denoted by f. In this case the problem is called interfering jobs problem with global objective function. Each job j∈ J khas to be processed on machine iwith processing time pk ij,i= 1, . . . , m. If there is only one machine, its processing time is denoted pk j. Additionally, we define pk=∑m i=1 ∑j∈J kpk ij and P=∑m i=1 ∑j∈J pij. As many references deal with two disjoint sets of jobs (k= 2 J1∩ J 2=∅), we denote these sets as JAand JB, each one with nAand nBjobs, and objective functions fAand fB, respectively. Obviously, some special cases of this notation do not constitute MASPs. For instance, in the problem with two-sets, JA=∅(or JB=∅) constitutes a single-criterion scheduling problem, while JA=JBdenotes a standard (i.e. not competing) multicriteria scheduling problem. Such cases will not be treated here. A complete sequence σ= [σ1, . . . , σn] is a permutation of all jobs in J, where each σj,j= 1, . . . , n, is in some Jk. Given a sequence σ, the completion time of job σjin machine iis denoted as Cij (σ), being Cj(σ) the completion time of job σjin the last machine on which this job needs to be processed. Without loss of generality, we omit σin the completion times unless necessary. A classification for MASPs can be obtained extending on the standard triplet α|β|γnotation by Graham et al. (1979) (see Pinedo, 1995 for a complete description). The αfield represents the machine environment, i.e. including the single machine (1), identical machines in parallel (Pm), machines in parallel with different speeds (Qm), unrelated machines in parallel (Rm), flowshop (Fm), jobshop (Jm), or openshop (Om). We denote the case of the permutation flowshop (PFm) in order to obtain a clearer taxonomy of the problems with an empty βfield (in the standard notation, the permutation condition in flowshops is indicated in the field βby the notation prmu). βindicates conditions applying to jobs. If a condition is applied only in some sets, then it is indicated by a super-index. Usual restrictions are: •Time-related conditions, such as release dates (rj) and common due dates (dj=d), •Processing-times-related conditions: such as preemption (prmp); learning effect (learning) / deteriorating jobs (deteriorating) i.e. processing times decrease/increase with the starting time or the position of the job in σ; controlable processing times (ctrl), i.e. pk ij is a variable in the problem and can be chosen in a given interval [pk ij, pk ij], with a cost of the compression of the processing times, ck ij, which is penalized in the objective function by Ctrlk sum =∑m i=1 ∑j∈J kck ij(pk ij −pk ij); and on-line problems 6 (on-line), when processing times only become known on arrival, opposite to off-line problems, which is the usual case, when processing times are known in advance. •Batch-related constraints (batch). Parallel batch (p-batch) indicates that a machine can process up to bjobs simultaneously, being the processing time of a batch equal to the largest processing time of the jobs in the batch. In serial batching (s-batch), jobs are processed sequentially with a setup time for each batch (i.e. setup time between two jobs is equal to zero if both jobs are scheduled in the same batch). This case is also called family/part type-dependent setup times, including the case where a family is determined by a set of jobs. There may be batch capacity restrictions (denoted as b≤x, otherwise we assume b=∞), where each job has a size sizej. Finally, there may be incompatible sets (IS) if jobs from different sets cannot be placed in the same batch. •Availability constraints. A case treated in the literature is that of forbidden intervals (I), denoting a time interval where no jobs can be scheduled. The number of forbidden intervals is denoted by n∗. •Precedence. This condition can be applied to machines or jobs: Machine precedence is denoted as mi7→ mjindicating that jobs must be processed by machine mibefore entering in machine mj. Job precedence is denoted prec. Usually, γincludes the objective function to be minimized. In our proposal, it contains a model indicating the performance measures fkused for each set of jobs Jk. Different problems or approaches can be defined using the functions fk. In order to unify the notation, we integrate some of the multicriteria approaches in T’kindt and Billaut (2002) with those found in the MASP literature: •Linear Convex Combination (LCC) approach: We denote Fl(f1, . . . , fK) if the objective is to minimize a linear convex combination of the Kcriteria, ∑K i=1 λifi, where ∑K i=1 λi= 1. •Epsilon-constraint (ϵ-constraint) approach: We denote ϵ(f1/f2, . . . , fK), if the objective is to minimize f1subject to fk≤ϵk,ϵk≥0 for k= 2, . . . , K. Constraints can be defined for all or for some fk, i.e. ϵk= +∞for some values of k. An instance of an ϵ-constraint problem may not have feasible solutions, and it is denoted feasible if there is at least one feasible solution. •Pareto approach: We denote #(f1, . . . , fK) if the objective is to enumerate all Pareto optima. A schedule σis weak Pareto optimum if and only if @σ′such that ∀k= 1, . . . , K,fk(σ′)< fk(σ), and it is strict Pareto optimum (or efficient solution or nondominated solution) if and only if @σ′such that ∀k= 1, . . . , K,fk(σ′)≤fk(σ) (fk(σ′)< fk(σ)), with at least one strict inequality. Other approaches found in the literature are Goal Programming and Lexicographical approach. The goal programming approach, denoted GP(f1, . . . , fK), also named feasibility model or decision model, is the special case ϵ(f/f1, . . . , fK), with fconstant. The goal here is to find a feasible schedule σsatisfying fk≤ϵk,k= 1, . . . , K. The lexicographical approach, denoted Lex(f1, . . . , fK), minimizes all criteria in the given order. 7 Note that the order in which fkare considered is only relevant for the ϵ-constraint and the lexicographical approaches, as different orders imply different problems. For each approach, different forms of fkcan be considered. Cheng et al. (2006) distinguish two types depending on the functions gk japplied to the completion times Ck j,j∈ J k,k= 1, . . . , K, i.e.: max-form: max fk= max1≤j≤nkgk j(Ck j), and sum-form:∑fk=∑1≤j≤nkgk j(Ck j). When the jobs are weighted, we denote the functions max wkfkand ∑wkfkrespectively. If gk jare non-decreasing functions of Ck jfor all j∈ J k, then they are called regular performance measures (see e.g. Pinedo, 1995). We denote a regular performance measure with capital letter. Among non-regular performances measures, only those related to earliness, defined as Ej= max{0, dj− Cj}, have been found in the review. These performance measures, jointly with the related to the tardiness defined below, are called just in time performance measures (see e.g. T’kindt and Billaut, 2002 for more information). Table 1 summarizes the regular and non-regular performance measures encountered in the literature. The usual definitions for lateness (Lj=Cj−dj), tardiness (Tj= max{Cj−dj,0}), and unit penalty (Ujyields 1 if Cj> dj, 0 otherwise) apply. Type Function form Regular Due date independent Max-form Maximum cost max Fk j= maxj∈J kgk j(Cj) Makespan (Weighted) max Ck j= maxj∈J kCj(max wk jCk j= maxj∈J kwjCj) Sum-form Sum of costs ∑Fk j=∑j∈J kgk j(Cj) Flowtime (Weighted) ∑Ck j=∑j∈J kCj(∑wk jCk j=∑j∈J kwjCj) Due date dependent Max-form Maximum lateness max Lk j= maxj∈J kLj Maximum tardiness max Tk j= maxj∈J kTj Sum-form Total tardiness (Weighted) ∑Tk j=∑j∈J kTj(∑wk jTk j=∑j∈J kwjTj) Number of tardy jobs (Weighted) ∑Uk j=∑j∈J kUj(∑wk jUk j=∑j∈J kwjUj) Non regular Due date dependent Max-form Maximum earliness max Ek j= maxj∈J kEj Sum-form Total earliness (Weighted) ∑Ek j=∑j∈J kEj(∑Ek j=∑j∈J kwjEj) Table 1: Usual performance measures for MAPSs Finally, we also analyse performance measures employed in the rescheduling literature in order to include them in the notation proposed. In rescheduling, usually two sets of jobs are considered: old jobs JO, and new jobs JN, as well as two schedules: an initial sub-sequence σo, formed by jobs in JO, and a final sequence obtained when jobs have been rescheduled σn, formed by jobs in J=JO∪JN. There are two approaches depending on σo(Hall and Potts, 2004): to consider a single disruption, so the original schedule is optimal with respect to the initial scheduling objective, or to consider the most recent of multiple disruptions, so the initial schedule is regarded as arbitrary due to previous disruptions. 8 Different ways to measure the disruption of jobs in JOcan be considered: 1. No tardy jobs constraint. In this case, jobs in JOcannot be late, which means that Cj≤dj,∀j∈ J O. There are several (equivalent) ways to model this constraint, such as max LO j≤0, max TO j= 0 (equivalent to max TO j≤0), ∑TO j= 0 (equivalent to ∑TO j≤0), and ∑UO j= 0 (equivalent to ∑UO j≤0). All of these models have a weighted counterpart. Note that these constraints are on the form of an ϵ-constraint approach. If the objective is to minimize fsubject to no tardy jobs for the set JO, it is denoted as 0(f/fO), with fO∈ {max Lj,max Tj,∑Tj,∑Uj,max wjTj,∑wjTj,∑wjUj}. 2. Sequence disruption: Dj(σo, σn) = |y−x|with ythe position of the job jin σo, and xits position in σn. When there is no ambiguity, the notation is simplified to Dj, with objectives max Djand ∑Dj. 3. Time disruption: ∆j(σo, σn) = |Cj(σn)−Cj(σo)|. When there is no ambiguity, the notation is simplified to ∆j, with objectives max ∆jand ∑∆j. Depending on the approach, machine setting, objective function, etc, there are many different problems in the literature. A broad classification is to divide the problems into basic problems (i.e. when there are no conditions for the machines or jobs, i.e. the most general case indicating only the machine environment and the objectives considered for each set of jobs) and extended problems (i.e. where specific conditions are imposed). Prior to this classification, it is useful to recall the complexity of the different problems and to derive general properties that may apply to some approaches. Both aspects are discussed in the next section. 4 Complexity and General Properties 4.1 Complexity Many contributions in the literature about MASPs are devoted to classify and/or determine the complexity of different problems. In the same way as in single criterion and classical multicriteria scheduling problems, the complexities of some MASPs can be determined by reductions to known problems. In this subsection we intend to give a first step to determine the relationship between the complexities of MASPs and known problems. Complexity theory is based on languages theory and Turing machines (see Garey and Johnson, 1979). A problem belongs to a class of complexity, which informs us of the complexity of the “best algorithm” able to solve it (T’kindt and Billaut, 2002). We know the complexity of a problem if it can be reduced from/to another problem with a known complexity. A search (decision) problem π′is NP -hard (NP-complete) if and only if another search (decision) problem πis NP-hard (NP-complete) and a reduction of πtowards π′ exists. The problem π′is at least as difficult to solve as the problem π.NP -hard problems are also called NP-hard in the ordinary sense, ordinary NP-hard, binary NP-hard problems, or weakly NP-hard. A subclass of NP-hard problems are the so-called strongly NP-hard problems (NP-hard in the strong sense or unary NP-hard). For detailed definitions we refer the reader to Garey and Johnson (1979); Gawiejnowicz (2008); T’kindt and Billaut (2002). 9 fA\fBmax Fj∑Cj∑wjCj∑Tj∑Uj∑wjUj max FjO((nA)2+nBlog nB)O(nAlog nA+nBlog nB) NP NP O(nAlog nA+nBlog nB) NP ∑CjNP NP NP NP NP ∑wjCjNP NP s-NP s-NP ∑TjNP NP NP ∑UjO(nnAnB) NP ∑wjUjNP Table 3: Complexity for basic MASPs with two disjoint set of jobs on a single machine for ϵ-constraint approach ratio. 5.1.2 ϵ-constraint approach In this section, we review the problem when the sets of jobs are disjoint considering the ϵ-constraint approach. Most studies are devoted to one-machine layout and two sets of jobs. Table 3 summarizes the complexities for 1||ϵ(fA/fB) when fAand fBare regular functions. For the single machine case, Agnetis et al. (2004) proved that the symmetric problems are equivalent, since it is possible to reduce 1||ϵ(fB/fA) from 1||ϵ(fA/fB) by a binary search in a logarithmic number of instances. Then, in the same way that the LCC approach, we have indicated the complexities in the upper part of a triangular matrix. These problems have been studied by Agnetis et al. (2004); Ng et al. (2006); Agnetis et al. (2007a, 2009a); Leung et al. (2010). The general case 1||ϵ(max FA j/max FB j), with max Fjregular is polynomial (Agnetis et al., 2004, 2007a). This result is extended by Agnetis et al. (2004) for more than two sets of jobs, giving Agnetis et al. (2007b) an algorithm for the goal programming counterpart. Moreover, Agnetis et al. (2004) prove that 1||ϵ(∑wA jCA j/max FB j) is NP-hard by proving that the goal programming counterpart is NP-complete, although 1||GP(∑C1 j,max F2 j, . . . , max FK j) is polynomial in O(n1log n1+n′log n′), with n′=∑K k=2 nk (Agnetis et al., 2007b). Although 1||ϵ(∑wA jCA j/max FB j) is NP-hard, the case with max LB jis shown to be strongly NP-hard by Ng et al. (2006). The case 1||ϵ(∑wA jCA j/max CB j) is addressed by Kellerer and Strusevich (2010) by means of an FPTAS. They show it to be equivalent to a single criterion problem with one fixed non-availability machine interval in the case that the non-availability is resumable and the total weighted completion time as objective. As we can see in Table 3, the problem 1||ϵ(∑wA jCA j/∑wB jCB j) is NP-hard. This complexity also holds for more than two sets of jobs (Lee et al., 2009). These authors provide an FPTAS to solve the goal programming version of this problem for the single machine and the unrelated parallel machines. In the same way, Agnetis et al. (2004) find 1||ϵ(∑U1 j/∑U2 j, . . . , ∑UK j) to be polynomially solvable since 1||ϵ(∑UA j/∑UB j) is polynomially solvable too. This result implies that the goal programming counterpart is polynomial too, although the weighted version 1||GP(∑w1 jU1 j,...,∑wK jUK j) is proved to be strongly NP-complete by Cheng et al. (2006). These authors present an FPTAS for the problem and prove that it is polynomial when Kis arbitrary and the weights and epsilon values of all sets are positive integers. Related to 16 the latter problem, Agnetis et al. (2007a,b) obtain a O(∑K′ k=1 nk∏K k=1 nk+nlog n) running time algorithm for the problem 1||GP(∑w1 jU1 j, . . . , ∑wK′ jUK′ j,max fK′+1 j, . . . , max fK j). Regarding problems considering non-regular performance measures, Mor and Mosheiov (2010) study the general case where max fk j= maxj∈J k{fk j(Ek j)}, with k=A, B, providing an algorithm to solve the problem in polynomial time with O(nBlog nB+ (nA)2). With respect to other layouts different from the single machine, although 1||ϵ(max CA j/max CB j) is trivial, the ϵ-constraint problem with the same objective is shown to be NP-hard for even the 2-machine open shop (Agnetis et al., 2004) and, consequently, for the permutation flowshop (Luo et al., 2011). For the last problem, Luo et al. (2011) provide an FPTAS. A consequence is that PFm||ϵ(max CA j/max TB j) is NP-hard, and the structure of the solutions is studied by Perez-Gonzalez et al. (2011) for common and different due dates. PF2||ϵ(∑CA j/∑UB j) and PF2||ϵ(∑TA j/∑UB j) are both NP-hard (Lee et al., 2011, 2010). The authors present B&B as well as SA algorithms for both problems. Finally, there are some rescheduling problems where the objective is to minimize a function of one set of jobs subject to that one or more functions of the other set to be bounded. All of them have the form 1||ϵ(fA/fB 1, fB 2), and are presented in Table 4. Some properties about feasibility and conditions for optimal schedules are given by Mu and Hao (2010) for 1||ϵ(fA/fB,max DB j) and 1||ϵ(fA/fB,max ∆B j) when fA, fB∈ {max Cj,∑Cj,max Lj}. Polynomially solvable algorithms for 1||ϵ(max CA j/max CB j,max DB j) and 1||ϵ(max CA j/max CB j,max ∆B j) are given by Mu and Gu (2010). The rest of the problems can be solved by dynamic programming algorithms (Mu and Gu, 2010; Mu and Hao, 2010). fB 2 max Dj∑Djmax ∆j∑∆j 1||ϵ(max CA j/max CB j, fB 2)O(nAlog nA)O((nA)2(nB)2ϵ1)O(nAlog nA)O((nB)2(nA)2pAϵ1) 1||ϵ(∑CA j/∑CB j, fB 2)O(nB(nA)2ϵ1)O((nB)2(nA)2ϵ1)O(nBnApAϵ1+nAlog nA)O(nB(nA)2pAϵ1) Table 4: Complexity of the algorithms to solve basic multiagent rescheduling problems on a single machine for LCC approach with the form 1||ϵ(fA/fB 1, fB 2) 5.1.3 Pareto approach In this section, we review the problem of finding the set of Pareto optima when there are disjoint sets of jobs. As discussed in Section 4, some authors only provide an algorithm to determine the size of the nondominated sets. For 1||#(max FA j,∑CB j), the size of the non-dominated set is at most nAnB(Agnetis et al., 2004, 2007a). Agnetis et al. (2004, 2007b) provide procedures to determine the size of the non-dominated set with complexity O(nAlog nA+nBlog nB). For the weighted case, 1||#(max FA j,∑wB jCB j), Agnetis et al. (2007b) show that it may have an exponential number of non-dominated solutions with respect to the instance size. The case with parallel machines Pm||#(max CA j,∑CB j), is shown to be NP-hard by Balasubramanian et al. (2009), developing several constructive heuristics and a GA. Saule and Trystram (2009) show that Pm||#(max C1 j, . . . , max CK j) is strongly NP-hard, and provide an approximation algorithm for the problem for an arbitrary number of machines. 17 Agnetis et al. (2004) prove that finding one non-dominated solution for 1||#(∑CA j,∑CB j) is NP-hard, and the number of non-dominated solutions may be exponential with respect to the instance size. Saule and Trystram (2009) study the case with more than two sets, 1||#(∑C1 j, . . . , ∑CK j), proposing an approximation algorithm and extending the approach to Pm||#(∑C1 j, . . . , ∑CK j). Lee et al. (2009) develop the same approximation algorithm for the goal programming counterparts 1||GP(∑C1 j, . . . , ∑CK j) and Rm||GP(∑C1 j, . . . , ∑CK j). For the weighted case 1||#(∑wA jCA j,∑wB jCB j), an algorithm based on the Nash Bargaining Solution is proposed by Agnetis et al. (2009b). For 1||#(∑w1 jC1 j, . . . , ∑wK jCK j) with K fixed, Lee et al. (2009) develop an FPTAS for computing a δ-efficient set (according to the definition given by Warburton, 1987), with δthe error bound. Additionally, Saule and Trystram (2009) consider the case for parallel machines, P m||#(∑w1 jC1 j, . . . , ∑wK jCK j), developing approximation algorithms for this problem and Pm||#(∑w1 jC1 j, . . . , ∑wK′ jCK′ j,max CK′+1 j,· · · ,max CK′′ j) with K=K′+K′′. Finally, Agnetis et al. (2000) consider a job shop problem, J2||#(fA, fB), assuming that both JAand JBcontain only one job with nAand nBoperations, and fAand fBnon-regular cost functions fi(Ci). For this problem, the set of nondominated schedules is identified, and an algorithm to generate them in polynomial time is provided. The running time depends on the number of incompatible pairs, defined as a pair of operations of JAand JBwhich require the same machine and cannot be done in parallel. 5.2 Non-disjoint (Interfering) sets of jobs 5.2.1 Linear Convex Combination approach For this approach, only one machine problems have been studied. Table 5 shows the complexity of these problems with global objective for some regular measures analysed by Huynh-Tuong et al. (2011) and Huynh- Tuong and Soukhal (2010). f\fBmax Cjmax Lj∑Cj∑wjCj∑Tj∑wjTj∑Uj∑wjUj max Cjtrivial O(nlog n)O(nlog n)O(nlog n) NP NP NP NP max LjO(nlog n)O(nlog n)O(n2) NP NP NP NP NP ∑CjO(nlog n) Open O(nlog n)O(nlog n) NP NP NP NP ∑wjCjO(nlog n) NP O(nlog n)O(nlog n) NP NP NP NP ∑TjNP NP NP NP NP NP NP NP ∑wjTjNP NP NP NP NP NP NP NP ∑UjO(nlog n) Open NP NP NP NP NP NP ∑wjUjNP NP NP NP NP NP NP NP Table 5: Complexity for basic MASPs with global objective function on a single machine for LCC approach (Huynh-Tuong et al., 2011; Huynh-Tuong and Soukhal, 2010) Hall and Potts (2004) study several rescheduling problems, shown in Table 6. They consider JAas the set of old jobs, and Jis the set of old and new jobs. Objective functions are f∈ {∑Cj,max Lj} and fA∈ {max DA j,∑DA j,max ∆A j,∑∆A j}, considering all of them with a single disruption. Additionally, 18 the study includes the case with multiple disruption (md) for the problem 1||Fl(∑Cj,max DA j). Finally, 1||Fl(max wjTj,∑FA j) is addressed by Li and Cheng (1999), with JAthe set of the new jobs. The objective is to determine the due dates of the new jobs which are calculated depending on their completion times by considering ∑FA j=∑j∈J Adj(Cj) as a function cost. The problem is shown to be NP-hard, although the unweighted version is polynomially solvable in O(n4). f\fAmax Dj∑Djmax ∆j∑∆j ∑CjO(n+nAlog nA); (md) O(nAn3)O(nBlog nB)O(n+nBlog nB)O(nBlog n) max LjO(n+nBlog nB) NP O(n+nBlog nB) NP Table 6: Complexity for basic multiagent rescheduling problems with global objective function on a single machine for LCC approach (Hall and Potts, 2004) 5.2.2 ϵ-constraint approach Similar to the LCC approach, the single machine layout is the most extended case, all of them with global objective function. Taking into account that the problem is not symmetric, most of them have the form 1||ϵ(f/fA), whereas 1||ϵ(fA/f) has not been tackled in the literature. Table 7 shows the complexity of these problems for some regular measures given by Huynh-Tuong et al. (2011) and Huynh-Tuong and Soukhal (2010). Additionally, the problem with more than two sets of jobs 1||ϵ(max Fj/max F1 j, . . . , max FK j) is polynomially solvable in O(n2) (Sadi et al., 2012). For this approach, Hall and Potts (2004) study some rescheduling problems whose complexities are shown in Table 8. All problems are studied with a single disruption, and for several cases where there may be several job arrivals, multiple disruptions (md) are included. Finally, Sadi et al. (2012) show that Pm||ϵ(f/fA) is NP-hard if fA, f ∈ {max Lj,∑Cj,∑wjCj,∑Uj,∑wjUj,∑Tj,∑wjTj}. They also give a dynamic programming algorithm to solve the problem for m= 2 and fA, f ∈ {max Cj,∑Cj}in running time O(n2ϵ). f\fBmax Cjmax Lj∑Cj∑wjCj∑Tj∑wjTj∑Uj∑wjUj max Cjtrivial O(nlog n)O(nlog n) NP NP NP Open NP max LjO(nlog n)O(nlog n)O(nlog n) NP NP NP Open NP ∑CjO(nlog n) Open NP NP NP NP NP NP ∑wjCjO(nlog n) NP NP NP NP NP NP NP ∑TjNP NP NP NP NP NP NP NP ∑wjTjNP NP NP NP NP NP NP NP ∑UjO(n2) NP NP NP NP NP Open NP ∑wjUjNP NP NP NP NP NP NP NP Table 7: Complexity for basic MASPs with global objective function on a single machine for ϵ-constraint approach (Huynh-Tuong et al., 2011; Huynh-Tuong and Soukhal, 2010) 19 f\fAmax Dj∑Djmax ∆j∑∆j ∑CjO(n+nAlog nA); (md) O(n3)O((nAnB)2)O(n+nAlog nA) s-NP max LjO(n+nAlog nA) Open O(n+nAlog nA); (md) NP NP; (md) NP Table 8: Complexity for basic multiagent rescheduling problems with global objective function on a single machine for ϵ-constraint approach (Hall and Potts, 2004) 5.2.3 Pareto approach In this case, we are only aware of the work by Ben Ltayef et al. (2009), who address the PF2||#(max Cj, fA) and PF2||#(max Tj, fA) problems, where fA∈ {∑DA j,max DA j,∑∆A j,max ∆A j}. They give the mathematical formulation for these problems, and present solution procedures based on SA and TS. 6 Extended problems Extended problems have some condition/s for jobs and/or machines, indicated in the field β. In the next subsections, we review the main contributions for each approach. Note that, given the heterogeneity of the problems addressed, it is not possible to clearly classify the contributions as in the case of basic problems. Nevertheless, we have identified the following categories: Release times and/or preemption; Variable processing times (processing times are not fixed values); Batch and/or set-up; and Others. These categories should be interpreted in a loose manner and only as a way to classify the disparity of contributions. 6.1 Disjoint (Competing) sets of jobs 6.1.1 Linear Convex Combination approach Release times and/or preemption Regarding problems in which release times are allowed, 1|rj|Fl(max CA j,max CB j) is shown to be NP-hard by Ding and Sun (2010), who also give an optimal algorithm with O(nA+nB) running time for its preemptive version. For the on-line case, i.e. 1|on-line, rj, prmp|Fl(max CA j,max CB j) they develop an approximation algorithm. The equivalent problem without preemption, 1|on-line, rj|Fl(max CA j,max CB j), is also addressed giving an on-line algorithm with a lower bound of the competitive ratio of the problem. Different contributions are due to Cheng et al. (2008) for some specific cases with more than two sets and regular performance measures. They prove that 1|prec, I, prmp|Fl(F1, . . . , FK) and 1|prec|Fl(F1, . . . , FK) can be solved in pseudo-polynomial time when Kis fixed. Finally, the case without precedence 1|I, prmp|Fl(F1, . . . , F K) is polynomial with O((n∗log n∗+nlog n)(∏K k=1 nk)K), where n∗is the number of forbidden intervals, when Fk∈ {max wA jCk j,max Lk j}. 6.1.2 ϵ-constraint approach Release times and/or preemption 20 The assumption of preemption for all jobs in both sets has only been studied for the problem 1|prmp|ϵ(∑UA j/max FB j) by Agnetis et al. (2004), who show that it is solvable in O(nAlog nA+nBlog nB). The case 1|prmp, rj|ϵ(max FA j/max FB j) where release times for all sets of jobs are added to the preemption hypothesis is addressed by Leung et al. (2010),who show that is polynomially solvable in O(n2). This complexity can be further reduced to O(nAlog nA+nBlog nB) when the criterion for JAis max LA jor ∑CA j, and to O(n3(nAnB)2) when it is ∑UA j. Moreover, they show that 1|prmpA, rj|ϵ(∑CA j/max TB j) and 1|prmpA, rj|ϵ(max LA j/max TB j) are solvable in O((nA)nB+1 log nA) when ϵ= 0. Finally, they study some problems on parallel machines: P2|prmp|ϵ(∑CA j/maxFB j) is solvable in O(nAlog nA+nBlog nB) (this result is shown by Wan et al. (2010) too). However, the problem with release dates for all jobs is NP-hard when m≥2 and fixed. Additionally, P m|prmp|ϵ(∑UA j/max FB j) is solvable in O(n2nAnB) for m= 2, in O(n3m−5(nA)2(nB)2) time for m > 2 and fixed, and NP-hard when mis arbitrary. Furthermore, they show that the assumption of release dates transform the problem into NP-hard even for m≥2 and fixed. Finally, the problem Pm|prmp|ϵ(max FA j/max FB j) is solvable in O(log(αU−αL)nlog(nm)), where αU= maxj∈J A{FA j(P)}and αL= minj∈J A{FA j(0)}. When release times are considered, the complexity is O(log(αU−αL)n3). Leung et al. (2010) show that 1|rB j|ϵ(max FA j/max TB j) is NP-hard. Note that this result, although developed independently from Ding and Sun (2010), is a consequence of the NP-hardness of the 1|rj|Fl(max CA j/max CB j) shown by the latter authors. The problem is NP-hard too for the criteria ∑CA j and ∑UA j. However, if preemption is allowed, all corresponding problems are polynomially solvable. Yin et al. (2012b) consider two problems with release dates for all jobs. First, they prove that 1|rj|ϵ(∑CA j/max LB j) is strongly NP-hard. Therefore, 1|rj|ϵ(∑TA j/max LB j) is strongly NP-hard too, and they present a mixed integer programming model, a B&B with some dominance rules and a marriage in honey-bees optimization algorithm. Cheng et al. (2007) study different problems with preemption, precedence constraints and forbidden intervals. They show that the problems 1|prmp, I, precB|ϵ(∑FA j/max FB j) can be polynomially reduced to 1|prmp, I|∑FA jin O((nB)2+n∗log n∗), solving it in (O((nB)2+nAlog nA+n∗log n∗)) when ∑FA j∈ {∑CA j,∑UA j}. Finally, for more than two sets of jobs, Agnetis et al. (2007b) address 1|prmp|ϵ(F1/max F2 j, . . . , max FK j) and 1|prmp, I|ϵ(F1/max F2 j, . . . , max FK j) in order to discover some properties that were later applied to their basic counterpart. Pm|prmp|ϵ(∑Fj/∑F1 j, . . . , ∑FK j) is considered by Sadi et al. (2012), showing that it is NP-hard. They present a linear programming model for the general case with un-related machines in parallel. Variable processing times The references reviewed in this section assume that the processing times are not fixed in advance. They include deteriorating jobs, learning effect and controllable processing times. For the 1|deteriorating|ϵ(max FA j/max FB j) problem, Yin et al. (2012a) give a polynomial time algorithm with running time O((nA)2+nBlog nB). 1|deteriorating|ϵ(max LA j/max CB j) and linear deterioration is shown to be O(nAlog nA) by Liu and Tang (2008); Liu et al. (2010a, 2011b). There are no such general results when both functions are not under the max form. However, 21 there are algorithms to optimally solve a number of problems in O(nAlog nA+nBlog nB), such as 1|deteriorating|ϵ(∑CA j/max FB j) with linear deterioration depending on the starting time (Liu and Tang, 2008; Liu et al., 2011a,b) and with linear deterioration depending on the position of the jobs (Liu et al., 2010c); as well as for 1|deteriorating|ϵ(∑EA j/max FB j) and 1|deteriorating, dA j=d|ϵ(∑wA jEA j/max FB j) (Yin et al., 2012a). The problem 1|deteriorating|ϵ(∑TA j/∑UB j) with ϵ= 0 is tackled by Gawiejnowicz et al. (2010) and Gawiejnowicz et al. (2011). In the first reference, the authors develop a B&B combined with simple heuristics and local search, while in the second present an evolutionary algorithm. Liu et al. (2010b) study the problem 1|deteriorating, s-batch|ϵ(∑CA j/max FB j), where the processing times as well as the setup times of each job are linear functions of its starting time. They tackle two problems depending on the type of the deteriorating function, proposing two algorithms to solve both problems in O(nAlog nA) time respectively. Regarding the learning effect, 1|learning|ϵ(∑CA j/max FB j) is shown to be solvable in O(nAlog nA+ nBlog nB) if there is a linear deterioration depending on the position of the jobs (Liu et al., 2010c). For the 1|learning|ϵ(∑Tj/∑Uj) problem with ϵ= 0, Wu et al. (2011a) present a B&B and develop heuristic algorithms for larger instance sizes. The problem 1|learning|ϵ(∑wA jCA j/∑UB j) with ϵ= 0 is addressed by Cheng et al. (2011a) with a position based function. They show that the problem is NP-hard since the corresponding basic case is already NP-hard (Ng et al., 2006), and propose a B&B and three SA-based algorithms. The combination of position-based- learning and deteriorating effects is addressed by Cheng et al. (2011b), as they show that the 1|learningA, deterioratingB|ϵ(∑CA j/max LB j) problem is NP-hard. A B&B is proposed, as well as several SA-based algorithms. Wu et al. (2011b) address the same problem with a different position-based function. Again, a B&B and metaheuristics based on ACO are provided and compared. Regarding controllable processing times, Wan et al. (2010) address several 1|ctrl|ϵ(fA/fB) problems: •For the objective ϵ(CtrlA sum/max LA j,max FB j) with ϵ= (0, ϵB), the problems where βis ctrlA, rA j, prmp;ctrlA, rj, prmp; and ctrlA, prmpAare shown to be polynomial with running time O(n(log n+k+ 1)), with kthe number of different costs of JA. However, the case where βis ctrlA, rA j, prmpAis strongly NP-hard. •When βis ctrlAand ctrlA, prmpA, the problem with objective ϵ(CtrlA sum +∑CA j/max FB j) is polynomial with running time O((nA)2nBnlog n), and O((nA)2nBn) for ϵ(CtrlA sum + max TA j/max FB j) and ϵ(CtrlA sum +max LA j/max FB j). However, when βis ctrlA, rA j, prmpAall of them are strongly NP-hard. Finally, for the parallel machines case, the problem P2|ctrlA, prmp|ϵ(∑FA j+∑CA j/max FB j) is shown to be polynomially solvable in O(nBlog nB+ (nA)3+ (nA)2nB) by Wan et al. (2010). Batch and/or set-up The p-batch case has been studied by Li and Yuan (2011) for different forms of fAand fB, including both incompatible and compatible sets of jobs. Table 9 shows the complexities and the running times in the pseudo-polynomial and polynomial cases on a single machine, where αU= maxj∈J A{fA j(P)},P=∑j∈J pj and αL= minj∈J A{fA j(0)}. 22 ϵ(max FA j/max FB j)ϵ(∑FA j/max FB j)ϵ(∑FA j/∑FB j)ϵ(∑wA jCA j/max CB j) CS O(nlog nlog(αU−αL)) O(n2P)O(n2ϵP) NP IS O(nnAnBlog(αU−αL)) O(nnAnBP)O(nnAnBϵP) NP ϵ(∑wA jCA j/∑CB j)ϵ(max LA j/max FB j)ϵ(∑UA j/∑UB j)ϵ(∑UA j/max FB j) CS NP O(nlog nlog P)O(n2nAnB)O(n2nA) IS NP O(nnAnBP)O(n2(nA)2(nB)2)O(n2(nA)2nB) Table 9: Complexity of ϵ-constraint approach for extended MASPs on a single machine with p−batch The s-batch case is addressed by Mor and Mosheiov (2011) when set-up times depend on the set and the batches of jobs in JBmust be processed continuously, i.e. the batches of jobs in JAare partitioned into two sequences, scheduled prior to and after the batches of jobs in JB, respectively. They introduce an efficient O(n3 2) solution algorithm for the resulting problem 1|s-batch, pj= 1|ϵ(∑CA j/∑CB j). The problem 1|s-batch|ϵ(∑wB jCB j/max TA j, setup, ∑DA j) is analysed by Unal et al. (1997) with ϵ= (0,0,0). The objective is to minimize the total weighted completion times of jobs in JB, integrating them into the schedule of jobs in JAmaking any job in JAtardy and without incurring any setup times or changing the relative sequence of the jobs in JA. They show that the problem is NP-hard, and that the specific case where pj= 1 ∀j∈ J is solvable in polynomial time. This case turns to be strongly NP-hard if there are chain-like precedence constraints on the jobs in JA. Others Fan (2010) study the 1|V(1,∞), direct|ϵ(∑CA j/∑CB j) problem for a particular case where each set of jobs belongs to a customer situated at different locations. Jobs are processed and delivered to each customer by a uncapacitated vehicle. In this case, Cjis the completion time plus transportation time. V(1,∞), direct specifies that a single delivery vehicle can deliver any number of orders, and that only jobs going to the same customer can be delivered together in the same shipment. The authors prove that the problem is NP-hard, and develop a dynamic programming algorithm with complexity O(n8). In the case of unrelated machines, the only contributions are Elvikis et al. (2009) and Elvikis et al. (2010a) for the Qm|pj=p|ϵ(FA,max CB j) problem, which is used to solve the Parero counterpart. The complexity of this problem depends on the form of FA, and it is reduced from the complexity of the Pareto counterpart indicated in the following subsection. Regarding flowshops, there are very few contributions. Huynh-Tuong and Soukhal (2009a) show that the F3|J A(m17→ m2),JB(m27→ m3)|ϵ(max CB j/max CA j) problem is NP-hard. Huynh-Tuong and Soukhal (2009b) provide a pseudo-polynomial algorithm with running time O(nBϵβ), with β=∑j∈J B(p2j+p3j). Finally, Perez-Gonzalez et al. (2011) analyze the structure of solutions for the problem PFm|dj= d|ϵ(max CA j/max TB j) when ϵ= 0. As the problem is NP-hard by reduction from PF2||ϵ(max CA j/max CB j), Perez-Gonzalez and Framinan (2010b) develop some heuristics and a VNS method are proposed which are tested for this problem. 23 6.1.3 Pareto approach Preemption and/or release dates Cheng et al. (2007) present a polynomial algorithm to obtain the set of nondominated solutions for 1|prmp, I, precB|#(fA/max fB j) with fA∈ {∑Cj,∑Uj}, giving a bound of the running time. The algorithm is valid for the cases without precedence constraints. The problem 1|rj, prmp|#(∑CA j,∑wB jUB j) is shown to be NP-hard by Meiners and Torng (2007). However, they show that if pj= 1 is polynomially solvable. Regarding other settings, only Peha (1995) models the problem Pm|rj, pj= 1|#(∑wA jCA j,∑wB jUB j) from a practical application about real-time systems and integrated services networks. They develop an algorithm to solve this problem in O(n2) running time. Batch and/or set-up Tan et al. (2011) consider the 1|p-batch|#(max CA j,max CB j) problem where each job has a different size. This problem is shown to be NP-hard by reduction to the case with one set of jobs. They give the mathematical formulation of the problem, and provide an ACO to solve it. Moreover, an evaluation is carried out in order to compare ACO to a GA adapted from the one set problem. Yazdani Sabouni and Jolai (2010) provide one heuristic for each of the following problems: Problem 1|p-batch, IS, b ≤n|#(max CA j,max LB j) and equal size of the jobs, problem 1|p-batch, IS|#(max CA j,max LB j), and problem 1|p-batch, CS, b ≤n, pB j=p|#(max CA j,max LB j) and equal size of the jobs. They also show that the heuristic for the first problem turns to be optimal if pB j=p. Finally, Feng et al. (2011) study the problem 1|s-batch, IS|#(max CA j,max LB j), giving a polynomial time algorithm with O(nA+ (nB)4). Others The case of unrelated machines has been only studied in the context where pj=pwhen JAand JBhave only one job with nAand nBoperations respectively, Qm|pj=p|#(max FA j,max FB j), addressed by Elvikis and T’kindt (2012); Elvikis et al. (2010b). They develop an algorithm that enumerates all Pareto solutions of this problem in O((nA)2nB+nAnBlog nB) running time. The algorithms are further refined by Elvikis et al. (2009, 2010a) for Qm|pj=p|#(FA,max CB j), with FAany regular function. For this problem, they develop an algorithm to enumerate the set of Pareto solutions by solving iteratively the ϵ-constraint version of this problem with different ϵvalues. The algorithm has O(nlog m+nAψ) running time, with ψdepending on the time needed to assign jobs in JA. When FAtakes a regular sum form, the aforementioned generic algorithm reduces its running time to O(n4). Moreover, for ∑wA jCA j,∑TA jand ∑wA jTA jwith the due dates and weights agreeable, i.e. dj≤dj′⇒wj≥wj′, the running time is O(nlog m+ψ′), with ψ′the time to solve 1|pj= 1|∑FA j. Additionally, for ∑UA jand ∑wA jUA j, the running time is O(nlog m+nAlog nA). When FAtakes a regular max form, the nondominated solutions can be found in O(n3). Furthermore, for max CA j, there are only two strictly non-dominated solutions, and finally, for max LA jthey develop an O(nlog m+nAlog nA) running time algorithm. Finally, Peha (1995) consider the problem Pm|pj= 1|#(∑wA jCA j,∑wB jUB j) where the complexity of the algorithm is O(nlog n). 24 6.1.4 Other problems Some references found in the literature consider MASPs with different objective functions and do not correspond to the previous subsections. Some of them are applied problems. Agnetis et al. (2007a) consider a constraint specific of MASPs, where a coordination protocol is defined by an arbitrator. Each set of jobs belongs to an agent, who submits the jobs one by one to the arbitrator on each step. Between those jobs provided for each agent, the arbitrator selects one according to a priority rule, and schedules it at the end of the current schedule (initially empty). In this problem, the objective is to determine the order to provide the jobs for each agent to the arbitrator, since the priority rule is public information, whereas jobs characteristics are private information of the respective agent. Some rules encountered in the literature include priority rules (such as the well-known SPT,WSPT,EDD); Round-Robin rule (denoted as RR), where jobs are alternated from each set; or k-R, where at most kconsecutive jobs of the same set are selected according to rule R. Considering the single machine problem, Agnetis et al. (2007a) prove that 1|RR|Fl(∑CA j,∑CB j), 1|RR|#(∑CA j,∑CB j), 1|k-R|Fl(∑CA j,∑CB j) and 1|k-R|#(∑CA j,∑CB j) are solvable using the SPT rule. Although 1|WSPT|#(∑wA jCA j,∑wB jCB j) is optimally solvable by WSPT rule, for the LCC case the weights must be the same. Finally, they also prove that, for the problem 1|EDD|Fl(∑UA j,∑UB j), the coordination rule (for example EDD) turns out to be ineffective. In the previous sections we have mentioned some problems considering the goal programming approach used to solve problems of different approaches. However, there are some references explicitly addressing a goal programming objective. For example, 1|p−batch, IS|GP (max LA j,max FB j) is solved by Li and Yuan (2011) by an algorithm developed previously to solve 1|p−batch, IS|ϵ(max FA j/max FB j), and which can be easily applied to this problem. The running time of this algorithm is O(nnAnBlog(αU−αL)) where αU= maxj∈J A{FA j(P)}with P=∑m i=1 ∑j∈J pij, and αL= minj∈J A{FA j(0)}. Moreover, Cheng et al. (2008) shows that 1|prec|GP(max F1 j,...,max FK j) is solvable in O(n2), and the running time is O(n∗log n∗+n2), depending on the number of forbidden intervals, n∗, if we consider the case with preemption. The same problem is polynomially solvable in O(n∗log n∗+nlog n) without the precedence constraint. Finally, Cheng et al. (2006) shows that 1|prmp|GP(∑U1 j, . . . , ∑UK j) is equivalent to the basic case, and this problem with forbidden intervals is reducible in linear time to the equivalent basic problem, with modified due dates. The rest of the references are applied problems. First, Peha and Tobagi (1990) consider a MASP applied to traffic in telecommunications (file transfer or interprocess communication) on a single packet-switched network. They consider two sets of jobs formed by packets, JAand JB, and a lexicographical approach where the objective functions are ∑wA jUA j ∑j∈J AwA j and max wB jLB j ∑j∈J BwB j . They present an algorithm with O(n2) for the weighted and the unweighted cases. Arbib et al. (2004) consider two problems with two disjoint sets of jobs JAand JB: in the first problem the objective is to maximize the minimum between ∑FA jand ∑FB j. The second one is an ϵ-constraint approach where the objective is to maximize ∑FA jsubject to ∑FB j≥ϵ. Problems are solved by pseudopolynomially dynamic programming algorithm. Finally, some authors consider the problem where jobs (in JA) and maintenance tasks (in JB), are 25 Mu, Y. and Guo, X. (2009b). On-line rescheduling to minimize makespan under a limit on the maximum disruptions. In 2009 International Conference on Management of e-Commerce and e-Government, ICMeCG 2009, pages 141–144. Mu, Y. and Hao, Y. (2010). Rescheduling to minimize the total completion time under a limit on the total completion time of the original jobs. In Proceedings - 2010 3rd IEEE International Conference on Computer Science and Information Technology, ICCSIT 2010, volume 4, pages 307–311. Ng, C. T., Cheng, T. C. E., and Yuan, J. J. (2006). A note on the complexity of the problem of two-agent scheduling on a single machine. Journal of Combinatorial Optimization, 12(4):386–393. Nong, Q. Q., Cheng, T. C. E., and Ng, C. T. (2011). Two-agent scheduling to minimize the total cost. European Journal of Operational Research, 215(1):39–44. Peha, J. M. (1995). Heterogeneous-criteria scheduling: Minimizing weighted number of tardy jobs and weighted completion time. Computers and Operations Research, 22(10):1089–1100. Peha, J. M. and Tobagi, F. A. (1990). Evaluating scheduling algorithms for traffic with heterogeneous performance objectives. Global Telecommunications Conference, 1990, and Exhibition.’Communications: Connecting the Future’, GLOBECOM ’90., IEEE, pages 21–27. Perez-Gonzalez, P. and Framinan, J. M. (2009). Scheduling permutation flowshops with initial availability constraint: Analysis of solutions and constructive heuristics. Computers & Operations Research, 36(10):2866–2876. Perez-Gonzalez, P. and Framinan, J. M. (2010a). Finite-capacity due date setting in permutation flowshops: Analysis of solutions and simple heuristics. International Workshop on Project Management and Scheduling, PMS. Tours - Loire Valley, France, pages 319–322. Perez-Gonzalez, P. and Framinan, J. M. (2010b). Setting a common due date in a constrained flowshop: A variable neighbourhood search approach. Computers & Operations Research, 37(10):1740–1748. Perez-Gonzalez, P., Framinan, J. M., and Molina Pariente, J. M. (2011). Due date setting in permutation flowshop with arrival of new jobs. International Conference on Industrial Engineering and Systems Management, IESM. Metz, France. Pinedo, M. (1995). Scheduling: Theory, algorithms, and systems. Prentice Hall International Series in Industrial and System Engineering. Prentice Hall, Englewood Cliffs, New Jersey (USA). Ruiz, R., Carlos Garcia-Diaz, J., and Maroto, C. (2007). Considering scheduling and preventive maintenance in the flowshop sequencing problem. Computers & Operations Research, 34(11):3314–3330. Sadi, F., Soukhal, A., and Billaut, J. C. (2012). Parallel machines multi-agent scheduling problems with a global objective function. International Conference on Project Management and Scheduling, PMS. Leuven, Belgium, pages 274–277. Saule, E. and Trystram, D. (2009). Multi-users scheduling in parallel systems. IPDPS 2009 - Proceedings of the 2009 IEEE International Parallel and Distributed Processing Symposium. Shen, L. (1998). Logistics with competing users. PhD thesis, University of Arizona, United States – Arizona. Shen, W., Hao, Q., Yoon, H. J., and Norrie, D. H. (2006). Applications of agent-based systems in intelligent manufacturing: An updated review. Advanced Engineering Informatics, 20(4):415–431. Soltani, R., Jolai, F., and Zandieh, M. (2010). Two robust meta-heuristics for scheduling multiple job classes on a single machine with multiple criteria. Expert Systems with Applications, 37(8):5951–5959. Tan, Q., Chen, H. P., Du, B., and Li, X. L. (2011). Two-agent scheduling on a single batch processing machine with non-identical job sizes. 2nd International Conference on Artificial Intelligence, Management Science and Electronic Commerce, AIMSEC 2011, pages 7431–7435. T’kindt, V. and Billaut, J. C. (2001). Multicriteria scheduling problems: a survey. Operations Research, 35(2):143–163. T’kindt, V. and Billaut, J. C. (2002). Multicriteria scheduling: Theory, models and algorithms. Springer, Berlin (Germany), second edition. Unal, A. T., Uzsoy, R., and Kiran, A. S. (1997). Rescheduling on a single machine with part-type dependent setup times and deadlines. Annals of Operations Research, 70:93–113. Wan, G., Vakati, S. R., Leung, J. Y. T., and Pinedo, M. L. (2010). Scheduling two agents with controllable processing times. European Journal of Operational Research, 205(3):528–539. 32 Warburton, A. (1987). Approximation of pareto optima in multiple-objective, shortest-path problems. Operations Research, 35(1):70. Wu, C. C., Huang, S. K., and Lee, W. C. (2011a). Two-agent scheduling with learning consideration. Computers and Industrial Engineering, 61(4):1324–1335. Wu, W. H., Cheng, S. R., Wu, C. C., and Yin, Y. (2011b). Ant colony algorithms for a two-agent scheduling with sum-of processing times-based learning and deteriorating considerations. Journal of Intelligent Manufacturing, In press. Yang, B. (2007). Single machine rescheduling with new jobs arrivals and processing time compression. The International Journal of Advanced Manufacturing Technology, 34(3-4):378–384. Yazdani Sabouni, M. T. and Jolai, F. (2010). Optimal methods for batch processing problem with makespan and maximum lateness objectives. Applied Mathematical Modelling, 34(2):314–324. Yin, Y., Cheng, S. R., and Wu, C. C. (2012a). Scheduling problems with two agents and a linear non-increasing deterioration to minimize earliness penalties. Information Sciences, 189:282–292. Yin, Y., Wu, W. H., Cheng, S. R., and Wu, C. C. (2012b). An investigation on a two-agent single-machine scheduling problem with unequal release dates. Computers and Operations Research, In press. Yuan, J. and Mu, Y. (2007). Rescheduling with release dates to minimize makespan under a limit on the maximum sequence disruption. European Journal of Operational Research, 182(2):936–944. Yuan, J., Mu, Y., Lu, L., and Li, W. (2007). Rescheduling with release dates to minimize total sequence disruption under a limit on the makespan. Asia - Pacific Journal of Operational Research, 24(6):789–796. Yuan, J. J., Shang, W. P., and Feng, Q. (2005). A note on the scheduling with two families of jobs. Journal of Scheduling, 8(6):537–542. Zhao, C. and Tang, H. (2010). Rescheduling problems with deteriorating jobs under disruptions. Applied Mathematical Modelling, 34(1):238–243. 33