# OL-DEC-MDP Model for Multiagent Online Scheduling with a Time-Dependent Probability of Success

Authors: Cheng Zhu; Jiangfeng Luo; Weiming Zhang; Zhong Liu
Journal: Mathematical Problems in Engineering
 (2014)

---

## Abstract

Focusing on the on-line multiagent scheduling problem, this paper considers the time-dependent probability of success and processing duration and proposes an OL-DEC-MDP (opportunity loss-decentralized Markov Decision Processes) model to include opportunity loss into scheduling decision to improve overall performance. The success probability of job processing as well as the process duration is dependent on the time at which the processing is started. The probability of completing the assigned job by an agent would be higher when the process is started earlier, but the opportunity loss could also be high due to the longer engaging duration. As a result, OL-DEC-MDP model introduces a reward function considering the opportunity loss, which is estimated based on the prediction of the upcoming jobs by a sampling method on the job arrival. Heuristic strategies are introduced in computing the best starting time for an incoming job by each agent, and an incoming job will always be scheduled to the agent with the highest reward among all agents with their best starting policies. The simulation experiments show that the OL-DEC-MDP model will improve the overall scheduling performance compared with models not considering opportunity loss in heavy-loading environment.


---

## Body

## 1. Introduction

Problems involving time-dependent success probability extensively exist in manufacturing, industrial, and military domains. One example is the scheduling of a procrastinator [1], whose speed and success probability of job processing will increase as the due date is approaching. Practice shows that a procrastinator’s performance varies under different time pressures when processing the same job. As higher time pressure is more likely to force a procrastinator to make mistakes when processing a sophisticated job, the success probability is consequentially dependent on the starting time. Another example is the antiship missile defense by SAM (surface-air-missile) systems shown in [2]. SAM systems are scheduled to intercept the incoming antiship missiles within feasible interception time window. Killing probability of the interception is associated with the range at which the interception missile and the antiship missile meets, which in turn depends on the launching time of the interception. Usually, an earlier firing time means more flight time before engagement.Both of the above examples imply that though early starting strategy for job processing guarantees maximal time window for processing, longer processing duration will be spent as a price. Compared with the classic on-line scheduling [3, 4], extra trade-offs should be considered by the agent between the current job and the possible incoming jobs. For example, Figure 1 gives the killing probability associated with the time at which the engagement occurs for a SAM system of a Halifax ship against the incoming antiship missile [5]. It can be inferred that an antiship missile can be intercepted in the feasible time window [tl,tu]. Hence the SAM system can choose the best engaging time tm to get the highest killing probability. If the interception fails, SAM system will have time window [tm,tu] to take an immediate remedial interception. However, if the SAM system fires at earlier time and makes the engagement occur at tl, though the killing probability is lowered down, longer time window is left in case of interception fail. Therefore, the SAM system needs to make trade-off between a high killing probability of current interception and more feasible time left to take remedial action in case of interception fail. In addition, for an antiship missile and a SAM system, an earlier firing time always means more flight time before the engagement. Hence adopting the early firing strategy would cause SAM system to spend longer duration on the current interception, while losing more opportunities to intercept possible upcoming missiles. This is the second trade-off to be considered.Figure 1
Engagement time-dependent killing probability of the interception missile.Similar trade-off also exists in the application of procrastinator on-line scheduling [1]. To the best of our knowledge, multiagent on-line scheduling with the trade-off discussed above is not studied by previous researches such as time-dependent scheduling [6–9], on-line stochastic optimization [3, 4, 10, 11], and stochastic resource allocation in a multiagent environment [12–15]. Therefore, in this paper, we consider the above trade-offs in a multiagent scheduling process. There are several independent agents that can be scheduled to process the stochastically arriving jobs. Each job has a specific feasible time window, during which an agent can process it with time-dependent success probability. In case of fail, an agent will immediately make another try as long as the remaining time window allows. The objective is to complete all jobs with high probability. A general problem definition is introduced in Section 2, and Section 3 surveys closely related studies. Section 4 builds a DEC-MDP (decentralized Markov Decision Processes) to model the on-line multiagent scheduling process without considering the opportunity loss. An OL-DEC-MDP (opportunity loss-decentralized Markov Decision Processes) model is proposed in Section 5 to include the opportunity loss in the scheduling decision with proofs on its properties. Section 6 is the simulation evaluation of the OL-DEC-MDP, and Section 7 contains the conclusions and the future work.


## 2. Problem Definitions

There is a group of agents, denoted asI, that should be scheduled to process a set of stochastically arriving jobs, which is denoted as J. For each job j∈J, there is a time interval Tj=[tjl,tju], during which the process of job j is feasible. For example, tjl and tju are the low bound and upper bound of the feasible time window for job j to be processed. For each agent i∈I, there is a duration dij(t), which should be spent to process job j for one time starting from time t. The outcome of the process by the end of dij(t) is either success or fail, and probability of success is denoted as pij(t).Assumption 1.
One agent can only be scheduled to process one job at a time.Assumption 2.
If the agent fails to complete the job by the end of the process, it will immediately start another try as long as the feasible processing time window of the job will not elapse before the next try can be finished.Assumption 3.
The agent will be released from the current job and be available for the next job, if either the current job is completed successfully or the current job is discarded because of insufficient time window left for another try.According to the above assumptions, an agenti will have several opportunities to complete a job j before the feasible time window [tjl,tju] of job j elapses depending on the process duration dij(t) of each try. For example, If a process starting from time t0 fails by the end of time t0+dij(t0), agent i must try to reprocess the job immediately at time t0+dij(t0), as long as t0+dij(t0)+dij(t0+dij(t0))≤tju.Assumption 4.
For an assignment of jobj to agent i, later a try of process starts; later the process will end, but the process duration will be shorter.Assumption4 is in accordance with the observations in the time-sensitive applications such as air defense. With the threat approaching, the time needed for an interception is diminishing. For example, the earlier a process starts, the earlier the effect can be observed, but a longer duration needs to be spent. According to Assumption 4, For any t1, t2∈[tjl,tju], s.t. t1+dij(t1)∈[tjl,tju],t2+dij(t2)∈[tjl,tju], if t1<t2, then dij(t1)>dij(t2) and t1+dij(t1)<t2+dij(t2).Assumption 5.
Each agent operates independently, and there is no resource competition or mutual influence between agents.The objective is to schedule the agents on-line to successfully complete all the arriving jobs with highest probability. In the off-line case, the objective of the problem can be modelled as (1)
(1)max⁡∏i∈I(1-∏j∈J(1-pij(t))uij(t))
s.t. 						(2)uij(t)={1ifagentistartstoprocessorreprocessjobjattimet0otherwise,∑uij(t)≥0,(3)t∈[tjl,tju],t+dij∈[tjl,tju],foranyuij(t)=1;
objective function (1) is to maximize the probability of successfully completing all the incoming jobs. Constraint (2) implies that an agent can process a job more than one time. Constraint (3) ensures that a try of job processing should not be started if the feasible time window of the job will elapse before a try can be finished.Compared with a similar model in Karasakal et al. [2], the starting time of job processing in the above model is continuously distributed in a job’s feasible time window. Moreover, in the on-line version, the future arriving jobs could not be known in advance, which makes the model more difficult to solve.As a result, trade-off should be made during the on-line scheduling of the problem to ensure good scheduling quality:(1)
the trade-off between the probability of successful process of the current job and the probability of the successful reprocess of the job in case of fail;(2)
the trade-off between the reward of successful process of the current job and the opportunity loss that the agent might have with other incoming jobs during the current job processing.


## 3. Related Works

### 3.1. Scheduling

Job scheduling [16] is a classic domain to solve the problem, in which jobs need to be handled by one ore more machines regarding the constraints of due date, processing time, priorities, and so forth. There are many different models such as single or parallel machine model depending on the number of machines. If a job needs to be handled by a series of machines in-order, the models are called flow shops, job shops, or open shops under different situations. The objective is to handle all the jobs with a minimum makespan [17] or lateness [18, 19]. Time-independent uncertainties such as machine breakdowns, unexpected releases of jobs with high priority [16], duration of a processing [20], and execution uncertainty [21] are introduced in the scheduling, which are called stochastic scheduling. Recently, models on time-dependent scheduling are proposed, in which parameters of the scheduling are time-dependent. For example, learning effect and processing time are defined as increasing funtion [22, 23] or deceasing function [1, 24, 25] of their start times. However, most of the above studies are discussed in the off-line case, where all of the jobs exist from the beginning. Moreover, time-dependent parameters mainly focus on the processing times or the cost of processing, while time-dependent success probability of job processing is not discussed.


### 3.2. On-Line Stochastic Optimization

On-line stochastic optimization, such as the on-line packet scheduling, stochastic reservations, vehicle dispatching, or routing, has been studied [3, 4], in which a job or requisition arrives stochastically in queue to wait for a certain machine or a sever to be served. A job or requisition will be successfully processed once a machine is scheduled. Scheduling can be centralized or decentralized depending on whether the scheduling decision is made globally or by each agent. To model real-world problems, time-independent uncertainties such as action duration [11], resource consumption [10], and operation outcomes [12, 14] are introduced into the scheduling process. Sampling approach is also introduced to estimate the future arriving jobs to achieve a global optimal solution [26–28]. Similar to our problem, each agent of the above problem is dynamically scheduled against the stochastically arriving jobs, and there is no resource competition or dependences among the agents. However, time-dependent probability of success is not considered, and each job will be successfully processed once an agent is scheduled to process it. Moreover, job discarding is allowed if a more important job is arriving. Instead, in our problem, each agent should retry in case of fail as long as the time allows.


### 3.3. Stochastic Resource Allocation in Multiagent Environment

The most related studies in the area of stochastic resource allocation in multiagent environment mainly focus on the following problems; each agent can execute a task independently while different agents may share the same resources. An agent consuming shared resources may decrease the reward of other agents. As the outcome of the job execution is uncertain, the resources are allocated to achieve the global optimal solution. [12] solves this type of problems by introducing dynamic constraint satisfaction problem (DCSP) model into MDP and constructing a Markovian CSP (MaCSP) model. The best action at each Markovian step depends on the resource availability. As the state space increases exponentially with the number of agent and the types of resource, some studies propose heuristic search [29] and decomposition approaches [14, 15] in solving Decentralized Markov Decision Processes (DEC-MDP). As the dependency between different agents is taken into account, starting an action too early or too late by an agent may jeopardize the operation of others. Hence, trade-off is introduced into DEC-MDP to estimate the cost that one agent may suffer due to the negative influence of others [13].Comparing between our problems with closely related studies is listed in Table1.Table 1
Comparing of the closely related works.
Stochastic jobs or tasks
Multiagent (machine)
Dependences or resource competition among agents
Time-dependent processing time or action duration
Due date for jobs
On-line sampling
DEC-MDP
Time-dependent probability of success
Time-dependent scheduling
✓
✓
✓
On-line stochastic optimization
✓
✓
✓
✓
Stochastic resource allocation of multiagent
✓
✓
✓
✓
OL-DEC-MDP model based on-line scheduling
✓
✓
✓
✓
✓
✓
✓


## 3.1. Scheduling

Job scheduling [16] is a classic domain to solve the problem, in which jobs need to be handled by one ore more machines regarding the constraints of due date, processing time, priorities, and so forth. There are many different models such as single or parallel machine model depending on the number of machines. If a job needs to be handled by a series of machines in-order, the models are called flow shops, job shops, or open shops under different situations. The objective is to handle all the jobs with a minimum makespan [17] or lateness [18, 19]. Time-independent uncertainties such as machine breakdowns, unexpected releases of jobs with high priority [16], duration of a processing [20], and execution uncertainty [21] are introduced in the scheduling, which are called stochastic scheduling. Recently, models on time-dependent scheduling are proposed, in which parameters of the scheduling are time-dependent. For example, learning effect and processing time are defined as increasing funtion [22, 23] or deceasing function [1, 24, 25] of their start times. However, most of the above studies are discussed in the off-line case, where all of the jobs exist from the beginning. Moreover, time-dependent parameters mainly focus on the processing times or the cost of processing, while time-dependent success probability of job processing is not discussed.


## 3.2. On-Line Stochastic Optimization

On-line stochastic optimization, such as the on-line packet scheduling, stochastic reservations, vehicle dispatching, or routing, has been studied [3, 4], in which a job or requisition arrives stochastically in queue to wait for a certain machine or a sever to be served. A job or requisition will be successfully processed once a machine is scheduled. Scheduling can be centralized or decentralized depending on whether the scheduling decision is made globally or by each agent. To model real-world problems, time-independent uncertainties such as action duration [11], resource consumption [10], and operation outcomes [12, 14] are introduced into the scheduling process. Sampling approach is also introduced to estimate the future arriving jobs to achieve a global optimal solution [26–28]. Similar to our problem, each agent of the above problem is dynamically scheduled against the stochastically arriving jobs, and there is no resource competition or dependences among the agents. However, time-dependent probability of success is not considered, and each job will be successfully processed once an agent is scheduled to process it. Moreover, job discarding is allowed if a more important job is arriving. Instead, in our problem, each agent should retry in case of fail as long as the time allows.


## 3.3. Stochastic Resource Allocation in Multiagent Environment

The most related studies in the area of stochastic resource allocation in multiagent environment mainly focus on the following problems; each agent can execute a task independently while different agents may share the same resources. An agent consuming shared resources may decrease the reward of other agents. As the outcome of the job execution is uncertain, the resources are allocated to achieve the global optimal solution. [12] solves this type of problems by introducing dynamic constraint satisfaction problem (DCSP) model into MDP and constructing a Markovian CSP (MaCSP) model. The best action at each Markovian step depends on the resource availability. As the state space increases exponentially with the number of agent and the types of resource, some studies propose heuristic search [29] and decomposition approaches [14, 15] in solving Decentralized Markov Decision Processes (DEC-MDP). As the dependency between different agents is taken into account, starting an action too early or too late by an agent may jeopardize the operation of others. Hence, trade-off is introduced into DEC-MDP to estimate the cost that one agent may suffer due to the negative influence of others [13].Comparing between our problems with closely related studies is listed in Table1.Table 1
Comparing of the closely related works.
Stochastic jobs or tasks
Multiagent (machine)
Dependences or resource competition among agents
Time-dependent processing time or action duration
Due date for jobs
On-line sampling
DEC-MDP
Time-dependent probability of success
Time-dependent scheduling
✓
✓
✓
On-line stochastic optimization
✓
✓
✓
✓
Stochastic resource allocation of multiagent
✓
✓
✓
✓
OL-DEC-MDP model based on-line scheduling
✓
✓
✓
✓
✓
✓
✓


## 4. Decentralize MDP (DEC-MDP)

In theory, models (1)–(3) can obtain the optimal scheduling solution for an off-line problem. However, in the on-line case, the scheduling decision should be made according to the state of each agent and the incoming job in real time. As a result, MDP provides a suitable approach to model the on-line scheduling by mapping the current state of agents and incoming jobs to an optimal scheduling decision. In order to construct the MDP model of a problem, the state space of the problem should be defined.


### 4.1. States of the Agent and the Job

The state of an agent is eitherbusy when it is processing a job orunemployed when it is released from the current job. Let sai(t) denote the state of agent i at time t:
(4)sai(t)={busyifagentiisprocessingajobattimetunemployedotherwise.
If a job is being processed by an agent, the state of the job is modelled as the ratio of the remaining time window feasible for the job to be completed. If it is waiting to be processed, its state is set to be 0; if it has been completed successfully, the state is set to be 1; otherwise the state is set to be −1. Let smj(t) denote the state of job j at time t:
(5)smj(t)={0ift<tjlorjhasnotbeenscheduledtoanyagent;t-tjltju-tjlift∈[tjl,tju),andjisbeingprocessedbyanagent1ift≥tjlorjhasbeencompleted;-1ifjhasbeendiscarded.
For example, at time 0s, there is an unemployed agent i without any job coming. The state of the agent i at 0s is
(6)sai(0)=unemployed.At time10s, a job j arrives with feasible time window [12, 30], and it is scheduled to agent i which is due to start at time 12s. Then
(7)sai(t)=unemployed,smj(t)=0fort∈[10,12)sai(t)=busy,smj(t)=t-1230-12fort∈[12,12+dij(12)].
By Assumption 4, there is 12+dij(12)≤30. Suppose dij(12)=8, and job processing ends successfully; then
(8)sai(20)=unemployed,smj(20)=1.
If job processing fails by the time 20s, agent i will start another try to process job j immediately as long as 20+dij(20)≤30 holds. Suppose dij(20)=9; then
(9)sai(t)=busy,smj(t)=t-1230-12fort∈[20,20+dij(20)].
If job processing fails again by the end of the second try (e.g., at time 29s), and the remaining time window of job j (only 1 second is left, since tju=30) is not enough for another try, then job j will be discarded from time 29s:
(10)sai(t)=unemployed,smj(t)=-1fort>29.
In this case, agent i will be available for other incoming jobs from time 29s. As the different agents may be released or start to process a job at different times, it is hard to define a joint action, which is the set of actions for each agent in each decision step of the on-line scheduling process [13]. Moreover, because of the time-dependent state space, the reward of a joint action is difficult to evaluate by a recursive approach as introduced in [30]. Recently, in order to limit the set of state space in the multiagent environment, there is significant progress in extending the Markov Decision Processes (MDP) for optimizing decentralized control [13, 31]. In this paper, as there is no dependence or resource competition among agents, a decentralized MDP is adopted to model the decision process of each agent.


### 4.2. DEC-MDP

For an agenti and its allocated job j with time window [tjl,tju], the corresponding DEC-MDP is defined as a tuple 〈sij,Aij,pij,rij〉t1, where(i)
sij=(sai,smj) is the state set regarding agent i and job j during the whole process period (e.g., from the time when the process is started for the first time, denoted as t1, to the time when agent i is released from job j);(ii)
Aij is the strategy set of agent ai, represented by the starting time that agent i may choose to process job j for the first time. Aij={t∣t∈[tjl,tju],t+dij(t)∈[tjl,tju]};(iii)
pij(t) is a function of time t, which gives the success probability of completing job j by agent i by the time of t+dij(t), when the process or the reprocess starts at time t. According to Assumptions 2 and 3, there is pij(t)=0 if t∉[tjl,tju] or t+dij(t)∉[tjl,tju];(iv)
rij(t) is the reward function as defined in (13).The initial state of a DEC-MDP is
(11)sij(t1)={sai(t1)=busy,smj(t1)=(t1-tjl)(tju-tjl)}.
The absorbing state is
(12)sij(·)={sai(·)=unemployed,smj(·)=1or-1}.
Figure 2 shows the state transition process when agent ai starts to process job j at time t1 for the first time, in which the maximal retry times are K, and K is the smallest number that satisfies tK+1+dij(tK+1)>tju. The reward function is defined as in (13), which is represented by the probability that agent i will successfully complete job j when starting the first process at time t1. Consider
(13)rij(t1)=pij(t1)+∑x=2K(∏y=1x-1(1-pij(ty)))·pij(tx)
s.t. 								(14)tx∈[tjl,tju],tx+1=tx+dij(tx),tx+1∈[tjl,tju],HHHHx=1,2,…,K(15)tK+1+dij(tK+1)>tju;
when starting from time t1, agent i can process job j not more than K times. With (13)–(15), the best time for agent i to begin to process job j is t1*:
(16)t1*=argmax⁡t∈Aij⁡rij(t).
Therefore, during the on-line scheduling, we prefer scheduling the incoming job j to an agent i* with highest success probability:
(17)i*=argmax⁡i∈I⁡rij(t1*).
However, as stated in Section 4, this decision does not take the opportunity loss into account. Agent may lose higher rewards with upcoming jobs during its engagement with the current job. As a result, we introduce a opportunity loss decentralized MDP (OL-DEC-MDP) model in the next section.Figure 2
The state transition process of MDP〈sij,Aij,pij,rij〉t1.


## 4.1. States of the Agent and the Job

The state of an agent is eitherbusy when it is processing a job orunemployed when it is released from the current job. Let sai(t) denote the state of agent i at time t:
(4)sai(t)={busyifagentiisprocessingajobattimetunemployedotherwise.
If a job is being processed by an agent, the state of the job is modelled as the ratio of the remaining time window feasible for the job to be completed. If it is waiting to be processed, its state is set to be 0; if it has been completed successfully, the state is set to be 1; otherwise the state is set to be −1. Let smj(t) denote the state of job j at time t:
(5)smj(t)={0ift<tjlorjhasnotbeenscheduledtoanyagent;t-tjltju-tjlift∈[tjl,tju),andjisbeingprocessedbyanagent1ift≥tjlorjhasbeencompleted;-1ifjhasbeendiscarded.
For example, at time 0s, there is an unemployed agent i without any job coming. The state of the agent i at 0s is
(6)sai(0)=unemployed.At time10s, a job j arrives with feasible time window [12, 30], and it is scheduled to agent i which is due to start at time 12s. Then
(7)sai(t)=unemployed,smj(t)=0fort∈[10,12)sai(t)=busy,smj(t)=t-1230-12fort∈[12,12+dij(12)].
By Assumption 4, there is 12+dij(12)≤30. Suppose dij(12)=8, and job processing ends successfully; then
(8)sai(20)=unemployed,smj(20)=1.
If job processing fails by the time 20s, agent i will start another try to process job j immediately as long as 20+dij(20)≤30 holds. Suppose dij(20)=9; then
(9)sai(t)=busy,smj(t)=t-1230-12fort∈[20,20+dij(20)].
If job processing fails again by the end of the second try (e.g., at time 29s), and the remaining time window of job j (only 1 second is left, since tju=30) is not enough for another try, then job j will be discarded from time 29s:
(10)sai(t)=unemployed,smj(t)=-1fort>29.
In this case, agent i will be available for other incoming jobs from time 29s. As the different agents may be released or start to process a job at different times, it is hard to define a joint action, which is the set of actions for each agent in each decision step of the on-line scheduling process [13]. Moreover, because of the time-dependent state space, the reward of a joint action is difficult to evaluate by a recursive approach as introduced in [30]. Recently, in order to limit the set of state space in the multiagent environment, there is significant progress in extending the Markov Decision Processes (MDP) for optimizing decentralized control [13, 31]. In this paper, as there is no dependence or resource competition among agents, a decentralized MDP is adopted to model the decision process of each agent.


## 4.2. DEC-MDP

For an agenti and its allocated job j with time window [tjl,tju], the corresponding DEC-MDP is defined as a tuple 〈sij,Aij,pij,rij〉t1, where(i)
sij=(sai,smj) is the state set regarding agent i and job j during the whole process period (e.g., from the time when the process is started for the first time, denoted as t1, to the time when agent i is released from job j);(ii)
Aij is the strategy set of agent ai, represented by the starting time that agent i may choose to process job j for the first time. Aij={t∣t∈[tjl,tju],t+dij(t)∈[tjl,tju]};(iii)
pij(t) is a function of time t, which gives the success probability of completing job j by agent i by the time of t+dij(t), when the process or the reprocess starts at time t. According to Assumptions 2 and 3, there is pij(t)=0 if t∉[tjl,tju] or t+dij(t)∉[tjl,tju];(iv)
rij(t) is the reward function as defined in (13).The initial state of a DEC-MDP is
(11)sij(t1)={sai(t1)=busy,smj(t1)=(t1-tjl)(tju-tjl)}.
The absorbing state is
(12)sij(·)={sai(·)=unemployed,smj(·)=1or-1}.
Figure 2 shows the state transition process when agent ai starts to process job j at time t1 for the first time, in which the maximal retry times are K, and K is the smallest number that satisfies tK+1+dij(tK+1)>tju. The reward function is defined as in (13), which is represented by the probability that agent i will successfully complete job j when starting the first process at time t1. Consider
(13)rij(t1)=pij(t1)+∑x=2K(∏y=1x-1(1-pij(ty)))·pij(tx)
s.t. 								(14)tx∈[tjl,tju],tx+1=tx+dij(tx),tx+1∈[tjl,tju],HHHHx=1,2,…,K(15)tK+1+dij(tK+1)>tju;
when starting from time t1, agent i can process job j not more than K times. With (13)–(15), the best time for agent i to begin to process job j is t1*:
(16)t1*=argmax⁡t∈Aij⁡rij(t).
Therefore, during the on-line scheduling, we prefer scheduling the incoming job j to an agent i* with highest success probability:
(17)i*=argmax⁡i∈I⁡rij(t1*).
However, as stated in Section 4, this decision does not take the opportunity loss into account. Agent may lose higher rewards with upcoming jobs during its engagement with the current job. As a result, we introduce a opportunity loss decentralized MDP (OL-DEC-MDP) model in the next section.Figure 2
The state transition process of MDP〈sij,Aij,pij,rij〉t1.


## 5. Opportunity Loss Decentralized MDP (OL-DEC-MDP)

An OL-DEC-MDP model has the same state space, strategy set, and transition probability with a DEC-MDP. However, the reward function of an OL-DEC-MDP should be redefined to take the opportunity loss into account.


### 5.1. Opportunity Loss

As shown in Figure2, the agent may try at most K times before being released from the current job. It will not be available for other upcoming jobs during the period ΔTijz(t1)=[t1,tz+dij(tz)](1≤z≤K) with the probability
(18)pijz={1z=1∏x=1z-1‍(1-pij(tx))2≤z≤K,
where tx+1=tx+dij(tx) and x=1,2,…,z-1. As a result, agent will lose all upcoming jobs during ΔTijz(t1) with probability of pijz. Hence the opportunity loss for agent i to process job j starting from t1 can be defined as
(19)OL(i,j,t1)=max⁡1≤z≤K(pijzmax⁡q∈M(ΔTijz(t1))⁡riq(t1q)).
In the above equation, t1q is the best starting time for agent i to process job q, which is decided by (16). M(ΔTijz(t1)) is the set of all possible jobs that will arrive during period ΔTijz(t1). The opportunity loss of the agent is defined to be the highest possible reward that the agent may lose during the period of engagement with its current job. Considering both the reward and the potential loss in scheduling decision, we now refine the reward function in OL-DEC-MDP as following:
(20)r′(i,j,t1)=rij(t1)-OL(i,j,t1).
As a result, the best starting time of agent i to process job j is t1*:
(21)t1*=argmax⁡t∈Aij⁡r′(i,j,t).
Reward function (21) calculates the maximum reward when schedule agent i to process job j while taking the opportunity loss into account.


### 5.2. Computation of the Reward with Opportunity Loss

For an OL-DEC-MDP〈sij,Aij,pij,rij′〉t1, if job j is allocated to agent i, then agent i should choose a starting time t1 from the time window [tjl,te], while te+dij(te)=tju. If derivation of the reward function (21) exists within interval [tjl,te], the optimal starting time t1* can be decided as following:
(22)∂[rij(t1)-OL(i,j,t1)]∂t1=0(t1∈[tjl,te]).
However, if derivation of reward function (21) does not exist within interval [tjl,te], t1 can be decided with the following heuristics.(1)
Start as early as possible. For example, sett1=tjl if the agent is available earlier than tjl, or set t1 to be the earliest time when agent i becomes available. We denote t1 under this heuristic as ta, ta∈[tjl,te].(2)
Start as late as possible, as long as agent will still have the same number of retrying opportunities (K) with starting as early as possible (e.g., at time ta). With this heuristic, there are tx+1=tx+dij(tx)(x=1,2,…,K-1) and tK+dij(tK)=tju. We denote t1 under this heuristic as t′.(3)
Start at the time with highest success probability to complete jobj within the first try, while still having the maximal retrying opportunities (K). For example, t1 is the time point between [ta,t′] with the highest success probability of the first try. With this heuristic, there is t1=argmax⁡t∈[ta,t′]⁡pij(t). We denote t1 under this heuristic as tm.(4)
Start at the time with the highest success probability to complete the jobj within the first try. With this heuristic, there is t1=argmax⁡t∈[ta,te]⁡pij(t), while te+dij(te)=tju. We denote t1 under this heuristic as tM.As a result, the best starting time t1* of agent i to process job j considering both rewards and opportunity loss can be computed as
(23)t1*=argmax⁡t1∈{ta,t′,tm,tM}⁡[rij(t1)-OL(i,j,t1)].
According to (19), to compute OL(i,j,t1), we should know M(ΔTijK(t1)); for example, the set of all possible jobs that will arrive during time ΔTijK(t1). M(ΔTijK(t1)) can be estimated on-line by the sampling approach, as described in [26, 27], which can forecast the possible events according to the job arriving distribution.


### 5.3. On-Line Scheduling Based on OL-DEC-MDP

The detailed scheduling algorithm is given as following.(
1) Queuing Up the Incoming jobs. When a new job comes, it is queued up in a time-priority queue. A new arrived job with a smaller low bound of feasible time will have higher priority.(
2) Observing the System State Change. Each agent has a job list with length of 1, which indicates its next job to be processed. System state changes when(a)
agent is released from current job and starts to process the assigned job in its job list (the agent’s job list will be empty);(b)
agent fails to complete the current job and begins to make another try (the job in the agent’s job list will be still waiting, which will be rescheduled);(c)
a new job is coming, and there exists at least one agent with empty job list (the incoming job will be assigned to some agent by being pushed into its job list).(
3) Scheduling/Rescheduling When System State Changes. When system state changes, scheduling or rescheduling decision will be made to decide or adjust the best next job as well as the best starting time for each agent. JL denote the current set of next job of all agents before rescheduling.(a)
If∥JL∥<∥I∥, then dequeue ∥I∥-∥JL∥ jobs from queue. Let Jn be the set of these dequeued jobs. Then, JL∪Jn is the job set to be scheduled/rescheduled, as denoted by Js.(b)
Order jobs inJs according to time priority, and clear the job list of all agents.(c)
Schedule each job by order inJs to an agent as following.
(i)
Given jobj, it will be scheduled to the agent i* with highest reward:
(24)i*=argmax⁡i∈IA⁡r′(i,j,t1*).
In the above computation, IA is the set of all agents with empty job list; t1* is decided by (23) with given i and j. For each agent, If it has not been released when job j comes, its earliest available time ta is set to be the ending time of its current process cycle. For example, the scheduling decision is made based on the assumption that all agents will be released by the end of its current process cycle. If the assumption is violated according to the observation, it is thought to be a system state change, and rescheduling will be made as described in step 3.(ii)
Push jobj into job list of i*.(
4) Job Processing. when available (being released from the current job), agent will begin to process the job in its job list at time t1*, and its job list will be cleared. By Assumption 2, agents will try many times to complete assigned jobs before success or time window of the job expires.


### 5.4. Properties and Proofs

Property 1.
The time complexity to compute the best starting timet1* for an agent i to process job j according to (21) is O(tju-tjl).Proof.
As shown in Figure2, there is one state for an OL-DEC-MDP in t1, and two possible states in tk, where k=2,3,…,K,K+1. Hence, the maximum number of possible states during the job process is 2K+1. As a result, the time complexity to calculate the expectation value of completing current job is O(2K+1). On the other hand, the time complexity to calculate the maximal possible opportunity loss is O(|M(ΔTijK)|·(2K+1)). Therefore, the time complexity to calculate the reward for a given agent i, job j, and start time t1 is O((|M(ΔTijK(t1))|+1)·(2K+1)). As |M(ΔTijK(t1))| and K are constant for a given instance, we can set a constant C=(|M(ΔTijK(t1))|+1)·(2K+1). Therefore, the time complexity to compute t1* in (21) is
(25)O(∫tjltjuC)=O(C·(tju-tjl))=O(tju-tjl).Property 2.
The average time for agenti on processing job j is ∑z=1Kpijz·(tz+dij(tz)-t1), while tz+1=tz+dij(tz) and z=1,2,…,K-1.Proof.
As shown in (17), given the starting time of the first processing t1, the probability is pijz for the agent i to spend ΔTijz(t1)=[t1,tz+dij(tz)] on processing job j, where tz+1=tz+dij(tz) and z=1,2,…,K-1. Thus, the average time for agent i to spend on job j is
(26)∑z=1Kpijz·(tz+dij(tz)-t1).


## 5.1. Opportunity Loss

As shown in Figure2, the agent may try at most K times before being released from the current job. It will not be available for other upcoming jobs during the period ΔTijz(t1)=[t1,tz+dij(tz)](1≤z≤K) with the probability
(18)pijz={1z=1∏x=1z-1‍(1-pij(tx))2≤z≤K,
where tx+1=tx+dij(tx) and x=1,2,…,z-1. As a result, agent will lose all upcoming jobs during ΔTijz(t1) with probability of pijz. Hence the opportunity loss for agent i to process job j starting from t1 can be defined as
(19)OL(i,j,t1)=max⁡1≤z≤K(pijzmax⁡q∈M(ΔTijz(t1))⁡riq(t1q)).
In the above equation, t1q is the best starting time for agent i to process job q, which is decided by (16). M(ΔTijz(t1)) is the set of all possible jobs that will arrive during period ΔTijz(t1). The opportunity loss of the agent is defined to be the highest possible reward that the agent may lose during the period of engagement with its current job. Considering both the reward and the potential loss in scheduling decision, we now refine the reward function in OL-DEC-MDP as following:
(20)r′(i,j,t1)=rij(t1)-OL(i,j,t1).
As a result, the best starting time of agent i to process job j is t1*:
(21)t1*=argmax⁡t∈Aij⁡r′(i,j,t).
Reward function (21) calculates the maximum reward when schedule agent i to process job j while taking the opportunity loss into account.


## 5.2. Computation of the Reward with Opportunity Loss

For an OL-DEC-MDP〈sij,Aij,pij,rij′〉t1, if job j is allocated to agent i, then agent i should choose a starting time t1 from the time window [tjl,te], while te+dij(te)=tju. If derivation of the reward function (21) exists within interval [tjl,te], the optimal starting time t1* can be decided as following:
(22)∂[rij(t1)-OL(i,j,t1)]∂t1=0(t1∈[tjl,te]).
However, if derivation of reward function (21) does not exist within interval [tjl,te], t1 can be decided with the following heuristics.(1)
Start as early as possible. For example, sett1=tjl if the agent is available earlier than tjl, or set t1 to be the earliest time when agent i becomes available. We denote t1 under this heuristic as ta, ta∈[tjl,te].(2)
Start as late as possible, as long as agent will still have the same number of retrying opportunities (K) with starting as early as possible (e.g., at time ta). With this heuristic, there are tx+1=tx+dij(tx)(x=1,2,…,K-1) and tK+dij(tK)=tju. We denote t1 under this heuristic as t′.(3)
Start at the time with highest success probability to complete jobj within the first try, while still having the maximal retrying opportunities (K). For example, t1 is the time point between [ta,t′] with the highest success probability of the first try. With this heuristic, there is t1=argmax⁡t∈[ta,t′]⁡pij(t). We denote t1 under this heuristic as tm.(4)
Start at the time with the highest success probability to complete the jobj within the first try. With this heuristic, there is t1=argmax⁡t∈[ta,te]⁡pij(t), while te+dij(te)=tju. We denote t1 under this heuristic as tM.As a result, the best starting time t1* of agent i to process job j considering both rewards and opportunity loss can be computed as
(23)t1*=argmax⁡t1∈{ta,t′,tm,tM}⁡[rij(t1)-OL(i,j,t1)].
According to (19), to compute OL(i,j,t1), we should know M(ΔTijK(t1)); for example, the set of all possible jobs that will arrive during time ΔTijK(t1). M(ΔTijK(t1)) can be estimated on-line by the sampling approach, as described in [26, 27], which can forecast the possible events according to the job arriving distribution.


## 5.3. On-Line Scheduling Based on OL-DEC-MDP

The detailed scheduling algorithm is given as following.(
1) Queuing Up the Incoming jobs. When a new job comes, it is queued up in a time-priority queue. A new arrived job with a smaller low bound of feasible time will have higher priority.(
2) Observing the System State Change. Each agent has a job list with length of 1, which indicates its next job to be processed. System state changes when(a)
agent is released from current job and starts to process the assigned job in its job list (the agent’s job list will be empty);(b)
agent fails to complete the current job and begins to make another try (the job in the agent’s job list will be still waiting, which will be rescheduled);(c)
a new job is coming, and there exists at least one agent with empty job list (the incoming job will be assigned to some agent by being pushed into its job list).(
3) Scheduling/Rescheduling When System State Changes. When system state changes, scheduling or rescheduling decision will be made to decide or adjust the best next job as well as the best starting time for each agent. JL denote the current set of next job of all agents before rescheduling.(a)
If∥JL∥<∥I∥, then dequeue ∥I∥-∥JL∥ jobs from queue. Let Jn be the set of these dequeued jobs. Then, JL∪Jn is the job set to be scheduled/rescheduled, as denoted by Js.(b)
Order jobs inJs according to time priority, and clear the job list of all agents.(c)
Schedule each job by order inJs to an agent as following.
(i)
Given jobj, it will be scheduled to the agent i* with highest reward:
(24)i*=argmax⁡i∈IA⁡r′(i,j,t1*).
In the above computation, IA is the set of all agents with empty job list; t1* is decided by (23) with given i and j. For each agent, If it has not been released when job j comes, its earliest available time ta is set to be the ending time of its current process cycle. For example, the scheduling decision is made based on the assumption that all agents will be released by the end of its current process cycle. If the assumption is violated according to the observation, it is thought to be a system state change, and rescheduling will be made as described in step 3.(ii)
Push jobj into job list of i*.(
4) Job Processing. when available (being released from the current job), agent will begin to process the job in its job list at time t1*, and its job list will be cleared. By Assumption 2, agents will try many times to complete assigned jobs before success or time window of the job expires.


## 5.4. Properties and Proofs

Property 1.
The time complexity to compute the best starting timet1* for an agent i to process job j according to (21) is O(tju-tjl).Proof.
As shown in Figure2, there is one state for an OL-DEC-MDP in t1, and two possible states in tk, where k=2,3,…,K,K+1. Hence, the maximum number of possible states during the job process is 2K+1. As a result, the time complexity to calculate the expectation value of completing current job is O(2K+1). On the other hand, the time complexity to calculate the maximal possible opportunity loss is O(|M(ΔTijK)|·(2K+1)). Therefore, the time complexity to calculate the reward for a given agent i, job j, and start time t1 is O((|M(ΔTijK(t1))|+1)·(2K+1)). As |M(ΔTijK(t1))| and K are constant for a given instance, we can set a constant C=(|M(ΔTijK(t1))|+1)·(2K+1). Therefore, the time complexity to compute t1* in (21) is
(25)O(∫tjltjuC)=O(C·(tju-tjl))=O(tju-tjl).Property 2.
The average time for agenti on processing job j is ∑z=1Kpijz·(tz+dij(tz)-t1), while tz+1=tz+dij(tz) and z=1,2,…,K-1.Proof.
As shown in (17), given the starting time of the first processing t1, the probability is pijz for the agent i to spend ΔTijz(t1)=[t1,tz+dij(tz)] on processing job j, where tz+1=tz+dij(tz) and z=1,2,…,K-1. Thus, the average time for agent i to spend on job j is
(26)∑z=1Kpijz·(tz+dij(tz)-t1).


## 6. Evaluations

### 6.1. Evaluation Setting

In the evaluation, a scenario of antiship missile defence by SAM systems is studied, which is introduced in [2].Suppose there are four ship-borne SAM systems that can be scheduled to intercept the incoming antiship missiles, and each SAM system is capable of working independently and intercepting antiship missile coming from any direction (the modern ship-borne vertical launching missile system matches these features and is becoming very popular). The feasible interception time window of each incoming antiship missilej is set to be [tjl,tj+43.29s], in which tjl is the time when the antiship missile is detected. The length of interception time window is decided by the detection capability of SAM system as well as the speed of the antiship missile. As a result, based on Section 5, if a SAM system is available when the missile is detected, there are ta=tjl, tm=tM=ta+15.9s, and t′=ta+20.47s based on scenario in [2]. The killing probability associated with the starting time of each interception pij(t) is shown in Figure 3, which is approximated by a cubic multinomial. The duration function is defined as dij(t)=rij(t)/(νsam+νm), where rij(t) is the range at time t between the SAM missile and the antiship missile; νsam and νm are the velocities of the SAM missile and the antiship missile.Figure 3
killing probability function.For the incoming antiship missile, the total number is set to bem(m∈{10,12,14,16,18}), and its arrival follows uniform distribution during a time span [0,T](T∈{20,30,40,50,60,70,80,90}). To compute the opportunity loss as described in Section 5, a sampling method [26, 27] is implemented. Simulations are run under each combination of m and T to compare the scheduling result under different circumstances.


### 6.2. Quality of Scheduling

In the air-defence scenario, fail to intercept even one time may result in severe damage. Hence the quality of scheduling is measured by the probability of successfully interception of all incoming antiship missiles, which is denoted asP-interception. As shown in Figures 4 and 5, both DEC-MDP and OL-DEC-MDP based scheduling approaches illustrate that less intensive the attack comes (fewer antiship missiles with fixed time span or longer time span with fixed incoming antiship missiles), higher theP-interception will be. The reason is that if there are fewer antiship missiles per time unit, there should be more available SAM systems that can be scheduled, hence the overall interception performance will be improved.Figure 4
Probability of overall interception of DEC-MDP based approach.Figure 5
Probability of overall interception of OL-DEC-MDP based approach.However, as shown in Figure6, the OL-DEC-MDP based scheduling approach always has a higher probability of overall interception compared with DEC-MDP model. It can be observed that, for the same time span, the improvement of OL-DEC-MDP becomes more significant as the number of incoming missiles (m) increases. For example, there is performance improvement under more intensive attack environment. On the other hand, the overall shape of the improvement along the time span (for the fixed number of incoming antiship missiles, longer time span means less intensive attack) tends out to be a “cap.” For example, the improvement rises sharply with the time span increasing at first and then comes down after reaching some peaks. The reason is that when the time span is small at first, which means that the antiship missiles are coming very intensively, it is very hard to improve the interception performance by OL-DEC-MDP since the SAM system reaches its saturation point under very intensive attack. The decision space left for each SAM system to decide the best starting time of the interception is quite small; hence OL-DEC-MDP has similar performance with DEC-MDP. However, when the intensity falls below the saturation point of the SAM system, the improvement brought by OL-DEC-MDP becomes gradually significant as opportunity loss is taken into account in on-line scheduling to achieve better overall performance. As the attack intensity continues to lower down with the increase of time span, the whole system has more than enough capability (available SAM systems) to intercept the incoming missiles; hence the improvement brought by OL-DEC-MDP becomes less significant.Figure 6
The increased probability of interception by OL-DEC-MDP compared with DEC-MDP.Figure7 shows the best starting time of interception used in OL-DEC-MDP obtained by heuristic strategy introduced in Section 5. Y-axis is the time indicating how long after an antiship missile is detected the first interception is launched. It can be observed that when the antiship missiles arrive intensively (which means smaller time span with fixed total incoming missiles), OL-DEC-MDP prefers to postpone the first interception launch. Study on the simulation data shows that the optimal starting time for interception under this case is near the time tm, which means that the strategy to achieve the highest killing probability against the antiship missile by one shot is the superior strategy. This observation can be inferred from Property 2 that the superior strategy in this case is to release the SAM system as early as possible to treat the next incoming antiship missile. On the other hand, when the attack is less intensive (which means longer time span with fixed total incoming missiles), OL-DEC-MDP prefers to start the interception earlier as to leave more feasible time for retrying in case of interception fail.Figure 7
The average starting time of interception (t1*) computed by OL-DEC-MDP.


## 6.1. Evaluation Setting

In the evaluation, a scenario of antiship missile defence by SAM systems is studied, which is introduced in [2].Suppose there are four ship-borne SAM systems that can be scheduled to intercept the incoming antiship missiles, and each SAM system is capable of working independently and intercepting antiship missile coming from any direction (the modern ship-borne vertical launching missile system matches these features and is becoming very popular). The feasible interception time window of each incoming antiship missilej is set to be [tjl,tj+43.29s], in which tjl is the time when the antiship missile is detected. The length of interception time window is decided by the detection capability of SAM system as well as the speed of the antiship missile. As a result, based on Section 5, if a SAM system is available when the missile is detected, there are ta=tjl, tm=tM=ta+15.9s, and t′=ta+20.47s based on scenario in [2]. The killing probability associated with the starting time of each interception pij(t) is shown in Figure 3, which is approximated by a cubic multinomial. The duration function is defined as dij(t)=rij(t)/(νsam+νm), where rij(t) is the range at time t between the SAM missile and the antiship missile; νsam and νm are the velocities of the SAM missile and the antiship missile.Figure 3
killing probability function.For the incoming antiship missile, the total number is set to bem(m∈{10,12,14,16,18}), and its arrival follows uniform distribution during a time span [0,T](T∈{20,30,40,50,60,70,80,90}). To compute the opportunity loss as described in Section 5, a sampling method [26, 27] is implemented. Simulations are run under each combination of m and T to compare the scheduling result under different circumstances.


## 6.2. Quality of Scheduling

In the air-defence scenario, fail to intercept even one time may result in severe damage. Hence the quality of scheduling is measured by the probability of successfully interception of all incoming antiship missiles, which is denoted asP-interception. As shown in Figures 4 and 5, both DEC-MDP and OL-DEC-MDP based scheduling approaches illustrate that less intensive the attack comes (fewer antiship missiles with fixed time span or longer time span with fixed incoming antiship missiles), higher theP-interception will be. The reason is that if there are fewer antiship missiles per time unit, there should be more available SAM systems that can be scheduled, hence the overall interception performance will be improved.Figure 4
Probability of overall interception of DEC-MDP based approach.Figure 5
Probability of overall interception of OL-DEC-MDP based approach.However, as shown in Figure6, the OL-DEC-MDP based scheduling approach always has a higher probability of overall interception compared with DEC-MDP model. It can be observed that, for the same time span, the improvement of OL-DEC-MDP becomes more significant as the number of incoming missiles (m) increases. For example, there is performance improvement under more intensive attack environment. On the other hand, the overall shape of the improvement along the time span (for the fixed number of incoming antiship missiles, longer time span means less intensive attack) tends out to be a “cap.” For example, the improvement rises sharply with the time span increasing at first and then comes down after reaching some peaks. The reason is that when the time span is small at first, which means that the antiship missiles are coming very intensively, it is very hard to improve the interception performance by OL-DEC-MDP since the SAM system reaches its saturation point under very intensive attack. The decision space left for each SAM system to decide the best starting time of the interception is quite small; hence OL-DEC-MDP has similar performance with DEC-MDP. However, when the intensity falls below the saturation point of the SAM system, the improvement brought by OL-DEC-MDP becomes gradually significant as opportunity loss is taken into account in on-line scheduling to achieve better overall performance. As the attack intensity continues to lower down with the increase of time span, the whole system has more than enough capability (available SAM systems) to intercept the incoming missiles; hence the improvement brought by OL-DEC-MDP becomes less significant.Figure 6
The increased probability of interception by OL-DEC-MDP compared with DEC-MDP.Figure7 shows the best starting time of interception used in OL-DEC-MDP obtained by heuristic strategy introduced in Section 5. Y-axis is the time indicating how long after an antiship missile is detected the first interception is launched. It can be observed that when the antiship missiles arrive intensively (which means smaller time span with fixed total incoming missiles), OL-DEC-MDP prefers to postpone the first interception launch. Study on the simulation data shows that the optimal starting time for interception under this case is near the time tm, which means that the strategy to achieve the highest killing probability against the antiship missile by one shot is the superior strategy. This observation can be inferred from Property 2 that the superior strategy in this case is to release the SAM system as early as possible to treat the next incoming antiship missile. On the other hand, when the attack is less intensive (which means longer time span with fixed total incoming missiles), OL-DEC-MDP prefers to start the interception earlier as to leave more feasible time for retrying in case of interception fail.Figure 7
The average starting time of interception (t1*) computed by OL-DEC-MDP.


## 7. Conclusions

This paper proposes an OL-DEC-MDP model for on-line multiagent stochastic scheduling, which considers the starting time-dependent probability of success and processing duration. The probability of completing the assigned job by an agent would be higher when the process is started earlier, but the opportunity loss could be also high due to the longer engaging duration. As a result, OL-DEC-MDP model introduces the reward function considering the opportunity loss and schedules the incoming job to the agent with the highest reward. In order to measure the opportunity loss, OL-DEC-MDP model uses sampling method to predict the upcoming jobs and introduces heuristic strategies to compute the best starting time of an agent against an incoming job. The simulation experiments show that the OL-DEC-MDP model will improve the overall scheduling performance compared with models without considering opportunity loss, such as DEC-MDP. The overall trend of performance improvement is studied under different scenarios, which shows that the performance improvement is most significant if the jobs are coming intensively but within the saturation point of the multiagent system.For the future research, we should extend the model to more general cases.(1)
Dependency Between Agents. In some cases, agents may interfere with other’s operation. For example, if soft weapons such as chaff rocket are used during the interception, there may be mutual interference between different air defence weapons: firing a chaff rocket may prevent the missile guiding radar of the SAM system from working normally. In future work, the mutual influence between agents will be considered in constructing available strategy set and computing action reward.(2)
Partial Observation. For some real-world problem, the result of the action can only be partially observed. For example, the result of interception by a SAM system may not be totally observed by other agents due to the limitation of sensing capability. Hence the reward and the opportunity loss should be reevaluated, and POMDP (partial observation MDP) based approach could be a good candidate.(3)
On-line Learning. The sampling approach implemented in OL-DEC-MDP is based on the prior knowledge of the arrival distribution of the incoming jobs. If the prior knowledge of the arrival distribution does not exist, the on-line learning method could be used to learn and predict the future incoming jobs.



---

*Source: 753487-2014-07-22.xml*