Citation: Roberta Bianchini, Chiara Saffirio. Fluid instabilities, waves and non-equilibrium dynamics of interacting particles: a short overview[J]. Mathematics in Engineering, 2023, 5(2): 1-5. doi: 10.3934/mine.2023033
[1] | Zhimeng Liu, Shuguang Li, Muhammad Ijaz Khan, Shaimaa A. M. Abdelmohsen, Sayed M. Eldin . Bicriteria multi-machine scheduling with equal processing times subject to release dates. Networks and Heterogeneous Media, 2023, 18(3): 1378-1392. doi: 10.3934/nhm.2023060 |
[2] | Yipeng Chen, Yicheng Liu, Xiao Wang . The critical delay of the consensus for a class of multi-agent system involving task strategies. Networks and Heterogeneous Media, 2023, 18(2): 513-531. doi: 10.3934/nhm.2023021 |
[3] | Urszula Ledzewicz, Heinz Schättler, Shuo Wang . On the role of tumor heterogeneity for optimal cancer chemotherapy. Networks and Heterogeneous Media, 2019, 14(1): 131-147. doi: 10.3934/nhm.2019007 |
[4] | Catherine Choquet, Ali Sili . Homogenization of a model of displacement with unbounded viscosity. Networks and Heterogeneous Media, 2009, 4(4): 649-666. doi: 10.3934/nhm.2009.4.649 |
[5] | Dieter Armbruster, Christian Ringhofer, Andrea Thatcher . A kinetic model for an agent based market simulation. Networks and Heterogeneous Media, 2015, 10(3): 527-542. doi: 10.3934/nhm.2015.10.527 |
[6] | Ken-Ichi Nakamura, Toshiko Ogiwara . Periodically growing solutions in a class of strongly monotone semiflows. Networks and Heterogeneous Media, 2012, 7(4): 881-891. doi: 10.3934/nhm.2012.7.881 |
[7] | Carlo Brugna, Giuseppe Toscani . Boltzmann-type models for price formation in the presence of behavioral aspects. Networks and Heterogeneous Media, 2015, 10(3): 543-557. doi: 10.3934/nhm.2015.10.543 |
[8] | Yaru Xie, Genqi Xu . The exponential decay rate of generic tree of 1-d wave equations with boundary feedback controls. Networks and Heterogeneous Media, 2016, 11(3): 527-543. doi: 10.3934/nhm.2016008 |
[9] | Denis Mercier . Spectrum analysis of a serially connected Euler-Bernoulli beams problem. Networks and Heterogeneous Media, 2009, 4(4): 709-730. doi: 10.3934/nhm.2009.4.709 |
[10] | Antonin Chambolle, Gilles Thouroude . Homogenization of interfacial energies and construction of plane-like minimizers in periodic media through a cell problem. Networks and Heterogeneous Media, 2009, 4(1): 127-152. doi: 10.3934/nhm.2009.4.127 |
We study a problem of two-agent scheduling on an unbounded serial-batch machine. There are two agents A and B having nA and nB jobs respectively, where nA+nB=n. Each agent has his own objective function to optimize that depends on the completion times of his own jobs only. However, all the jobs share a common processing resource (e.g., the serial-batch machine). In this paper we assume that agent A expects the maximum completion time (makespan) of his jobs to be minimized, while agent B expects the maximum lateness (to be defined later) of his jobs to be minimized. Using the standard scheduling notation, see, for example, [1], this circumstance can be modeled as an objective vector (CAmax,LBmax). For the purpose of meeting the needs of two agents to the maximum extent, the decision-maker has to design some strategies to stimulate the agents to cooperate.
The jobs are processed on the machine in batches, and a fixed setup time s>0 is incurred before each batch is started. The serial-batch machine can process at most one job at a time and cannot process any job when a setup is being performed. The processing time of a batch is equal to the total processing time of the jobs in it. This is different from parallel-batch, where the jobs in the same batch are processed simultaneously and the processing time of a batch is equal to the largest processing time of the jobs in it [2,3]. An unbounded machine means that the batch capacity b (the maximum number of jobs in a batch) is unlimited, i.e., b≥n; Otherwise, it is bounded, i.e., b<n. Compatibility means that the jobs from different agents can be processed in a common batch; Otherwise, the jobs from different agents are incompatible. We analyze both the compatible and incompatible models under both the batch availability and item availability assumptions. Batch availability means that any job in a batch is not available until all the jobs in this batch are completed. Item availability means that a job in a batch becomes available immediately after it is completed processing. The completion time of a job is defined to be the moment when it is available.
Problem formulation
There are two agents A and B, and agent X has a set JX={JX1,JX2,…,JXnX} of jobs to be non-preemptively processed on an unbounded serial-batch machine, X∈{A,B}. The jobs in JX are called X-jobs. Assume that JA∩JB=∅. Let JA∪JB=J and nA+nB=n. Each job JXj has a processing time pXj. Each B-job JBj has a due date dBj.
A schedule can be specified by a sequence of batches B1,B2,…,Bx. A fixed setup time s>0 is incurred before each batch. Let p(Bi) and C(Bi) denote the processing time and completion time of Bi, respectively. Clearly, C(Bi)=i⋅s+∑iq=1p(Bq), i=1,2,…x. For the case of batch availability, all jobs in Bi are completed simultaneously at time C(Bi). In contrast, for the case of item availability, a job is completed immediately after it is completed processing.
A batch containing only X-jobs is an X-batch, X∈{A,B}. A mixed batch refers to a batch that contains both A-jobs and B-jobs.
Given a feasible schedule σ of the n jobs, let CXj(σ) denote the completion time of JXj in σ. Let LBj(σ)=CBj(σ)−dBj denote the lateness of job JBj. If there is no confusion, we simply use CXj and LBj to denote CXj(σ) and LBj(σ), respectively. Let CXmax=maxnXj=1{CXj} and Cmax=max{CAmax,CBmax} denote the makespan of X-jobs and the makespan of σ, respectively. Let LBmax=maxnBj=1{LBj} be the maximum lateness of B-jobs. Notice that the makespan and maximum lateness criteria are both regular, i.e., they are non-decreasing in the job completion times.
This paper studies the two-agent scheduling problem on an unbounded serial-batch machine to minimize the makespan CAmax of agent A and the maximum lateness LBmax of agent B simultaneously. Using the three-field notation introduced by Graham et al. [4] and extended by T'kindt and Billaut [5], the four variants of the problem under consideration are denoted by 1|s−batch,b≥n,co,batch−avail|(CAmax,LBmax), 1|s−batch,b≥n,inco,batch−avail|(CAmax,LBmax), 1|s−batch,b≥n,co,item−avail|(CAmax,LBmax) and 1|s−batch,b≥n,inco,item−avail|(CAmax,LBmax), where "co'' and "inco'' mean "compatibility'' and "incompatibility'', and "batch−avail'' and "item−avail'' denote the "batch availability'' and "item availability'', respectively.
Since we are dealing with two criteria CAmax and LBmax which are not non-conflicting, we focus on the calculation of Pareto optima for CAmax and LBmax. The approach is called Pareto optimization which is one of the most popular approaches in multi-criteria scheduling [5,6].
Let fA and gB denote the two objectives of agents A and B respectively to be minimized. A feasible schedule σ is Pareto optimal with respect to fA and gB if there is no feasible schedule σ′ such that fA(σ′)≤fA(σ) and gB(σ′)≤gB(σ) with at least one strict inequality. The objective vector (fA(σ),gB(σ)) is called a Pareto optimal point [5,6].
Literature review
The problem under consideration falls into the categories of batch scheduling [2,3,7] and multi-criteria optimization [5,6], which are hotspots in scheduling research. Multi-agent scheduling [1,8,9,10] is a research topic in multi-criteria optimization. Here, we only review the results closely related to our study.
Webster and Baker [11] proposed an O(n2)-time algorithm for 1|s−batch,b≥n,batch−avail|Lmax (single-criterion problem). Wagelmans and Gerodimos [12] improved the time complexity to O(nlogn). He et al. [13] presented an O(n2)-time algorithm for 1|s−batch,b≥n,batch−avail|(Cmax,Lmax) (Pareto optimization problem). Later, the result has been extended to an O(n5)-time algorithm for 1|s−batch,b≥n,batch−avail|(Cmax,fmax) (maximum lateness Lmax is replaced by maximum cost fmax) [14]. He et al. [15] obtained an O(n6)-time algorithm for 1|s−batch,b<n,batch−avail|(Cmax,Lmax) (bounded serial-batch). Geng et al. [16] presented O(n4)-time algorithms for 1|s−batch,b≥n,batch−avail|(Cmax,fmax) and 1|s−batch,b<n,batch−avail|(Cmax,fmax). Hence, problems 1|s−batch,b≥n,batch−avail|fmax and 1|s−batch,b<n,batch−avail|fmax can also be solved in O(n4) time.
There are many research results for two-agent scheduling on an incompatible serial-batch machine with batch availability. Kovalyov et al. [17] derived polynomial and pseudo-polynomial time algorithms for constrained optimization problems with various combinations of the objective functions. Constrained optimization means that minimizing the objective value of agent A, subject to the condition that the objective value of agent B is bounded by a given threshold value. Feng et al. [18] provided an O(nA+nB4)-time algorithm for 1|s−batch,b≥n,inco,batch−avail|(CAmax,LBmax). He et al. [19] presented an O(nA+nB5)-time algorithm for 1|s−batch,b≥n,inco,batch−avail|(CAmax,fBmax) and an O(nA+nB4lognB)-time algorithm for 1|s−batch,b<n,inco,batch−avail|(CAmax,LBmax). He and Lin [20] gave an improved algorithm for 1|s−batch,b≥n,inco,batch−avail|(CAmax,LBmax) that runs in O(nA+nB2lognB) time. He et al. [21] presented an O(nA+nB5)-time algorithm for 1|s−batch,b<n,inco,batch−avail|(CAmax,fBmax). He et al. [22] presented an O(nA3nB3n2)-time algorithm for 1|s−batch,b≥n,inco,batch−avail|(LAmax,LBmax).
To the best of our knowledge, very few results have been published for two-agent scheduling on a serial-batch machine with compatibility or item availability. For a compatible model, Li et al. [23] provided either polynomial or pseudo-polynomial time algorithms for some constrained optimization problems arising from different combinations of several regular criteria, including the maximum cost, the total completion time, and the (weighted) number of tardy jobs. He et al. [22] presented an O(nA+nB4lognB)-time algorithm for 1|s−batch,b≥n,co,batch−avail|(CAmax,LBmax), and an O(nAnBn3)-time algorithm for 1|s−batch,b≥n,co,batch−avail|(LAmax,LBmax). They also presented an O(nA+nB2)-time algorithm for 1|s−batch,b≥n,inco,item−avail|(CAmax,LBmax), and an O(nA2nB2n)-time algorithm for 1|s−batch,b≥n,inco,item−avail|(LAmax,LBmax).
Contribution and organization
The main result of this paper is an O(nA+nB2lognB)-time algorithm for 1|s−batch,b≥n,co,batch−avail|(CAmax,LBmax), improving the O(nA+nB4lognB)-time algorithm presented in [22]. A slight modification of the algorithm can solve 1|s−batch,b≥n,inco,batch−avail|(CAmax,LBmax) in O(nA+nB2lognB) time, which has the same time complexity as the algorithm in [20]. We also consider the item availability. For 1|s−batch,b≥n,co,item−avail|(CAmax,LBmax) and 1|s−batch,b≥n,inco,item−avail|(CAmax,LBmax), we present O(nA+nBlognB)-time algorithms. The algorithm for 1|s−batch,b≥n,inco,item−avail|(CAmax,LBmax) improves the O(nA+nB2)-time algorithm presented in [22].
The paper is organized as follows. In Section 2, we present an O(nA+nB2lognB)-time algorithm for 1|s−batch,b≥n,co,batch−avail|(CAmax,LBmax), and indicate the slight modification of the algorithm for the incompatible model. In Section 3, we present O(nA+nBlognB)-time algorithms for 1|s−batch,b≥n,co,item−avail|(CAmax,LBmax) and 1|s−batch,b≥n,inco,item−avail|(CAmax,LBmax). Some concluding remarks are drawn in Section 4.
In this section we will present an O(nA+nB2lognB)-time algorithm for 1|s−batch,b≥n,co,batch−avail|(CAmax,LBmax). At the end of this section, we will indicate the slight modification of the algorithm for the incompatible model.
We need the following lemma which describes the structure of the Pareto optimal schedules we are searching for.
Lemma 2.1. ([22]) For any Pareto optimal point of 1|s−batch,b≥n,co,batch−avail|(CAmax,LBmax), there is a corresponding Pareto optimal schedule so that all A-jobs belong to a common batch, and all B-jobs are scheduled in EDD (earliest due date first) order.
By this lemma, we re-index all B-jobs in EDD order so that dB1≤dB2≤⋯≤dBnB. The single batch containing all A-jobs may also contain B-jobs. For brevity, we will represent a schedule by a batch sequence B1,B2,…,BnB,BnB+1,…,B2nB+1, where BnB+1 is the batch containing all A-jobs and possibly some B-jobs. Some batches in B1,B2,…,BnB,BnB+1,…,B2nB+1 may be empty or dummy. An empty batch has processing time zero and setup time zero, while a dummy batch has processing time zero and setup time s.
Let us roughly illustrate the basic idea of the algorithm, conveniently showing the difference between the empty and dummy batches. There are many empty batches in the initial schedule. We iteratively adjust the schedule to decrease its LBmax-value. The adjustment is accomplished by moving some B-jobs (whose lateness values are not less than the currently fixed LBmax-value) to the left. Consequently, an empty batch may become nonempty and a setup time s incurs because some jobs are moved into it, and a nonempty batch may become a dummy batch because all its jobs have been moved out. Although the nonempty batch now contains no jobs, we retain it in the batch sequence with processing time zero and setup time s. The motivation for introducing the concept of "dummy batch'' is to ensure that any job cannot be moved to the right. It is worth pointing out that a dummy batch will never appear earlier than batch BnB+1.
Let Ω(J) denote the Pareto set which consists of all Pareto optimal points together with the corresponding schedules. The algorithm below for constructing Ω(J) will repeatedly apply the standard ε-constraint approach.
Lemma 2.2. ([6]) Let y be the optimal value of constraint optimization problem α|f≤ˆx|g, and let x be the optimal value of constraint optimization problem α|g≤y|f. Then the standard ε-constraint approach tells us that (x,y) is a Pareto optimal point for problem α||(f,g).
Let Π(J) denote the set of all feasible schedules for J=JA∪JB. Let Π(J,y)⊆Π(J) denote the set of the schedules whose LBmax-values are less than y, where y is a given threshold value.
Algorithm BATCHCO:
Step 1. Initially, set Ω(J)=∅, z=0. Set h=0, y(h)=+∞. Let σ(h)=(B(h)1,B(h)2,…,B(h)nB,B(h)nB+1,…,B(h)2nB+1) be the initial schedule, where B(h)nB+1 consists of all A-jobs, B(h)2nB+1 consists of all B-jobs, and all other batches are empty batches.
Step 2. The (h+1)-th iteration:
Set y(h+1)=LBmax(σ(h)). Invoke Procedure PBATCHCO(J,y(h+1)) to adjust σ(h) to construct σ(h+1) so that σ(h+1) has minimum CAmax among the schedules in Π(J,y(h+1)).
Step 3. If σ(h+1)=∅, then set π∗=σ(h). Let Ω(J)=Ω(J)∪{(CAmax(π∗),LBmax(π∗),π∗)} and return Ω(J). Otherwise, if CAmax(σ(h+1))>CAmax(σ(h)), then set z=z+1, πz=σ(h), and let Ω(J)=Ω(J)∪{(CAmax(πz),LBmax(πz),πz)}.
Step 4. Set h=h+1 and go to Step 2.
Procedure PBATCHCO(J,y(h+1)):
Step 1. Check the batches in σ(h) backwardly: For i=2nB+1,2nB,…,1, check the inequality LBj(C(B(h)i))<y(h+1) for each job JBj in B(h)i. Suppose that we find a job JBk∈B(h)i which violates the inequality LBk(C(B(h)i))<y(h+1). We distinguish two different cases:
Case 1. i≤nB+1.
If i=1, or i≤nB and JBk has the largest due date in B(h)i, then return σ(h+1)=∅. Otherwise, move all the B-jobs in B(h)i with their due dates no more than dBk into B(h)i−1. If B(h)i−1 is empty before these jobs are inserted, then introduce a new setup time s for it.
Case 2. i>nB+1 Subcase 2.1. Batch B(h)i−1 is not an empty batch (but possibly it is a dummy batch).
Move all the B-jobs in B(h)i with their due dates no more than dBk into B(h)i−1. If B(h)i contains no job after these jobs are moved, then it becomes a dummy batch.
Subcase 2.2. Batch B(h)i−1 is an empty batch, i.e., it has processing time zero and setup time zero.
Subcase 2.2.1. There is no dummy batch which succeeds B(h)i.
Introduce a new setup time s for B(h)i−1. Move all the B-jobs in B(h)i with their due dates no more than dBk into B(h)i−1. If B(h)i contains no job after these jobs are moved, then it becomes a dummy batch.
Subcase 2.2.2. There is a dummy batch which succeeds B(h)i.
Move all the B-jobs in B(h)i with their due dates no more than dBk into B(h)nB+1. If B(h)i contains no job after these jobs are moved, then it becomes a dummy batch. All the empty batches B(h)nB+2,B(h)nB+3,…,B(h)i−1 keep unchanged.
Step 2. Update the completion times of the jobs and the batches. Update the lateness values of the jobs accordingly.
Step 3. Repeat Steps 1 and 2 until there is no inequality violation in adjusted σ(h). Let σ(h+1) be the final σ(h).
In the h-iteration, Algorithm BATCHCO constructs σ(h) by adjusting σ(h−1). The adjustment of σ(h−1) is accomplished by performing a series of inequality violation adjustments. During the iteration, we get a series of tentative schedules σ(h)1,σ(h)2,…,σ(h)λh, where λh is the total number of tentative schedules in the h-iteration. Note that σ(h)1 is just the last tentative schedule in the preceding iteration, i.e., σ(h)1=σ(h−1)λh−1. Each next tentative schedule is obtained from the current tentative schedule by performing an inequality violation adjustment. When we describe Procedure PBATCHCO(J,y(h)), all tentative schedules except for the last one are denoted by σ(h−1), and σ(h)λh is denoted by σ(h). Here, for clarity of the discussion, the tentative schedules need to be distinguished more clearly. Among these tentative schedules, only σ(h)λh belongs to Π(J,y(h)).
If a schedule belongs to Π(J,y(h)), then all jobs in it have lateness values less than y(h), and vice versa. To analyze Procedure PBATCHCO(J,y(h)), we need the concept of candidate schedule. A candidate schedule for y(h) is a schedule which has the potential to be in Π(J,y(h)). Denote by Λ(J,y(h)) the set of candidate schedules for y(h). If we find a job in a schedule with lateness greater than or equal to y(h), then we get evidence that this schedule cannot be in Λ(J,y(h)). It is possible that at first a schedule is treated as in Λ(J,y(h)) because we have not found any job in it with lateness greater than or equal to y(h), but later we find evidence and exclude this schedule from Λ(J,y(h)). Clearly, Π(J,y(h))⊆Λ(J,y(h)).
For any given schedule σ=(B1,B2,…,BnB,BnB+1,…,B2nB+1), let σL=(B1,B2,…,BnB) and σR=(BnB+2,BnB+3,…,B2nB+1) denote the left side and right side of σ, respectively. Let n(σL) and n(σR) denote the numbers of nonempty B-batches on the left and right sides of σ, respectively. Let ΓB(σ) denote the set of the B-jobs in ⋃nB+1q=1Bq, i.e., the set of the B-jobs in σ which are not on the right side.
Lemma 2.3. Let σ(h)w=(B(h)w,1,B(h)w,2,…,B(h)w,nB,B(h)w,nB+1,…,B(h)w,2nB+1) denote the w-th tentative schedule (1≤w≤λh) during the implementation of Procedure PBATCHCO(J,y(h)) (h=0,1.…). Let σ=(B1,B2,…,BnB,BnB+1,…,B2nB+1) denote any schedule in Λ(J,y(h)). Then the following properties hold:
(1) ΓB(σ(h)1)⊆ΓB(σ(h)2)⊆⋯⊆ΓB(σ(h)λh)⊆ΓB(σ);
(2) If ΓB(σ(h)w)=ΓB(σ), then
(i) ⋃nB+1q=iB(h)w,q⊇⋃nB+1q=iBq, i=nB+1,nB,…,1;
(ii) n(σ(h)w,L)≤n(σL);
(iii) Batch B(h)w,i starts and completes no later than batch Bi, i=1,2,…,nB+1.
Proof. We prove the lemma by induction on h.
Consider PBATCHCO(J,y(0)). Obviously, the initial schedule σ(0) (described in Step 1 of Algorithm BATCHCO) and any schedule in Λ(J,y(0))=Π(J,y(0))=Π(J) satisfy the properties of the lemma, thus proving the base case.
Assume that the lemma holds for PBATCHCO(J,y(0)),PBATCHCO(J,y(1)),…,PBATCHCO(J,y(h)). We now consider PBATCHCO(J,y(h+1)).
Since y(h+1)<y(h), we have: Λ(J,y(h+1))⊆Λ(J,y(h)). Let σ be any schedule in Λ(J,y(h+1)). Then σ∈Λ(J,y(h)). Note that σ(h+1)1, the first tentative schedule for PBATCHCO(J,y(h+1)), is just σ(h)λh, the last one for PBATCHCO(J,y(h)). By the inductive assumption, σ(h+1)1 and σ satisfy the properties of the lemma. Assume that each of the first w (1≤w<λh+1) tentative schedules and σ satisfy the properties of the lemma. Below, we will prove that σ(h+1)w+1 and σ also satisfy the properties of the lemma. Suppose that we find a job JBk∈B(h+1)w,i which violates the inequality LBk(C(B(h+1)w,i))<y(h+1). There are two different cases to consider:
Case 1. i≤nB+1.
As described in Case 1 of Step 1 of Procedure PBATCHCO(J,y(h+1)), we move all the B-jobs in B(h+1)w,i with their due dates no more than dBk into B(h+1)w,i−1. Denote the obtained schedule as σ(h+1)w+1.
By the inductive assumption, we have: ΓB(σ(h+1)w)⊆ΓB(σ). Since ΓB(σ(h+1)w+1)=ΓB(σ(h+1)w), we get: ΓB(σ(h+1)w+1)⊆ΓB(σ). Hence, property (1) holds for σ(h+1)w+1 and σ.
To prove that property (2) holds for σ(h+1)w+1 and σ, we assume that ΓB(σ(h+1)w+1)=ΓB(σ). Then we have: ΓB(σ(h+1)w)=ΓB(σ). By the inductive assumption, we know that property (2) holds for σ(h+1)w and σ. Hence, we have: C(B(h+1)w,i)≤C(Bi). Since LBk(C(B(h+1)w,i))≥y(h+1), we get LBk(C(Bi))≥y(h+1). Hence, all the B-jobs in B(h+1)w,i with their due dates no more than dBk have to be scheduled earlier than Bi in σ.
The above argument ensures that property (i) of property (2) holds for σ(h+1)w+1 and σ. Thus, properties (ii) and (iii) of property (2) hold for σ(h+1)w+1 and σ.
Case 2. i>nB+1.
Subcase 2.1. Batch B(h+1)w,i−1 is not an empty batch (but possibly it is a dummy batch).
As described in Subcase 2.1 of Step 1 of Procedure PBATCHCO(J,y(h+1)), we move all the B-jobs in B(h+1)w,i with their due dates no more than dBk into B(h+1)w,i−1.
If i>nB+2, then the operation deals with only the right side of B(h+1)w,nB+1 and does not affect the two properties of the lemma. The lemma holds for σ(h+1)w+1 and σ.
If i=nB+2, then below we show an argument similar to the proof of Case 1, to prove that all the B-jobs in B(h+1)w,i with their due dates no more than dBk have to be scheduled earlier than Bi in σ.
Let B(h+1)w,z denote the earliest dummy batch which succeeds B(h+1)w,i, where z>i. If there is no dummy batch which succeeds B(h+1)w,i, then set z=2nB+2. It is easy to prove that ⋃z−1q=iB(h+1)w,q⊆⋃z−1q=iBq. Remove the jobs in (⋃z−1q=iBq)∖(⋃z−1q=iB(h+1)w,q) from batches Bi,Bi+1,…,Bz−1 and let the obtained batches be B′i,B′i+1,…,B′z−1. Note that B′i,B′i+1,…,B′z−1 are all non-empty. We can get ⋃z−1q=gB(h+1)w,q⊇⋃z−1q=gB′q, g=z−1,z−2,…,i. Hence, we get C(B(h+1)w,g)≤C(B′g), g=i,i+1,…,z−1. It follows that C(B(h+1)w,g)≤C(Bg), g=i,i+1,…,z−1. Since LBk(C(B(h+1)w,i))≥y(h+1), we get LBk(C(Bi))≥y(h+1). Hence, all the B-jobs in B(h+1)w,i with their due dates no more than dBk have to be scheduled earlier than Bi in σ.
Hence, for i=nB+2, property (2) holds for σ(h+1)w+1 and σ.
Subcase 2.2. Batch B(h+1)w,i−1 is an empty batch, i.e., it has processing time zero and setup time zero.
Subcase 2.2.1. There is no dummy batch which succeeds B(h+1)w,i.
As described in Subcase 2.2.1 of Step 1 of Procedure PBATCHCO(J,y(h+1)), we move all the B-jobs in B(h+1)w,i with their due dates no more than dBk into B(h+1)w,i−1. The operation deals with only the right side of B(h+1)w,nB+1 and does not affect the two properties of the lemma. The lemma holds for σ(h+1)w+1 and σ.
Subcase 2.2.2. There is a dummy batch which succeeds B(h+1)w,i.
Let B(h+1)w,z denote the earliest dummy batch which succeeds B(h+1)w,i, where z>i. If we introduce a new setup time s for B(h+1)w,i−1, then the completion times of batch B(h+1)w,i and its succeeding batches will increase by s. Consequently, the jobs in B(h+1)w,z−1 will have costs not less than y(h+1). In order to decrease the undesirable costs of these jobs, we have to move all the jobs in B(h+1)w,g into B(h+1)w,g−1, g=z−1,z−2,…,i. Job JBk has to violate its inequality once again. Nothing has changed except that the indices of B(h+1)w,i,B(h+1)w,i+1,…,B(h+1)w,z−1 decrease by 1.
Therefore, we cannot introduce a new setup time s for B(h+1)w,i−1. Instead, as described in Subcase 2.2.2 of Step 1 of Procedure PBATCHCO(J,y(h+1)), we move all the B-jobs in B(h+1)w,i with their due dates no more than dBk into B(h+1)w,nB+1. Denote the obtained schedule as σ(h+1)w+1.
Assume that ΓB(σ(h+1)w)=ΓB(σ) before we do the operation described in Subcase 2.2.2 of Step 1 of Procedure PBATCHCO(J,y(h+1)). Let E denote the set of the jobs in B(h+1)w,i,B(h+1)w,i+1,…,B(h+1)w,z−1. In σ, the number of the batches containing jobs in E is not less than that number in σ(h+1)w, i.e., z−i. Hence, if JBk is scheduled to the right side of BnB+1, then either JBk or the jobs in the latest batch containing jobs in E will have cost not less than y(h+1). Therefore, in σ, all the B-jobs in B(h+1)w,i with their due dates no more than dBk cannot be scheduled to the right side of BnB+1.
The above argument shows that property (1) of the lemma holds for σ(h+1)w+1 and σ. Since we moved all the B-jobs in B(h+1)w,i with their due dates no more than dBk into B(h+1)w,nB+1, combining the inductive assumption, we know that property (2) of the lemma also holds for σ(h+1)w+1 and σ. This completes the proof for PBATCHCO(J,y(h+1)).
By the principle of induction, we complete the proof of the lemma.
We get:
Lemma 2.4. Let σ(h) denote the last schedule upon the completion of Procedure PBATCHCO(J,y(h)) (h=0,1.…). If σ(h)=∅, then Π(J,y(h))=∅; Otherwise σ(h) has minimum CAmax among all schedules in Π(J,y(h)).
Proof. During the entire implementation of Algorithm BATCHCO, any job can only be moved to the left. Consequently, the completion time of any batch will not decrease, which in turn ensures that any job cannot be moved to the right.
Suppose that in implementing PBATCHCO(J,y(h)) we find a job JBk∈B(h−1)i such that LBk(C(B(h−1)i))≥y(h). If i=1, then JBk cannot be feasibly scheduled in any schedule in Π(J,y(h)), implying that Π(J,y(h))=∅. Therefore, we return σ(h)=∅. If i≤nB and B(h−1)i contains no jobs after we move all the B-jobs in B(h−1)i with their due dates no more than dBk into B(h−1)i−1, we also return σ(h)=∅. This can be verified by the minimality of the number of nonempty B-batches in σ(h−1)L (by property (ii) of property (2) of Lemma 2.3).
On the other hand, if σ(h)≠∅, then by property (iii) of property (2) of Lemma 2.3, σ(h) has minimum CAmax among all schedules in Π(J,y(h)).
We get:
Theorem 2.5. Algorithm BATCHCO solves 1|s−batch,b≥n,co,batch−avail|(CAmax,LBmax) in O(nA+nB3) time.
Proof. The correctness of the algorithm follows from Lemma 2.2 and Lemma 2.4.
In PBATCHCO(J,y(h+1)), finding and adjusting an inequality violation requires O(nB) time. In each adjustment, at least one B-job has to be moved to the left. Since any B-job can only be moved to the left, in the entire implementation of Algorithm BATCHCO, each B-job can go through at most 2nB batches. The total number of adjustments is O(nB2). The running time of Algorithm BATCHCO is O(nA+nB3) time.
Next, we show how to improve the time complexity of the algorithm to O(nA+nB2lognB).
For storing the completion times of all B-jobs, we use an array Abcompl, where the j-position of Abcompl stores the completion time of job JBj in the current schedule, j=1,2,…,nB. The completion times of all jobs in a common batch are equal. Recall that all B-jobs are scheduled in EDD order. We set an indicator for each batch that points to the first B-job (which has the smallest due date among the B-jobs in this batch) in this batch, whereby we immediately know the contents of all batches in the schedule.
It is useful to store the lateness values of all B-jobs in a max-heap [24], so that the LBmax-value of the current schedule can be extracted in O(lognB) time. However, the difficulty comes from how to efficiently maintain the heap. Therefore, we give up the idea. Instead, we use a max-heap Hblateness to store the lateness values of all batches consisting of at least one B-job, where the lateness value of a batch is defined to be the maximum lateness value of the B-jobs in this batch, which is equal to the completion time of the batch minus the due date of the first B-job in it. Thus, the LBmax-value of the current schedule can be extracted from Hblateness in O(lognB) time.
Let us illustrate how to efficiently maintain the array and the max-heap. Suppose that we are adjusting σ(h)=(B(h)1,B(h)2,…,B(h)nB,B(h)nB+1,…,B(h)2nB+1) in Step 1 of Procedure PBATCHCO(J,y(h+1)), and we find a job JBk∈B(h)i violating its inequality. As described in Step 1, there are two different cases to consider:
Case 1. i≤nB+1.
If i=1, or i≤nB and JBk has the largest due date in B(h)i, then return σ(h+1)=∅. Otherwise, let B(h)i,1 denote the set of the jobs to be moved from B(h)i to B(h)i−1, i.e., B(h)i,1 consists of the B-jobs with their due dates no more than dBk in B(h)i. Let p(B(h)i,1)=∑JBj∈B(h)i,1pBj.
Subcase 1.1. B(h)i−1 is not an empty batch.
After the jobs in B(h)i,1 are moved into B(h)i−1, the completion time of batch B(h)i−1, C(B(h)i−1), will increase by p(B(h)i,1). The lateness value of B(h)i−1 will also increase by p(B(h)i,1). All the other batches keep their completion times and lateness values unchanged. We just update the lateness value of B(h)i−1 in Hblateness. Therefore, finding a B-job violating its inequality can be done in O(lognB) time. Each job movement can be done in constant time. Since there are O(nB2) job movements, it takes O(nB2lognB) time to deal with this case.
Subcase 1.2. B(h)i−1 is an empty batch.
After the jobs in B(h)i,1 are moved into B(h)i−1, B(h)i−1 becomes nonempty and a setup time s incurs before it is started. The completion times of all the jobs in B(h)i−1 and succeeding batches will change. Therefore, we recalculate them and update Abcompl accordingly. Then, we recalculate the lateness values of B(h)i−1 and succeeding batches and update Hblateness accordingly in O(nBlognB) time. Since this case occurs at most O(nB) times, it takes O(nB2lognB) time to deal with it.
Case 2. i>nB+1.
Subcase 2.1. Batch B(h)i−1 is not an empty batch (but possibly it is a dummy batch).
Similarly to Subcase 1.1, let B(h)i,1 denote the set of the jobs to be moved from B(h)i to B(h)i−1. Let p(B(h)i,1)=∑JBj∈B(h)i,1pBj. After the jobs in B(h)i,1 are moved into B(h)i−1, the completion time of batch B(h)i−1, C(B(h)i−1), will increase by p(B(h)i,1). The lateness value of B(h)i−1 will also increase by p(B(h)i,1). We update the lateness value of B(h)i−1 in Hblateness. Moreover, if B(h)i contains no job after the jobs are moved, then it becomes a dummy batch and thus we delete the lateness value of B(h)i from Hblateness. Since there are O(nB2) job movements, it takes O(nB2lognB) time to deal with this case.
Subcase 2.2. Batch B(h)i−1 is an empty batch, i.e., it has processing time zero and setup time zero.
Subcase 2.2.1. There is no dummy batch which succeeds B(h)i.
Similarly to Subcase 1.2, let B(h)i,1 denote the set of the jobs to be moved from B(h)i to B(h)i−1. Let p(B(h)i,1)=∑JBj∈B(h)i,1pBj. After the jobs in B(h)i,1 are moved into B(h)i−1, B(h)i−1 becomes nonempty and a setup time s incurs before it is started. The completion times of all the jobs in B(h)i−1 and succeeding batches will change. Therefore, we recalculate them and update Abcompl accordingly. Then, we recalculate the lateness values of B(h)i−1 and succeeding batches and update Hblateness accordingly in O(nBlognB) time. Particularly, if B(h)i contains no job now, then it becomes a dummy batch and thus we delete the lateness value of B(h)i from Hblateness.
Since this case occurs at most O(nB) times, it takes O(nB2lognB) time to deal with it.
Subcase 2.2.2. There is a dummy batch which succeeds B(h)i. After we move all the B-jobs in B(h)i with their due dates no more than dBk into B(h)nB+1, we need to update the lateness value of B(h)nB+1 in Hblateness. Moreover, if B(h)i contains no job after the jobs are moved, then it becomes a dummy batch and thus we delete the lateness value of B(h)i from Hblateness. Since this case occurs at most O(nB) times, it takes O(nB2) time to deal with it.
The array Abcompl and max-heap Hblateness have sizes of O(nB). Hence, we get:
Theorem 2.6. A careful implementation of Algorithm BATCHCO leads to an O(nA+nB2lognB)-time algorithm for 1|s−batch,b≥n,co,batch−avail|(CAmax,LBmax) with O(nB) memory requirements.
With respect to the incompatible model, recall that we always represent a schedule by a batch sequence B1,B2,…,BnB,BnB+1,…,B2nB+1, where BnB+1 is the batch containing all A-jobs. Note that batch BnB+1 can no longer contain any B-job. Therefore, we simply treat batch BnB as the left adjacent batch of BnB+2 so that BnB+1 can be bypassed. When we move the B-jobs from right to the left, those jobs moved out of batch BnB+2 should be directly put into batch BnB. With such a slight modification, the above algorithm and its analysis work properly for the incompatible model. Therefore, we get:
Theorem 2.7. There is an O(nA+nB2lognB)-time algorithm for 1|s−batch,b≥n,inco,batch−avail|(CAmax,LBmax) with O(nB) memory requirements.
In this section we will present O(nA+nBlognB)-time algorithms for the compatible and incompatible models under item availability, i.e., 1|s−batch,b≥n,co,item−avail|(CAmax,LBmax) and 1|s−batch,b≥n,inco,item−avail|(CAmax,LBmax).
For the compatible model, we have the following lemma:
Lemma 3.1. For any Pareto optimal point of 1|s−batch,b≥n,co,item−avail|(CAmax,LBmax), there is a corresponding Pareto optimal schedule with the following properties:
(1) All jobs are contained in a single batch;
(2) All A-jobs are processed consecutively, i.e., they form a block such that no B-job is scheduled between two A-jobs;
(3) All B-jobs are scheduled in EDD order.
Proof. For any two consecutive batches, we can merge them into one batch with only a single setup retained. Repeat this process and we will obtain a schedule satisfying property (1), without increasing CAmax or LBmax.
Fix the position of the last A-job in this single-batch schedule. Move all the earlier A-jobs to later such that all A-jobs are processed consecutively, without increasing CAmax or LBmax. This schedule thus satisfies properties (1) and (2).
Fix a Pareto optimal schedule satisfying properties (1) and (2). If there are two B-jobs such that the earlier one has a larger due date than the later one, then we reschedule the B-job with a larger due date to let it complete immediately after the B-job with a smaller due date. Repeat this process and finally, we will obtain the desired Pareto optimal schedule.
Re-index all B-jobs in EDD order so that dB1≤dB2≤⋯≤dBnB. By Lemma 3.1, there are O(n) Pareto optimal schedules, each for an intermediate position of the block of A-jobs. Based on the idea, we present Algorithm ITEMCO below which solves 1|s−batch,b≥n,co,item−avail|(CAmax,LBmax) easily.
Algorithm ITEMCO:
Step 1. Let σ(0) be the initial schedule consisting of a single batch. The A-jobs in the batch are first processed in arbitrary order, and the B-jobs in the batch are then processed in EDD order. Let Ω(J)={(CAmax(σ(0)),LBmax(σ(0)),σ(0))}.
Step 2. For j=1,2,…,nB, perform the j-th iteration to get schedule σ(j): Move job JBj earlier such that it starts immediately before the block of A-jobs. If LBmax(σ(j))<LBmax(σ(j−1)), then let Ω(J)=Ω(J)∪{(CAmax(σ(j)),LBmax(σ(j)),σ(j))}.
We get:
Theorem 3.2. Algorithm ITEMCO solves 1|s−batch,b≥n,co,item−avail|(CAmax,LBmax) in O(nA+nBlognB) time.
For the incompatible model, we have the following lemma:
Lemma 3.3. For any Pareto optimal point of 1|s−batch,b≥n,inco,item−avail|(CAmax,LBmax), there is a corresponding Pareto optimal schedule with the following properties:
(1) All A-jobs belong to a common batch;
(2) All B-jobs are scheduled in EDD order;
(3) There are at most two B-batches and they are separated by the batch containing all A-jobs.
Re-index all B-jobs in EDD order so that dB1≤dB2≤⋯≤dBnB. By Lemma 3.3, there are O(n) Pareto optimal schedules, each for an intermediate position of the batch containing all A-jobs. Based on the idea, we present Algorithm ITEMINCO below which solves 1|s−batch,b≥n,inco,item−avail|(CAmax,LBmax) easily.
Algorithm ITEMINCO:
Step 1. Let σ(0)=(B1,B2,B3) be the initial schedule, where B1 is an empty batch, B2 consists of all A-jobs, and B3 consists of all B-jobs. The B-jobs in B3 are processed in EDD order. Let Ω(J)={(CAmax(σ(0)),LBmax(σ(0)),σ(0))}.
Step 2. For j=1,2,…,nB, perform the j-th iteration to get schedule σ(j): Move job JBj from B3 into B1. If B1 is empty before JBj is moved, then a setup incurs after JBj is moved into B1. If LBmax(σ(j))<LBmax(σ(j−1)), then let Ω(J)=Ω(J)∪{(CAmax(σ(j)),LBmax(σ(j)),σ(j))}.
We get:
Theorem 3.4. Algorithm ITEMINCO solves 1|s−batch,b≥n,inco,item−avail|(CAmax,LBmax) in O(nA+nBlognB) time.
In this paper, we studied the two-agent scheduling problem on an unbounded serial-batch machine to minimize the makespan of agent A and the maximum lateness of agent B simultaneously. We presented improved algorithms for compatible and incompatible models under batch availability and item availability assumptions. For future research, it is interesting to consider the combinations of general min-max and min-sum criteria, for example, (fAmax,fBmax), (fAmax,∑CBj) and (∑CAj,∑CBj). The bounded batch scheduling model with multiple agents can also be considered.
The authors declare they have not used Artificial Intelligence (AI) tools in the creation of this article.
This work is supported by Natural Science Foundation of Shandong Province China (No. ZR2020MA030).
The authors declare there is no conflict of interest.
[1] |
G. B. Apolinário, L. Chevillard, Space-time statistics of a linear dynamical energy cascade model, Mathematics in Engineering, 5 (2023), 1–23. http://doi.org/10.3934/mine.2023025 doi: 10.3934/mine.2023025
![]() |
[2] |
G. Basile, D. Benedetto, E. Caglioti, L. Bertini, Large deviations for a binary collision model: energy evaporation, Mathematics in Engineering, 5 (2023), 1–12. http://doi.org/10.3934/mine.2023001 doi: 10.3934/mine.2023001
![]() |
[3] |
J. Bedrossian, N. Masmoudi, Inviscid damping and the asymptotic stability of planar shear flows in the 2D Euler equations, Publ. math. IHES, 122 (2015), 195–300. http://doi.org/10.1007/s10240-015-0070-4 doi: 10.1007/s10240-015-0070-4
![]() |
[4] |
G. Bevilacqua, Symmetry break in the eight bubble compaction, Mathematics in Engineering, 4 (2022), 1–24. http://doi.org/10.3934/mine.2022010 doi: 10.3934/mine.2022010
![]() |
[5] |
T. Buckmaster, C. De Lellis, L. Székelyhidi Jr., Dissipative Euler flows with Onsager-critical spatial regularity, Commun. Pure Appl. Math., 69 (2016), 1613–1670. http://doi.org/10.1002/cpa.21586 doi: 10.1002/cpa.21586
![]() |
[6] | C. Collot, P. Germain, Derivation of the kinetic wave equation for quadratic dispersive problems in the inhomogeneous setting, 2021, arXiv: 2107.11819. |
[7] |
G. Crippa, C. Schulze, Sub-exponential mixing of generalized cellular flows with bounded palenstrophy, Mathematics in Engineering, 5 (2023), 1–12. http://doi.org/10.3934/mine.2023006 doi: 10.3934/mine.2023006
![]() |
[8] |
Y. C. de Verdière, L. Saint-Raymond, Attractors for two-dimensional waves with homogeneous Hamiltonians of degree 0, Commun. Pure Appl. Math., 73 (2020), 421–462. http://doi.org/10.1002/cpa.21845 doi: 10.1002/cpa.21845
![]() |
[9] |
D. Del Santo, F. Fanelli, G. Sbaiz, A. Wróblewska-Kamińska, On the influence of gravity in the dynamics of geophysical flows, Mathematics in Engineering, 5 (2023), 1–33. http://doi.org/10.3934/mine.2023008 doi: 10.3934/mine.2023008
![]() |
[10] |
C. De Lellis, L. Székelyhidi Jr., Dissipative Euler flows and Onsager's conjecture, J. Eur. Math. Soc., 16 (2014), 1467–1505. http://doi.org/10.4171/JEMS/466 doi: 10.4171/JEMS/466
![]() |
[11] | Y. Deng, Z. Hani, Full derivation of the wave kinetic equation, 2021, arXiv: 2104.11204. |
[12] |
M. Duerinckx, On nonlinear Schrödinger equations with random initial data, Mathematics in Engineering, 4 (2022), 1–14. http://doi.org/10.3934/mine.2022030 doi: 10.3934/mine.2022030
![]() |
[13] | G. E. Fal'kovich, A. V. Shafarenko, Nonstationary wave turbulence, J. Nonlinear Sci., 1 (1991), 457–480. |
[14] |
S. Federico, G. Staffilani, Sharp Strichartz estimates for some variable coefficient Schrödinger operators on R×T2, Mathematics in Engineering, 4 (2022), 1–23. http://doi.org/10.3934/mine.2022033 doi: 10.3934/mine.2022033
![]() |
[15] |
R. Feola, F. Iandoli, F. Murgante, Long-time stability of the quantum hydrodynamic system on irrational tori, Mathematics in Engineering, 4 (2022), 1–24. http://doi.org/10.3934/mine.2022023 doi: 10.3934/mine.2022023
![]() |
[16] | R. P. Feynman, R. Leighton, M. Sands, The Feynman lectures on physics, Volume I, 2015. |
[17] |
F. Flandoli, E. Luongo, Heat diffusion in a channel under white noise modeling of turbulence, Mathematics in Engineering, 4 (2022), 1–21. http://doi.org/10.3934/mine.2022034 doi: 10.3934/mine.2022034
![]() |
[18] |
L. E. Hientzsch, On the low Mach number limit for 2D Navier–Stokes–Korteweg systems, Mathematics in Engineering, 5 (2023), 1–26. http://doi.org/10.3934/mine.2023023 doi: 10.3934/mine.2023023
![]() |
[19] |
J. Lukkarinen, H. Spohn, Weakly nonlinear Schrödinger equation with random initial data, Invent. Math., 183 (2011), 79–188. http://doi.org/10.1007/s00222-010-0276-5 doi: 10.1007/s00222-010-0276-5
![]() |
[20] | S. Nazarenko, Wave turbulence, Berlin, Heidelberg: Springer, 2011. http://doi.org/10.1007/978-3-642-15942-8 |
[21] |
C. Nobili, The role of boundary conditions in scaling laws for turbulent heat transport, Mathematics in Engineering, 5 (2023), 1–41. http://doi.org/10.3934/mine.2023013 doi: 10.3934/mine.2023013
![]() |
[22] |
A. Nota, J. J. L. Velázquez, Homoenergetic solutions of the Boltzmann equation: the case of simple-shear deformations, Mathematics in Engineering, 5 (2023), 1–25. http://doi.org/10.3934/mine.2023019 doi: 10.3934/mine.2023019
![]() |
[23] |
D. Varma, M. Mathur, T. Dauxois, Instabilities in internal gravity waves, Mathematics in Engineering, 5 (2023), 1–34. http://doi.org/10.3934/mine.2023016 doi: 10.3934/mine.2023016
![]() |
1. | Shuguang Li, Jing Wei, Yanyue Liang, Haoxuan Shen, Vladimir Simic, Dragan Pamucar, A Pareto optimal scheduling algorithm for two agents with compatible non-disjoint jobs on an unlimited serial-batch processor, 2024, 1435-246X, 10.1007/s10100-024-00954-9 |