1.Introduction

In this paper, we consider a scheduling problem in which two agents compete to use a common single machine, and each agent has different performance objectives when processing a set of jobs. The processing order of one job belonging to one agent can affect the objective function of the other agent. Therefore, we need to find a schedule that optimizes two objective functions at the same time by considering the impact of scheduled jobs on the objective functions of two agents.

This scenario is called a two-agent scheduling problem, and requires special attention. If we handle this problem as a simple bi-criteria, single-agent optimization problem, we could use one of two general approaches : (i) represent the objective function as the weighted sum of two objective functions, or (ii) consider two objective functions one-by-one, using the first result as a new constraint for the second. However, neither of these methods can guarantee the optimality of the obtained solution, as the two objective functions might have different measurement units, and all jobs contribute to all criteria [2]. Therefore, two-agent scheduling problems are different from those commonly referred to as bi-criteria scheduling problems. The complexity of two-agent scheduling problems is higher than that of bi-criteria scheduling problems, and we need to devise more efficient and systematic approaches.

Two-agent scheduling problems occur in various industrial environments where two agents interact to perform their respective tasks using a common processing resource. For example, let us consider a project scheduling problem in a firm. As explained in [15], over time, multiple projects within a factory might compete to use shared common renewable resources, such as people and machinery. Each project manager is responsible for achieving good performance on his or her project, and so the use of these resources must be negotiated with other project managers. Another example can be found when tasks in a mechanical workshop require rescheduling [26]. If the main objective is to minimize the total flow time, some jobs that have not been done on one day become urgent the next. Two groups of jobs can then be assigned to two agents with different objective functions.

In recent decades, there have been a number of studies on this issue. First, the concept of two-agent scheduling problems was introduced by [4], which analyzed the computational complexity of combining two criteria into a single objective function. Then, Agnetis et al. [1] addressed the twoagent scheduling problem by considering the makespan, lateness, sum of completion times, and sum of weighted completion times, and analyzed the problem complexity while suggesting some solution algorithms. Ng et al. [25] considered the case whereby one agent minimizes the sum of completion times, while restricting the number of tardy jobs within a bound for the other agent, and showed that this problem is NP-hard under the condition of high multiplicity. Cheng et al. [9] extended the work of Agnetis et al. [1] to multiagent scheduling problems. Readers who are interested in this topic are referred to [11, 18, 32], and the references therein.

The above studies did not consider cases in which the job processing time depends on the position (or start time) of a job within the overall sequence. We call this the position- dependent processing time. In the literature, this processing time is categorized as having a learning effect or an aging effect. With a learning effect, the actual processing time of a job decreases according to its position in the sequence. For example, repeated processing of similar tasks improves workers’ skills, increasing the speed of machine operation. With an aging effect, the actual processing time of a job increases with its position in the sequence. As a practical example, we can consider the continuous casting and rolling processes in a steel plant, where the hot and cold charge process can be regarded as two agents - the processing time of the charges will increase with time due to the drop in temperature [20].

Recently, scheduling problems with position-dependent processing times have received considerable attention in the literature. Specifically, Biskup [5] introduced the concept of the learning effect into scheduling problems for a single agent. Mosheiov [24] mentioned the aging effect, and showed that a V-shaped schedule is optimal for the single-machine flowtime minimization problem [23]. Biskup [6] provided an extensive survey on scheduling problems with learning effects, and Kuo and Yang [16] considered a single-machine scheduling problem with a cyclic aging effect. Chang et al. [7] studied the learning/aging effect scheduling problem on a single machine with a common due date. For more recent results, see [30, 27, 33].

To the best of our knowledge, few studies on scheduling problems have simultaneously considered two-agent and position (or start time)-dependent processing times. These studies can be categorized by the functional representation method they use to compute the actual processing times : (i) linear function-based approaches (e.g., [20, 21, 17, 31]), and (ii) exponential function-based approaches (e.g., [10, 19, 29]). The above studies considered different combinations of objective functions, such as the (weighted) sum of completion times, (weighted) sum of tardiness, or lateness for one agent, under a constraint on the number of tardy jobs or the upper bound of the makespan for the other agent.

However, they did not consider cases in which each processed job has different learning or aging ratios. This means that the actual processing time for a job can be determined not only by the processing sequence, but also by the learning/ aging ratio, which can reflect the degree of processing difficulties in subsequent jobs. This modeling concept for the processing time was first suggested by Cheng and Wang [8]. Later, Bachman and Janiak [3] analyzed a simpler learning effect formulation for a single-machine case, and Wang and Xia [28] applied the concept to multiple-machine flowshop scheduling with an increasing series of dominating machines. These are plausible scenarios in real-life scheduling environments, and hence they deserve to be applied to the case of two-agent single-machine scheduling.

Thus, in this paper, we consider a two-agent single-machine scheduling problem with linear job-dependent position- based learning effects, where each job has a different learning ratio. Specifically, we take into account two objective functions such that one agent wants to minimize the total weighted completion time and the other agent wishes to restrict the makespan to within some upper bound. We formally define the problem by developing a mathematical formulation, and devise a branch-and-bound (B&B) algorithm to give optimal solutions. As this problem is at least binary NP-hard, we suggest efficient genetic algorithms (GAs) using different methods to generate the initial population and two crossover operations to find near-optimal solutions, and verify their performance by means of a numerical experiment.

The rest of this paper is organized as follows. In Section 2, we formally define the two-agent single-machine scheduling problem with linear job-dependent position-based learning effects by developing an appropriate mixed integer programming (MIP) model and design a B&B algorithm to find optimal solutions. In Section 3, we develop efficient GAs that give near-optimal solutions and verify the performance of these algorithms using a numerical experiment in Section 4. Finally we give our conclusions and suggestions for future work in Section 5.

2.Problem Definition and a Branchand Bound Algorithm

2.1.Problem Definition

The scheduling problem considered can be described as follows : Consider two agents A and B , each with a set of non-preemptive n_X jobs J^X = {J₁^X, J₂^X, ⋯J_nX^X}, where J_i^X represents the ith job of agent X , for X∈{A, B }. Any of these jobs can be processed at the beginning of the operation, and each of them is processed by a single common machine. Therefore, the two agents compete to use the machine while optimizing their own objective functions, which are dependent on the completion times of all jobs. Specifically, we assume that agent A is aiming to minimize the sum of the weighted completion times of all jobs in J^A , represented by ∑ i = 1 n A w i A C i A , , and that agent B must ensure that the makespan C_max^B is less than a given upper bound U , where w_i^A and C_i^A are the weight and the completion time of job J_i^A , respectively, for i = 1, 2, ⋯, n_A

Based on this problem description, we consider a special model for processing times that are position-dependent linear functions with job-dependent learning effects. Thus, for agent X∈{A, B }, the actual processing time of job J_i^X processed in rth position in a sequence, represented by p_i^X(r) , has a learning effect of p_i^X(r) = p_i^X - rb_i^X , where p_i^X is the normal processing time of job J_i^X and b_i^X > 0 is the constant learning ratio of job J_i^X, for i ∈ I^X = {1, 2, ⋯, n_X} and r∈I = {1, 2, ⋯, n} ( n =n_A + n_B ). Different schedules may therefore give different values ∑ i = 1 n A w i A C i A , and C_max^B for the two agents. Specifically, for a schedule S , we represent these as ∑ i = 1 n A w i A C i A , (S) and C_max^B (S), where C_max^B (S) can be computed as C max B S = max k ∈ I B C k B using C_k^B(S) to represent the completion time of J_k^B, k∈I^B . Furthermore, because all processing times are positive, we assume that

b i X < p i X n , ∀ J i X , i ∈ I X , X ∈ A , B .

Using the three-field notation Ψ₁|Ψ₂|Ψ₃, suggested by [12], we can denote the scheduling problem as

where the first component Ψ₁ is the number of machines, Ψ₂ describes the job characteristics, and Ψ₃ contains the objective functions. Therefore, Eq. 1 represents the two-agent single-machine scheduling problem with linear job-dependent position-based learning effects.

Furthermore, by defining

J j = J j A , if 1 ≤ j ≤ n A J j − n A B , if n A + 1 ≤ j ≤ n A + n B ,

we can develop the following MIP model for the problem under consideration :

s.t.

where x_jr is defined as x_jr = 1 if job J_j is assigned to the rth position and x_jr = 0, otherwise. C_j is the completion time of job J_j, p_j is the processing time of job J_j, and C_|r| is the completion time of the job in position r. Eq. 2 therefore represents the total weighted completion time of agent A , which is the objective function of this agent, and Eq. 3 denotes the position-dependent processing time of job J_j under consideration of learning effects. Eq. 4 computes the completion time of the rth job, and the completion time of job J_j can be obtained by using this in Eq. 5. Eq. 6 is the upper-bound makespan condition for agent B . Eqs. 7 and 8 are job assignment conditions: each job must be assigned to only one position, and each position can have only one job. Eqs. 9 and 10 are non-negativity conditions for variables C_j and C_|r|, and Eq. 11 is the binary condition for variable x_jr .

Agnetis et al. [1] showed that a two-agent single-machine scheduling problem 1 ∑ i = 1 n A w i A C i A : f max B is binary NP-hard, even without job learning or aging effects. Therefore, our problem is at least binary NP-hard, necessitating the development of an efficient solution procedure to find a (near-) optimal solution.

2.2.Properties for Dominance and Feasibility

First, we develop four dominance properties based on a pairwise interchange comparison. Suppose that there are two sequences s₁ = (π₁, J_i^X, J_j^X, π₂) and s₂ = (π₁, J_j^X, J_i^X, π₂), where π₁ and π₂ represent the scheduled and unscheduled parts, respectively. In S₁, two jobs J_i^X and J_j^X are in the rth and (r + 1) th positions, respectively, whereas S₂ is obtained by interchanging J_i^X and J_j^X in S₁. Then, by defining t as the completion time of sequence π₁, we have the following properties.

Property 1

If two jobs J_i^X , J_j^X ∈J^A satisfy (i) b_i^A < b_j^A and (ii) w_j^A/w_i^A ≤ (p_j^A(r) - b_i^A)/(p_i^A(r) - b_j^A), then S₁ dominates S₂.

Proof : From the definition, we can compute the completion times of J_i^A and J_jA for schedules S₁ and S₂ as follows.

C i A S 1 = t + p i A − rb i A C j A S 1 = t + p i A − rb i A + p j A − r + 1 b j A C j A S 2 = t + p j A − rb j A C i A S 2 = t + p j A − rb j A + p i A − r + 1 b i A .

From b_i^A < b_j^A , we have C_j^A(S₁) < C_i^A(S₂). Since w_j^A/w_i^A ≤ (p_j^A(r) - b_i^A)/(p_i^A(r) - b_j^A), we have w_i^AC_i^A(S₁) + w_j^AC_j^A(S₁ ) ≤ w_j^AC_j^A(S₂) + w_i^AC_i^A(S₂). Therefore, S₁ can have a smaller total weighted completion time for agent A and a faster makespan for agent B than S₂. This means that S₁ dominates S₂. ■

Three further properties can be proved in a similar manner to Property 1.

Property 2

Given two jobs J_i^X, J_j^X∈J^B , if (i) b_i^B < b_j^B and (ii) t + (p_i^B - rb_i^B) + (p_j^B - (r + 1)b_j^B) ≤ U, then S₁ dominates S₂.

Property 3

Given two jobs J_i^X∈J^A, J_j^X∈J^B , if (i) b_i^A < b_j^B (ii) p_j^B(r) - b_i^A ≥ 0 and (iii) t + (p_i^A - rb_i^A)+ (p_j^B - (r + 1)b_j^B)≤ U , then S₁ dominates S₂.

Property 4

Given two jobs J_i^X∈J^B , J_j^X∈J^A , if (i) b_i^B < b_j^A (ii) p_i^B(r) - b_j^A ≥ 0 and (iii) t + (p_i^B - rb_i^B )≤ U , then S₁ dominates S₂.

Additionally, we can state the following four properties regarding the feasibility of a sequence. Suppose that we have a sequence of jobs (π, π^c), where the scheduled part π consists of m jobs and the unscheduled part π^c consists of (n - m) jobs. Furthermore, let p ˜ m + r be the minimum actual processing time of jobs that can be scheduled in the rth position in π^c, which is position (m + r) in the whole sequence.

Property 5

Given a job J_i^X∈J^B∩π scheduled in the mth position with C_[m] > U , then (π, π^c) is infeasible.

Proof : Since job J_i^X∈J^B∩π in the mth position has C_[m] > U , it violates the condition for agent B ■.

Property 6

Given a job J_i^X∈J^A∩π scheduled in the mth position with C_[m] > U and a job J_j^X∈J^B∩π^c, then (π, π^c) cannot generate any feasible sequence.

Proof : Since job J_i^X∈J^A∩π and C_[m] > U , the completion time of any job J_j^X∈J^B∩π^c must be greater than U . Therefore, any sequence generated from (π, π^c) is not feasible. ■

Property 7

Given a job J_i^X∈J^B∩π^c, C_[m] ≤ U , and C_[m] + p ˜ m + 1 > U , then (π, π^c) cannot generate any feasible sequence.

Proof : By the definition of p ˜ m + 1 (m + 1), we have p_i^B(v) > p ˜ m + 1 (m + 1)for any job J_i^X∈J^B∩π^c and any position v in π^c. Therefore, we have C_i^B > U for any job J_i^X∈J^B∩π^c, making any schedule generated from (π, π^c) infeasible. ■

Property 8

If all jobs in π^c belong to agent B , then sequence (π, π^c) should be (ππ , π ˜whereπ is the sequence obtained by scheduling jobs in π^c in non-decreasing order of b_j^B

Proof : Since all jobs in π^c belong to agent B , we have a scheduling problem with (n - m) jobs for agent B , represented by

According to Bachman and Janiak [3], this problem can be optimized by scheduling jobs in non-decreasing order of b_j^B . ■

2.3.Branch-and-Bound Algorithm

Using the properties stated above, we now develop an efficient B&B algorithm. The algorithm attempts to assign jobs in a forward manner, i.e., iteratively from the first position. The basic idea is to branch a node into several nodes, each corresponding to the scheduling of one job among all possible jobs, and to bound each of them by computing the potential minimum value (i.e., lower bound) of the total weighted completion time of agent A for the schedule under consideration [14]. For each node, we perform the following process.

At each iteration of the algorithm, suppose that we have a sequence of jobs S = (π, π^c), where the unscheduled part π^c comprises n₁ jobs for agent A and n₂ jobs for agent B . Then, we have

where p[m + 1] is the actual processing time of the (m + 1) th job. Therefore, we can use Eq. 13 as the estimator of C [m + l], represented by

C ˆ m + l = C m + ∑ r = 1 l p ˜ m + r .

We can also sort the weights of the unscheduled n₁ jobs into non-increasing order, as w^A₍₁₎ ≥ w^A₍₂₎ ≥ ⋯ ≥ w^A_(n1). Then, the lower bound of ∑ i = 1 n A w i A C i A S can be computed as follows.

(Lemma 1)

For schedule S with (π, π^c), the lower bound of ∑ i = 1 n A w i A C i A S at the current iteration is

where w^A_[r] and C^A_[r] represent the weight and completion time of the job scheduled in rth position among all (n_A - n₁) jobs for agent A in π, respectively. Furthermore, C^A_(r) denotes the minimum completion time of a job scheduled in rth position among all n₁ jobs for agent A in π^c

Proof : The first term in Eq. 14 computes the total weighted completion time of (n_A - n₁) scheduled jobs for agent A in π. According to [13], ∑ i = 1 n a i b ia_ib_i is minimized if the two sequences of numbers a_i and b_i are monotonic in the opposite sense. Based on this, the minimum value of the total weighted completion time that can be achieved using the unscheduled n₁ jobs for agent A in π^c is ∑ r = 1 n 1 w r A C r A ,w^A_(r)C^A_(r) , which gives the second term in Eq. 14, resulting in a lower bound LB for S . ■

Specifically, we can compute C^A_r by assigning the estimated completion times C ˆ m + l l = 1 , 2 , ..., n 1 + n 2 to the remaining (n₁ + n₂) jobs for agents A and B as follows :

Since the lower bound gives the minimum value of the total weighted completion time for agent A that can be achieved after finishing the allocation procedure, it can be used to speed up the search procedure in the B&B algorithm by fathoming any non-prominent nodes. We apply a depth-first search to the B&B algorithm, the overall procedure of which can be described as follows.

3.An Efficient GA

It is well known that B&B algorithms require considerable computational time to find optimal solutions to large-sized or computationally difficult problems. Therefore, we develop a GA Mitchell [22], a well-known meta-heuristic approach that can find near-optimal solutions efficiently. The components of the suggested GA are as follows.

∙Design of a chromosome : First, we design a chromosome P as an n-dimensional array representing a sequence of n jobs for two agents. Each gene represents the job number, and its position in the chromosome corresponds to the order of the jobs in a schedule. Then, we can make the following statement on the validity of the suggested structure for a chromosome.

Property 9

Feasibility condition for a chromosome A chromosome is valid and feasible as a sequence for the scheduling problem under consideration if all jobs represented by genes satisfy the following two conditions : (i) job numbers are not duplicated, and (ii) the makespan for agent B satisfies the upper-bound condition.

∙Initialization of a population : We consider three methods of generating a chromosome to initialize a population :

We make Q chromosomes for the initial population, where Q is an even number. During the GA procedure, we allow a modest number of duplications, and set Q = 30 × n to increase the diversity of the chromosomes.

Moreover, we apply a mutation operation to each chromosome by swapping two randomly selected genes. This operation is useful in escaping from local optima, and is applied probabilistically according to some pre-specified rate rm (0 < rm < 1). If the resulting chromosome is not feasible under Property 9, we repeat the procedure.

4.Numerical Experiments

4.1.Experimental Design

To verify the performance of the GA described in the previous section, we designed a numerical experiment. First, we considered different scheduling problems by changing the number of jobs for each agent. Specifically, we considered n = 10, 12, 14, 16, assuming that each agent has the same number of jobs. The value of U for agent B was generated using the convex combination of the minimum value of the makespan and the minimum value of the maximum makespan, represented by V₁ and V₂, respectively. The value of V₁ can be obtained by solving the single-agent scheduling problem in Eq. 12. V₂ can be computed by the following lemma.

Lemma 2

Let C^B_max,Jk^BB denote the makespan of a schedule S with J_k^B in the last position. Then, we have

max C max , J k B B = ∑ i = 1 n A p i A + ∑ j = 1 n B p j B j ≠ k − min ∑ i = 1 n ∑ r = 1 n − 1 rb i x ir i ≠ n A + k + p k B − nb k B ,

and V 2 = min k ∈ I B max C max , J k B B ,

where b_i = b_i^A, if 1 ≤ i ≤ n_A and b_i = b_{i - nA} , if n_A +1 ≤ i ≤ n_A + n_B

Proof : For any schedule S ′ obtained from schedule S by removing J_k^B , we have

max C max , J k B B = max S ′ C max S ′ + p k B n = max ∑ i = 1 n A p i A + ∑ j = 1 n B p j B j ≠ k − ∑ i = 1 n ∑ r = 1 n − 1 rb i x ir i ≠ n A + k + p k B − nb k B = ∑ i = 1 n A p i A + ∑ j = 1 n B p j B j ≠ k − min ∑ i = 1 n p j B i ≠ n A + k ∑ r = 1 n − 1 rb i x ir + p k B − nb k B

where C_max (S ′) is the makespan of the remaining (n - 1) jobs using schedule S ′. Furthermore, we can compute ∑ i = 1 n i ≠ n A + k ∑ r = 1 n − 1 rb i x ir by arranging the remaining jobs in nonincreasing order of b_i^A and b_j^B . ■

Now, we can obtain different values of U by defining

where we consider the three different values of α = 0.25, 0.5 and 0.75. Therefore, we have 12 system configurations defined by different pairs of (n, α) . For each configuration, we produced 50 problem instances by randomly generating normal processing times in the range 1-100, learning effects in the range 1-100, and job weights in the range 1-100. Accordingly, we considered 4×3×50 = 600 problem instances.

Moreover, we considered three methods of generating the initial population and two different reproduction operations. Hence, we have 3×2 = 6 different GAs, represented by GA (IP_k,CO_t ) (k = 1, 2, 3, t = 1, 2). We determined the parameter values of these GAs by pretesting some randomly generated problem instances. As a result, we set r_c = 0.8, rm = 0.1, and applied the stopping condition if the GA went 30 iterations without any improvement. Each instance of the scheduling problem was solved using the B&B algorithm and the six GAs.

The performance of the GAs was evaluated in terms of the percentage error, which is defined as

% error = TWCT by GA − Optimal TWCT Optimal TWCT × 100

where TWCT is the total weighted completion time. Furthermore, we measured the number of generated nodes and CPU time using the B&B algorithm. The CPU time of the B&B algorithm was compared to that required by the GAs. To compare the six GAs, we defined the relative deviation percentage (RDP) as

Our numerical experiments considered the solutions to 600 problem instances. For each system configuration and solution method, we calculated the mean, standard deviation (stdev), maximum number of generated nodes (for the B&B), CPU time (in seconds), and % error. <Table 1> shows the experimental results. B&B could solve instances with up to 14 jobs with a reasonable CPU time. Even when n = 16, it solved instances generated using α = 0.25 efficiently. For a fixed value of n, B&B took more time to obtain the optimal solution as the value of was increased. This is because, from Eq. 15, small values of α increase the value of U , since V₁ ≤ V₂. Similarly, larger values of α make U smaller, giving a tight upper bound U for agent B , and making it difficult to find an optimal solution using B&B.

Overall, the GAs exhibited good performance in the sense that they gave small % errors, with a mean of less than 1% in almost every configuration. Even for the largest configuration (n, α)= (16, 0.75) , the maximum % error (using IP₂ was less than 5%. In terms of computation time, the 3~9 s CPU time of the GAs is favorable over that of B&B in environments where the scheduling problem has tight time constraints.

A comparative analysis of the performance of each GA was conducted by computing the RDPs among the GAs by Eq. 16 and comparing the mean, standard deviation, and maximum values. The results are given in <Table 2>. In terms of the initial population, the method of random generation gave better RDP values, indicating that special methods for generating the initial population did not affect the quality of the final solution. The initial population only influenced the convergence of the GA when agent B had a tight upper bound U . <Figure 1> shows the average of the mean RDPs for GAs using three initial population methods and different combinations of (n, α), where GA(IP_k), k = 1, 2, 3, represents GAs using IP_k as the initial population method. Note that GAs using IP₃ had low average RDPs in eight of the twelve configurations. Even when this does not give the best result, the difference from the best is less than 0.5%. Comparing two GAs using IP₃, GA(IP₃, CO₂) is superior to GA(IP₃, CO₁) because it gave a low average RDP in more cases. Based on these observations, we claim that the GA using a random initial population and the two-point crossover operation, represented by GA(IP₃,CO₂), is superior to the other GAs.

The number of generated nodes and CPU time of B&B increased exponentially with the number of jobs n, whereas the CPU time of the GAs increased linearly within the range 0.5~5.5 s. For the largest configuration of (n, α)= (16, 0.75) , B&B took an average of 45,095.698 s (12.53h) to find an optimal solution, whereas the GAs took only 2~5 s, depending on the method of generating the initial population. More precisely, GAs using IP₁ and IP₂ for the initial population took about 2 s, while GAs using IP₃ (the random initial population) required around 5.4 s.

It would also appear that the CPU times were affected by the value of and the method of generating the initial population. For a fixed value of n, small values of α (i.e., 0.25 and 0.50) result in faster convergence for those GAs using IP₃. However, GAs using IP₃ with α = 0.75 were slower than others. Therefore, it seems that the exploration ability of GA is restricted by the tightness of U , and a specific method for generating the initial population allows the GA to converge faster than when the initial population is generated randomly. However, fast convergence does not necessarily mean that the solution is of good quality.

5.Conclusions

In this paper, we considered the two-agent single-machine scheduling problem with linear job-dependent position-based learning effects, where each job has a different learning ratio. The objective was to minimize the total weighted completion time for one agent, with the restriction that the makespan of the other agent cannot exceed a given upper bound. Since this problem is at least binary NP-hard, we suggested some efficient GAs using different methods for generating the initial population and crossover operations. A B&B algorithm incorporating several dominance properties and a lower bound was developed to find the optimal solution. The computational results indicate that the B&B algorithm could solve instances with up to 14 jobs in a reasonable amount of CPU time, and it was found that GA(IP₃,CO₂), which uses a random initial population and the two-point crossover operation, performed well in almost every configuration. Overall, from the perspective of computation time, the 3~9 s of CPU time required by the GAs will generally be preferable to the CPU time of the B&B approach in environments where the scheduling problem has tight time constraints.

In future research, we will extend the current method in three ways. First, we will consider other performance objectives for the two agents, such as minimizing tardiness, weighted tardiness, or the number of tardy jobs. These are practical issues in industry, although they can make the problem more difficult. Second, we will use other learning effects so that the actual processing time is dependent on the sum of processing times of preceding jobs. This learning effect is nonlinear, making it more difficult to find optimal solutions to the two-agent scheduling problem. Finally, extensions to the multi-agent or multi-machine environments are another interesting topic for consideration.