## 3 Problem Description
### Entity Definitions and Constraints  
In the edge workflow computing platform, there are three key entities: workflow, sub-task, and edge server. This subsection provides detailed definitions for these three entities and specifies the constraints during the scheduling process.  
A workflow consists of multiple sub-tasks, where each sub-task has its predecessors and successors. The following symbols are used to describe the workflow model:  
* \(Workflows\): a collection of workflows submitted by users, containing a total of N workflows. \(Workflow=\{w^{1},w^{2},\ldots,w^{N}\}\);
* \(w^{i}\): a workflow is represented as a DAG and using adjacency matrix to represent DAG;
* \(st^{i}_{j}\): a sub-task in \(w^{i}\);
* \(x^{i}_{j,k}\): The elements in the matrix corresponding to \(w^{i}\). Specifically, \(x^{i}_{j,k}=1\) if \(st^{i}_{j}\) is the predecessor of \(st^{i}_{k}\), and \(x^{i}_{j,k}=0\) for all other cases;
* \(i\): the index of workflow.  
The workflow model is responsible for maintaining the constraints between sub-tasks, while each sub-task has its own attributes. Each sub-task can be represented as a tuple of \((C^{i}_{j},E^{i}_{j},\ AT^{i}_{j},D^{i}_{j},P^{i}_{j})\).  
* \(C^{i}_{j}\): the Service corresponding to \(st^{i}_{j}\);
* \(E^{i}_{j}\): the execution time of \(st^{i}_{j}\);
* \(AT^{i}_{j}\): the arrival time of the sub-task;
* \(D^{i}_{j}\): The resource requirements of \(st^{i}_{j}\). \(D^{i}_{j}=\{r_{1},r_{2},\ldots,r_{d}\}\), where \(d\) represents the number of resources. Each resource requirement lies in the range \([0,1]\);
* \(P^{i}_{j}\): the execution priority of \(st^{i}_{j}\);
* \(j\): the index of sub-task;
* \(SAT^{i}_{j}\): The start time of \(st^{i}_{j}\). This parameter is obtained by scheduling result.  
Figure 2: A schematic diagram of the workflow scheduling.  
The parameters of the edge server constrain the scheduling of sub-tasks. The definitions of the parameters relevant to the problem are as follows:  
* \(R_{edge}\): the resource for edge server. \(R_{edge}=\{R_{1},R_{2},\ldots,R_{d}\}\);
* \(d\): the index of Resource;
* \(t\): the timestamp for edge server. During scheduling, the parameters are subject to the following constraints:
* Time constraint: \(SAT_{j}^{i}\geq Max\{SAT_{k}^{i}+E_{k}^{i}\}\), \(\forall x_{k,j}^{i}=1\);
* Resource constraint: \(R_{edge}\geq D_{j}^{i}\), when \(st_{j}^{i}\) can be scheduled. For constraint (1), the actual start time of a sub-task, denoted as \(SAT_{j}^{i}\), must satisfy the condition \(SAT_{j}^{i}\geq Max\{SAT_{k}^{i}+E_{k}^{i}\}\). Here, \(\{SAT_{k}^{i}+E_{k}^{i}\}\) represents the set of completion times of all predecessor sub-tasks. This constraint ensures that \(st_{j}^{i}\) cannot be executed before its predecessor sub-tasks have been completed.  
For constraint (2), before adding a sub-task to the Sub-Task queue, it is crucial to verify that the computational resources available in the edge server can adequately meet the computational resource requirements for processing that Sub-Task.  
In addition, the following constraints exist during scheduling:  
* There will be no relationship between sub-tasks in different workflows;
* The time taken to transmit sub-tasks to the Sub-Task Queue and assemble the returned results is disregarded. The actual transmission time from the scheduling center to the edge servers can be determined through testing;
* Once a Service is processing a sub-task during runtime, it cannot be preempted or suspended;
* Upon completing a task, the Service can promptly release the allocated resources. Only the resources necessary for the Service to run are reserved.