
In this work, we report on a perfusion-based co-culture system that could be used for bone tissue engineering applications. The model system is created using a combination of Primary Human Umbilical Vein Endothelial Cells (HUVECs) and osteoblast-like Saos-2 cells encapsulated within a Gelatin Methacrylate (GelMA)-collagen hydrogel blend contained within 3D printed, perfusable constructs. The constructs contain dual channels, within a custom-built bioreactor, that were perfused with osteogenic media for up to two weeks in order to induce mineral deposition. Mineral deposition in constructs containing only HUVECs, only Saos-2 cells, or a combination thereof was quantified by microCT to determine if the combination of endothelial cells and bone-like cells increased mineral deposition. Histological and fluorescent staining was used to verify mineral deposition and cellular function both along and between the perfused channels. While there was not a quantifiable difference in the amount of mineral deposited in Saos-2 only versus Saos-2 plus HUVEC samples, the location of the deposited mineral differed dramatically between the groups and indicated that the addition of HUVECs within the GelMA matrix allowed Saos-2 cells, in diffusion limited regions of the construct, to deposit bone mineral. This work serves as a model on how to create perfusable bone tissue engineering constructs using a combination of 3D printing and cellular co-cultures.
Citation: Stephen W. Sawyer, Kairui Zhang, Jason A. Horton, Pranav Soman. Perfusion-based co-culture model system for bone tissue engineering[J]. AIMS Bioengineering, 2020, 7(2): 91-105. doi: 10.3934/bioeng.2020009
[1] | Hengxiao Qi, Muhammad Yussouf, Sajid Mehmood, Yu-Ming Chu, Ghulam Farid . Fractional integral versions of Hermite-Hadamard type inequality for generalized exponentially convexity. AIMS Mathematics, 2020, 5(6): 6030-6042. doi: 10.3934/math.2020386 |
[2] | Maryam Saddiqa, Saleem Ullah, Ferdous M. O. Tawfiq, Jong-Suk Ro, Ghulam Farid, Saira Zainab . k-Fractional inequalities associated with a generalized convexity. AIMS Mathematics, 2023, 8(12): 28540-28557. doi: 10.3934/math.20231460 |
[3] | Yonghong Liu, Ghulam Farid, Dina Abuzaid, Hafsa Yasmeen . On boundedness of fractional integral operators via several kinds of convex functions. AIMS Mathematics, 2022, 7(10): 19167-19179. doi: 10.3934/math.20221052 |
[4] | Ghulam Farid, Maja Andrić, Maryam Saddiqa, Josip Pečarić, Chahn Yong Jung . Refinement and corrigendum of bounds of fractional integral operators containing Mittag-Leffler functions. AIMS Mathematics, 2020, 5(6): 7332-7349. doi: 10.3934/math.2020469 |
[5] | Ye Yue, Ghulam Farid, Ayșe Kübra Demirel, Waqas Nazeer, Yinghui Zhao . Hadamard and Fejér-Hadamard inequalities for generalized k-fractional integrals involving further extension of Mittag-Leffler function. AIMS Mathematics, 2022, 7(1): 681-703. doi: 10.3934/math.2022043 |
[6] | Ghulam Farid, Saira Bano Akbar, Shafiq Ur Rehman, Josip Pečarić . Boundedness of fractional integral operators containing Mittag-Leffler functions via (s,m)-convexity. AIMS Mathematics, 2020, 5(2): 966-978. doi: 10.3934/math.2020067 |
[7] | Xiuzhi Yang, G. Farid, Waqas Nazeer, Muhammad Yussouf, Yu-Ming Chu, Chunfa Dong . Fractional generalized Hadamard and Fejér-Hadamard inequalities for m-convex functions. AIMS Mathematics, 2020, 5(6): 6325-6340. doi: 10.3934/math.2020407 |
[8] | Yu-Pei Lv, Ghulam Farid, Hafsa Yasmeen, Waqas Nazeer, Chahn Yong Jung . Generalization of some fractional versions of Hadamard inequalities via exponentially (α,h−m)-convex functions. AIMS Mathematics, 2021, 6(8): 8978-8999. doi: 10.3934/math.2021521 |
[9] | Wenfeng He, Ghulam Farid, Kahkashan Mahreen, Moquddsa Zahra, Nana Chen . On an integral and consequent fractional integral operators via generalized convexity. AIMS Mathematics, 2020, 5(6): 7632-7648. doi: 10.3934/math.2020488 |
[10] | Yue Wang, Ghulam Farid, Babar Khan Bangash, Weiwei Wang . Generalized inequalities for integral operators via several kinds of convex functions. AIMS Mathematics, 2020, 5(5): 4624-4643. doi: 10.3934/math.2020297 |
In this work, we report on a perfusion-based co-culture system that could be used for bone tissue engineering applications. The model system is created using a combination of Primary Human Umbilical Vein Endothelial Cells (HUVECs) and osteoblast-like Saos-2 cells encapsulated within a Gelatin Methacrylate (GelMA)-collagen hydrogel blend contained within 3D printed, perfusable constructs. The constructs contain dual channels, within a custom-built bioreactor, that were perfused with osteogenic media for up to two weeks in order to induce mineral deposition. Mineral deposition in constructs containing only HUVECs, only Saos-2 cells, or a combination thereof was quantified by microCT to determine if the combination of endothelial cells and bone-like cells increased mineral deposition. Histological and fluorescent staining was used to verify mineral deposition and cellular function both along and between the perfused channels. While there was not a quantifiable difference in the amount of mineral deposited in Saos-2 only versus Saos-2 plus HUVEC samples, the location of the deposited mineral differed dramatically between the groups and indicated that the addition of HUVECs within the GelMA matrix allowed Saos-2 cells, in diffusion limited regions of the construct, to deposit bone mineral. This work serves as a model on how to create perfusable bone tissue engineering constructs using a combination of 3D printing and cellular co-cultures.
Scheduling is one of the most widely researched areas of operational research, and its primary objective is to optimize one or more performance indicators by allocating scarce resources to productive operations in a given period [1,2,3]. From the perspective of machine environment, there are five environments in literature, namely, single machine shop, parallel machine shop, flow shop, job shop and open shop. Different from other machine environments, open shop has no restriction on the processing route of each job during the production process. In this paper, the open shop scheduling problem is considered.
Since open shop scheduling problem (OSSP) was raised, it has received considerable attention over the last four decades and has been applied to different fields including agriculture, hospitals, transport, and manufacturing industry [4,5]. In classic OSSP, a set of n jobs are to be processed by a set of m machines, with all jobs and machines available at the beginning. Each job contains a set of m operations, and each operation should only be processed on one machine. At any time, a job can be processed by at most one machine, and any machine can process only one job. Besides, setup times are negligible and preemption of operations is not allowed. The problem is to find an optimal schedule for the operations that minimizes the makespan. Due to unconstrained operational processing order within a job, OSSP can be perceived as a generalization of the job shop scheduling problem (JSSP) [6]. Compared with JSSP, the solution space of OSSP (represented by the sequence of operations on machines and operations within jobs) is too large to find the optimal solution.
With the standard scheduling notation [7], the simplest OSSP can be described as Om‖Cmax, where m is the number of machines. For problem O2‖Cmax, a priority rule named Longest Alternate Processing Time first (LAPT) was developed to find the optimal scheduling in polynomial time [8]. Besides, an NP-hardness proof for O3‖Cmax was provided by [4]. As the job is available only after its arrival in practice, the study of open shop scheduling problem with release dates is closer to the practical production [9], but it also makes it harder to arrange resources and tasks properly. Lawler, Lenstra, Kan, et al. [10] pointed out that the problem O2|rj|Cmax is strongly NP-hard. For problem O3|rj|Cmax, Chen, Huang and Tang [11] demonstrated that the worst-case performance ratio of greedy algorithm is 5/3. For small scale problems, Branch & Bound algorithm is the best choice [12,13]. For large scale problems, heuristic or metaheuristic algorithms may be the most effective way to obtain approximate optimal solutions. For example, hybrid genetic algorithms have been employed to solve large scale OSSP [14,15] while hybrid genetic algorithm and particle swarm optimization are introduced in integrated process planning and scheduling [16,17]. In addition, artificial bee colony algorithm is used in welding shop scheduling problem [18,19]. However, in terms of the scheduling problem with release dates, metaheuristic algorithms have great difficulty in modeling. Besides, metaheuristic algorithms may take much more time to obtain suboptimal solutions, making it difficult to meet the performance requirements of real-time scheduling decision. As the scale of the problem increases, the metaheuristic algorithms will fail fundamentally due to their inability to evaluate the performance of the solution in a timely and effective manner. In comparison, the heuristic algorithms are more promising as they achieve better trade-offs between computation time and solution quality. However, it remains a challenge to design appropriate heuristic algorithms for different problems.
In order to model and optimize large-scale complex dynamic systems in the real world, since the 1990s, complex network theory has been developed in the field of statistical physics [20,21]. Complex network consists of numerous nodes and edges, which respectively represent elements of the system and the correlations between the elements, providing a new way to deal with large-scale dynamic scheduling problem. The complex network theory holds that the complexity of a network is mainly caused by the complex association between a large number of nodes, rather than by the complex dynamic behavior of the individual nodes. Similarly, complex relationships among jobs, resources and operations determine the performance of the entire scheduling system. Therefore, complex network model may be an effective tool for solving large-scale dynamic open shop scheduling problem.
In recent years, complex network theory has already found its way into the scheduling problems. To the best of our knowledge, the first complex network model for open shop scheduling problem was built by [22,23]. The open shop scheduling problem was transformed into reasonably arranging the node traversal order, with the goal of traversing all nodes in the network as quickly as possible. Moreover, three scheduling rules based on complex network characteristics, namely Degree rule, Cluster rule and Redundancy rule were proposed. This research is very instructive, but has obvious limitations. Specifically, these proposed rules only apply to non-uniform network topologies, which are obtained by setting jobs with different numbers of operations. Therefore, for classical production scheduling problem, the performance of these algorithms will be greatly compromised due to their inability to identify valid initial scheduling nodes. Besides, a multi-task directed-weighted network was established by setting production factors involved in the job shop system as nodes, possible process routes and logistics paths between nodes as edges[24]. In conclusion, the production scheduling research based on complex network is still in its infancy. In this paper, both the network structural features and time attributes are considered to construct effective heuristic rules.
The rest of the paper is organized as follows: section 2 describes the framework of general scheduling object; Section 3 develops a complex scheduling network model for OSSP; Section 4 proposes several complex network based heuristic rules, and a novel complex network based dynamic rule selection approach. In section 5, two groups of experiments are conducted. Finally, conclusions and future works are summarized.
The general scheduling object involves many elements that have specific meanings in different application scenarios. In many cases, the relationship between these elements is quite complicated. In order to solve the scheduling problem in as many application scenarios as possible, a framework of general scheduling object is established based on the induction of the basic elements of the object, which can cover various types of scheduling problems, including OSSP.
As shown in Figure 1, a general scheduling object (GSO) can be defined by a formula:
GSO=[R,J,O,MJO,MOR,MOO,MRR] | (1) |
where R, J, O, MJO, MOR, MOO and MRR denotes resource set, job set, operation set, job-operation mapping, operation-resource mapping, operation-operation mapping and resource-resource mapping, respectively.
Resource set R can be simply defined as (2), which is made up of m resources.
R={r1,r2,...,rm} | (2) |
Each element in the job set J represents a job, which can contain some attributes, such as priority level, release date and due date. J with size n can be represented as (3). The release date RD of tasks can be represented as (4), and the due date DD of tasks can be described as (5).
J={J1,J2,...,Jn} | (3) |
RD={rd1,rd2,...,rdn} | (4) |
DD={dd1,dd2,...,ddn} | (5) |
Job-operation mapping MJO can be expressed as (6). Each job Ji is composed of ni operations to be processed, and Oki denotes the kth operation of job Ji (k = 1, 2, …, ni), which has the processing time tki. For flow shop and job shop, each job Ji is an ordered set.
Ji={O1i,O2i,...,Onii} | (6) |
Operation-resource mapping MOR can be presented as (7), of which the number of resources is sizeki given that the processing of operation Oki usually requires the cooperation of several resources.
OR(Oki)=fixki | (7) |
In order to approach the real-world problem, the setup time between any two operations should not be ignored, and the length of the setup time on the machine depends on the similarity between the two consecutive operations. The higher the similarity, the shorter the setup time. Operation-operation mapping MOO can be expressed as (8), where S denotes the total number of operations, and can be calculated by (9). Any element OOi, j represents the switching time from ith to jth operation.
MOO=[OOi,j]S∗S | (8) |
S=∑ni=1ni | (9) |
The occurrence of resources in parallel is common in the actual systems. Therefore, it is important to figure out if the resources can perform the same functions. Resource-resource mapping MRR can be formulated by a matrix, in which any element RRi, j represents the substitution efficiency of the corresponding two resources, specifically, RRi, j equals the ratio of the time spent on the ith resource to the jth resource.
MRR=[RRi,j]m∗m | (10) |
Most scheduling problems can be described under the framework of GSO, including OSSP. Om‖Cmax can be obtained from the GSO under these constraints: (1) the resource set R is made up of m unrelated resources, that is, no resource can be replaced by any other resource, thus, MRR is an unit matrix; (2) the job set J is made up of n jobs, and the release date RD of any task is set to zero, regardless of the due date DD; (3) each job Ji is composed of m operations to be processed, and its kth operation Oki needs to be processed for tki unit time on the kth resource. Thus, fixki={k} and sizeki=1 for all i and k; (4) MOR is consistent with the above expression; (5) all setup times are assumed to be zero, so MOO is zero matrix. When the release date of the ith job rdi is set as ri, the problem is converted into Om|rj|Cmax.
Under the framework of GSO, most scheduling problems can be easily transformed into complex scheduling network models. The complex scheduling network G can be represented by a triad G = (V, L, UR), where V denotes the set of nodes, L denotes the set of edges, and UR denotes the set of network update rules.
As shown in Figure 2, in the complex scheduling network model for OSSP, a node Oki represents the kth operation of the ith job, assigned two variables respectively representing the required processing time tki, and the release date rdi. Every edge represents mutually exclusive timing constraint between two operations. Specifically, since any two operations of the same job can't be processed simultaneously, an edge will link any pair of nodes of the same job (Oki and Oli). Similarly, since a resource can only be used for processing one operation at a time, an edge will link any pair of nodes that require the same resource (Oki and Okj). Then the problem can be formulated as: how to arrange the node traversal order so that all the nodes in the network can be traversed as quickly as possible, on condition that each node has a traversal time, and only the disconnected nodes can be traversed simultaneously.
As is known to us all, the network update rules UR can be divided into two parts. One part is growth rule (GR), and the other part is cutting rule (CR). GR controls the increase of network nodes and edges caused by the dynamic arrival of jobs, and CR determines the disappearance of network nodes and edges with the completion of operation. For Om|rj|Cmax, GR is predictable, but not fundamentally controllable. However, CR can be controlled to some extent by designing different scheduling algorithms.
Before presenting the complex network based dynamic rule selection approach, it is necessary to design several heuristic rules based on complex networks. The complex scheduling network model expresses the constraints between operations. Analysis of the topological features of complex networks helps simplify complex scheduling problems and inspire the design of heuristic rules based on complex networks. Given the fact that complex scheduling problems with different timing scheduling objectives can be congruously mapped to the node traversal problem on the complex scheduling network model, the general idea for generating complex network based heuristic rule is identical. The systematic heuristic rule generation approach based on network topological features can be divided into four steps:
(1) Establish complex scheduling network model for given scheduling object;
(2) Extract global features related to scheduling optimization objectives;
(3) Structure local features related to global features;
(4) Design heuristic rules based on the local features.
Intuitively, the more mutually exclusive timing constraints between the nodes in a network, the stronger the coupling between nodes, and consequently, the lower the traversal efficiency, and vice versa. Therefore, one feasible approach is to prioritize nodes that can significantly reduce system coupling after removal. Given that network average degree and network average efficiency can distinctly reflect this coupling, local topological features such as degree and clustering coefficient can be used as heuristic information. Therefore, the Largest Degree first (LD) rule and the Smallest Cluster Coefficient first (SCC) rule can be employed. In addition, the time attributes of nodes can also provide heuristic information, especially for non-uniform complex scheduling networks. Hence, the Longest Processing Time first (LPT) rule and the Shortest Processing Time first (SPT) rule are worthy of consideration. To combine the heuristic information from network topological features and time attributes of nodes, the Longest Total Remaining Processing on Adjacent Operations first (LTRPAO) rule and the Longest Total Remaining Processing on Other Machines first (LTRPOM) rule are developed. The effectiveness and performance of these six heuristic rules will be confirmed and compared in the experiments of Section 5.
Previous studies have shown that any elevated performance of an algorithm over one class of problems is offset by its performance over another class[25], which means no single dispatching rule performs dominantly better than any other in all scheduling environments[26]. Thus, designing or improving heuristic rules may not be the best research direction for solving NP-hard scheduling problems. With the arrival of new jobs and the completion of the operation, the production status changes over time, therefore, it is necessary to select the appropriate scheduling rules dynamically based on real-time production status, involving the effectiveness evaluation and selection of scheduling rules. The principle of dynamic rule selection based on complex networks can be divided into the following three steps:
(1) Calculate the attribute values of each node under different rules for each scenario.
(2) Design an effectiveness evaluation scheme based on the distribution of attribute values of nodes under different rules.
(3) Select the rule with the highest effectiveness as the rule in the current scenario.
Since the local features of nodes reflect the status of nodes in the network, the differences of local features provide heuristic information [27,28]. The larger the differences, the better effect the heuristic rule may achieve. Therefore, a feasible scheduling rule effectiveness evaluation scheme is to evaluate the difference in node attribute values under different rules. Considering that the node attribute values of different rules have different magnitudes and only one node needs to be selected at a time according to one scheduling rule, the ratio of the attribute value of the optimal node to the attribute value of the suboptimal node under different rules can be used as the validity index of the rule. The proof experiment of the proposed complex network based dynamic rule selection approach is also presented in Section 5.
To investigate the effectiveness of the proposed heuristic rules based on complex network, and to check the feasibility of the proposed complex network based dynamic rule selection approach, two experiments are carried out, respectively. All the experiments are executed on R2017a Matlab, 8 GB RAM and i7 processor.
In the first experiment, the open shop benchmarks from [29] are used to fully test the proposed heuristic rules based on complex networks, compared with the currently known optimal solution, and the chosen benchmarks are identical with the experiment in [30]. In order to verify whether the topology uniformity of the complex scheduling network has a significant impact on the performance of the rules, a carefully crafted set of test problems is generated for lack of the benchmark instances in the literature. To obtain the non-uniform open shop benchmarks with m jobs and m machines, the number of operations that are randomly removed from each job of the above benchmarks is subject to a discrete power-law distribution [31,32], with the range from 1 to m-1.
After mapping open shop scheduling problem to complex scheduling network model, Om‖Cmax can be transformed into reasonably arranging the node traversal order with the goal of traversing all nodes in the network as quickly as possible. All the proposed heuristic rules (LD, SCC, LPT, SPT, LTRPOM and LTRPAO) are used separately for solving Om‖Cmax. The results are listed in the Table 1, where the "BKS" is the best-known solution, 'm × m–k' means the kth instance for the OSSP with m jobs and m machines and 'm × m–k' is the instance generated by removing a part of the operations on the basis of 'm × m–k'.
Benchmark | BKS | LD | SCC | LPT | SPT | LTRPAO | LTRPOM |
10×10–1 | 637 | 702 | 702 | 674 | 683 | 674 | 682 |
10×10–2 | 588 | 629 | 629 | 658 | 624 | 639 | 626 |
10×10–3 | 598 | 711 | 711 | 698 | 706 | 708 | 749 |
10×10–4 | 577 | 690 | 690 | 668 | 680 | 689 | 710 |
10×10–5 | 640 | 685 | 685 | 723 | 707 | 707 | 746 |
10×10–6 | 538 | 668 | 668 | 666 | 660 | 665 | 678 |
15×15–1 | 937 | 958 | 958 | 946 | 995 | 944 | 948 |
15×15–2 | 918 | 998 | 998 | 1011 | 1013 | 981 | 1019 |
15×15–3 | 871 | 1013 | 1013 | 933 | 933 | 905 | 925 |
15×15–4 | 934 | 1064 | 1064 | 1055 | 1055 | 1063 | 1067 |
15×15–5 | 946 | 978 | 978 | 973 | 1024 | 986 | 1012 |
15×15–6 | 933 | 1043 | 1043 | 983 | 987 | 972 | 1009 |
20×20–1 | 1155 | 1290 | 1290 | 1230 | 1234 | 1314 | 1252 |
20×20–2 | 1241 | 1277 | 1277 | 1267 | 1316 | 1277 | 1287 |
20×20–3 | 1257 | 1391 | 1391 | 1375 | 1366 | 1386 | 1398 |
20×20–4 | 1248 | 1289 | 1289 | 1282 | 1340 | 1280 | 1337 |
20×20–5 | 1256 | 1276 | 1276 | 1279 | 1286 | 1305 | 1293 |
20×20–6 | 1204 | 1260 | 1260 | 1247 | 1254 | 1246 | 1251 |
10×10–1' | - | 632 | 631 | 634 | 671 | 650 | 664 |
10×10–2' | - | 527 | 574 | 562 | 579 | 533 | 543 |
10×10–3' | - | 650 | 669 | 646 | 668 | 650 | 655 |
10×10–4' | - | 584 | 605 | 622 | 591 | 615 | 609 |
10×10–5' | - | 639 | 665 | 692 | 651 | 670 | 659 |
10×10–6' | - | 661 | 660 | 660 | 660 | 693 | 662 |
15×15–1' | - | 923 | 883 | 909 | 911 | 908 | 908 |
15×15–2' | - | 996 | 970 | 965 | 975 | 992 | 976 |
15×15–3' | - | 898 | 855 | 870 | 854 | 861 | 869 |
15×15–4' | - | 1082 | 1047 | 1053 | 1059 | 1048 | 1073 |
15×15–5' | - | 938 | 895 | 927 | 901 | 928 | 969 |
15×15–6' | - | 925 | 972 | 909 | 942 | 916 | 917 |
20×20–1' | - | 1136 | 1144 | 1170 | 1135 | 1131 | 1155 |
20×20–2' | - | 1282 | 1303 | 1284 | 1262 | 1280 | 1279 |
20×20–3' | - | 1320 | 1306 | 1297 | 1303 | 1296 | 1321 |
20×20–4' | - | 1268 | 1260 | 1267 | 1309 | 1254 | 1280 |
20×20–5' | - | 1219 | 1187 | 1266 | 1233 | 1198 | 1214 |
20×20–6' | - | 1192 | 1233 | 1192 | 1202 | 1219 | 1190 |
Total time(s) | - | 120.9 | 122.6 | 145.8 | 145.2 | 172.6 | 174.4 |
From the above table, it is obvious that for uniform open shop scheduling problem, the consistent scheduling results are achieved by these two network topological features based heuristic rules: LD and SCC. The reasons are not hard to comprehend. (1) At the beginning, topological differences among nodes in the complex scheduling network for uniform Om‖Cmax do not work; (2) In the subsequent scheduling process, the local attributes of the nodes to be selected are sufficiently similar, and LD is approximately equivalent to SCC, subject to (11).
Ci=2∗Eiki∗(ki−1) | (11) |
In addition, heuristic rules involving local time attributes of nodes (LPT, SPT, LTRPAO and LTRPOM) obviously provide more heuristic information for uniform open shop scheduling problem. The results show that 16/18 best scheduling results are achieved by the heuristic rules involving local time attributes of nodes. Among them, LPT and LTRPAO perform best, the next does SPT, and the worst does LTRPOM. Both LPT and LTRPAO obtain 7/18 best scheduling schemes.
For non-uniform open shop scheduling problem, the running results of LD and SCC are no longer consistent, since different initial processing nodes are selected. Once the initial traversal nodes are different, the network will evolve in a significantly different direction. However, SCC becomes the best scheduling rule, and achieves 6/18 best scheduling schemes. It can be concluded that the effectiveness of heuristic rules based on the network topological features is greatly influenced by the non-uniformity of the initial complex network topology. The higher the non-uniformity, the better the scheduling effect, and vice versa. The performance of other heuristic rules is basically consistent with that of the uniform open shop scheduling problem. Specifically, LPT performs the best, followed by LTRPAO and SPT, and LTRPOM exhibits worst performance.
As outlined in Table 1, in terms of the computational speed, heuristic rules based on topological features have a slight advantage over the heuristic rules involving local time attributes. But all of them can meet the real-time requirements. In all experiments, the closest result to the best-known solution is obtained by LTRPAO rule on benchmark 15 × 15–1, and the Gantt chart is shown in Figure 3.
The first experiment illustrates the effectiveness of proposed heuristic rules based on complex networks. To further study the feasibility and effect of the proposed dynamic rule selection approach for open shop scheduling problem with release dates, a carefully crafted set of test problems is generated for the lack of benchmark instances in the literature for Om|rj|Cmax. In the benchmark instances, the processing time of each operation on the corresponding machine can vary within a range of 20–99, and the arrival time interval of two adjacent jobs can fluctuate within a range of 10–50. Based on the idea of dynamic rule selection approach, five new algorithms selected from different sets of heuristic rules are proposed, named DRSA1–DRSA5, respectively. The first one is selected from LPT, SPT, LTRPAO and LTRPOM, and the second to fifth algorithms are obtained by the first algorithm to remove separately LTRPOM, LTRPAO, SPT and LPT.
In Table 2, "m × m–k" instance means the kth case for the OSSP with m jobs and m machines at the beginning, and then another m jobs will arrive at random. Besides, the lower boundary 'LB' can be calculated roughly by the following formula:
LB=max(maxi∈Set1∑mk=1tki,maxi∈Set2∑mk=1tki+rti) | (12) |
Benchmark | LB | LD | SCC | LPT | SPT | LTRPAO | LTRPOM | DRSA1 | DRSA2 | DRSA3 | DRSA4 | DRSA5 |
10×10–1 | 984.3 | 1382 | 1382 | 1410 | 1409 | 1436 | 1397 | 1421 | 1434 | 1397 | 1405 | 1427 |
10×10–2 | 933 | 1447 | 1447 | 1452 | 1489 | 1480 | 1429 | 1458 | 1453 | 1458 | 1427 | 1446 |
10×10–3 | 949.6 | 1452 | 1452 | 1443 | 1432 | 1483 | 1461.4 | 1485 | 1442 | 1421 | 1453 | 1427 |
10×10–4 | 1060 | 1588 | 1588 | 1569 | 1598 | 1570 | 1516 | 1548 | 1572 | 1548 | 1610 | 1598 |
10×10–5 | 927 | 1418 | 1418 | 1436 | 1433 | 1418.6 | 1404 | 1396.6 | 1438.6 | 1408 | 1396.6 | 1401 |
10×10–6 | 919.2 | 1429 | 1429 | 1406 | 1494.7 | 1421 | 1430 | 1454 | 1450 | 1425 | 1421 | 1430 |
15×15–1 | 1471.9 | 2193 | 2193 | 2231 | 2159 | 2234 | 2217 | 2230 | 2196 | 2238 | 2204 | 2216 |
15×15–2 | 1463.3 | 2225 | 2225 | 2206 | 2188 | 2256 | 2207 | 2255 | 2218 | 2255 | 2204 | 2171 |
15×15–3 | 1342.5 | 2030 | 2030 | 2130 | 2101 | 2045 | 2100 | 2083 | 2065 | 2049 | 2076 | 2039 |
15×15–4 | 1161.2 | 2083 | 2083 | 2005 | 2039 | 2026 | 2043 | 2064 | 2096 | 2039.1 | 2047 | 2029 |
15×15–5 | 1379.1 | 2194 | 2194 | 2227 | 2204 | 2199 | 2199 | 2162 | 2175 | 2162 | 2168.1 | 2155 |
15×15–6 | 1311.5 | 2058 | 2058 | 2085 | 2068 | 2117 | 2075 | 2088 | 2053 | 2088 | 2079 | 2049 |
20×20–1 | 1912.6 | 2946 | 2946 | 2892 | 2927 | 2968 | 2948 | 2932 | 2944 | 2903 | 2904 | 2897 |
20×20–2 | 1842.9 | 2890 | 2890 | 2879 | 2877 | 2925 | 2888 | 2910 | 2867 | 2904 | 2896 | 2861 |
20×20–3 | 1797.4 | 2719 | 2719 | 2690 | 2723 | 2725 | 2737 | 2729 | 2714 | 2704 | 2725 | 2717 |
20×20–4 | 1800.4 | 2764 | 2764 | 2737 | 2757 | 2764 | 2776 | 2762 | 2753.2 | 2771 | 2781 | 2787 |
20×20–5 | 2001.9 | 2981 | 2981 | 2952 | 2936 | 2947 | 2961 | 2944 | 2990 | 2933 | 2949 | 2986 |
20×20–6 | 1906.9 | 2906 | 2906 | 2868 | 2954 | 2957 | 2894 | 2898 | 2931 | 2909 | 3000 | 2973 |
Total time (s) | - | 1819.2 | 1783.1 | 1893.8 | 1785.9 | 1901.3 | 1919.9 | 1808.1 | 1792.4 | 1796.4 | 1804.4 | 1804.4 |
where Set1 denotes a set of jobs at the beginning, Set2 denotes a set of jobs arriving successively and m is the number of machines.
As seen in Table 2, for uniform open shop scheduling problem with release dates, LD and SCC can still achieve the same scheduling results. Besides, it is clear that LPT rule is still the best-performing scheduling rule, but LTRPOM rule defeats LTRPAO rule. Satisfyingly, DRSA1–DRSA5 achieve similar performance compared with other single heuristic rules on all the benchmarks, and obtains better schemes than any single heuristic rules on the 8/18 benchmarks. Specially, DRSA5 achieves better results than that of any single heuristic rule on six benchmarks (10 × 10–3, 10 × 10–5, 15 × 15–2, 15 × 15–5, 15 × 15–6 and 20 × 20–2). And all the five dynamic rule selection approaches can obtain better results than that of any single heuristic rule on 15 × 15–5. The Gantt chart of best approximate scheme achieved by DRSA5 on benchmark 15 × 15–5 is shown in Figure 4. Compared withFigure 3, it appears that the result in Figure 5 is much more compact at the beginning. The main reason is that there are many jobs that can be processed at the beginning, due to the dynamic arrival of jobs.
The experimental results adequately demonstrate the feasibility and necessity of the proposed complex network based dynamic rule selection approach.
This study has dealt with open shop scheduling problems. Firstly, the framework of general scheduling object is built, under which most scheduling problems can be described, and open shop scheduling problem has no exception. Secondly, open shop scheduling problem is mapped to complex scheduling network model, in which one node denotes one operation of one job and one edge represents mutually exclusive timing constraint between two operations. By this means, OSSP can be transformed into reasonably arranging the node traversal order with the goal of traversing all nodes in the network as quickly as possible, on condition that each node has a traversal time, and only the disconnected nodes can be traversed simultaneously. Then from the perspective of decoupling complex scheduling networks, based on topological features, two heuristic rules (LD and SCC) are established. Given that local time attributes of nodes can also provide heuristic information, LPT and SPT are employed. Next, two heuristic rules (LTRPAO and LTRPOM) are developed to combine network topological features with local time attributes of nodes. Finally, an effective complex network based dynamic rule selection approach is proposed for open shop scheduling problem with release dates by switching the scheduling rules dynamically based on real-time production status.
For uniform Om‖Cmax and Om|rj|Cmax, heuristic rules based on topological features obtain same scheduling results. Moreover, heuristic rules involving local time attributes of nodes (LPT, SPT, LTRPAO and LTRPOM) provide more heuristic information and achieve better scheduling results on the most benchmarks. For non-uniform Om‖Cmax, LCC becomes the best scheduling rule and achieves 6/18 best scheduling results. Based on the idea of dynamic rule selection approach, DRSA1~DRSA5 are designed to change the scheduling rules dynamically based on real-time production status. They achieve similar performances compared with other single heuristic rules on all the benchmarks. Besides, they achieve better results than that of any single rule on the 8/18 benchmarks. The feasibility and necessity of the proposed complex networks based dynamic rule selection approach is confirmed. Future work is still needed to design more effective heuristic rules based on topological features or local time attributes of nodes for different scheduling objectives, and further study complex networks based dynamic rule selection mechanism for each scheduling decision scenario.
The authors would like to acknowledge financial supports of the National Science Foundation of China (No. 51775348, No. U1637211) and Shanghai Aerospace Science and Technology Innovation Fund (No. SAST2016048).
The authors declare no conflict of interest.
[1] |
Buckwalter JA, Glimcher MJ, Cooper RR (1995) Bone biology. Part I: Structure, blood supply, cells, matrix, and mineralization. J Bone Joint Surg 77: 1256-1275. doi: 10.2106/00004623-199508000-00019
![]() |
[2] | McCarthy I (2006) The physiology of bone blood flow: a review. JB & JS 88: 4-9. |
[3] |
Laroche M (2002) Intraosseous circulation from physiology to disease. Joint Bone Spine 69: 262-269. doi: 10.1016/S1297-319X(02)00391-3
![]() |
[4] |
Mercado-Pagán ÁE, Stahl AM, Shanjani Y, et al. (2015) Vascularization in bone tissue engineering constructs. Ann Biomed Eng 43: 718-729. doi: 10.1007/s10439-015-1253-3
![]() |
[5] |
Rouwkema J, Westerweel PE, De Boer J, et al. (2009) The use of endothelial progenitor cells for prevascularized bone tissue engineering. Tissue Eng Part A 15: 2015-2027. doi: 10.1089/ten.tea.2008.0318
![]() |
[6] |
Krishnan L, Willett NJ, Guldberg RE (2014) Vascularization strategies for bone regeneration. Ann Biomed Eng 42: 432-444. doi: 10.1007/s10439-014-0969-9
![]() |
[7] |
Shanjani Y, Kang Y, Zarnescu L, et al. (2017) Endothelial pattern formation in hybrid constructs of additive manufactured porous rigid scaffolds and cell-laden hydrogels for orthopedic applications. J Mech Behav Biomed Mater 65: 356-372. doi: 10.1016/j.jmbbm.2016.08.037
![]() |
[8] |
Murphy WL, Peters MC, Kohn DH, et al. (2000) Sustained release of vascular endothelial growth factor from mineralized poly (lactide-co-glycolide) scaffolds for tissue engineering. Biomaterials 21: 2521-2527. doi: 10.1016/S0142-9612(00)00120-4
![]() |
[9] |
Lee KY, Peters MC, Anderson KW, et al. (2000) Controlled growth factor release from synthetic extracellular matrices. Nature 408: 998-1000. doi: 10.1038/35050141
![]() |
[10] |
Sheridan MH, Shea LD, Peters MC, et al. (2000) Bioabsorbable polymer scaffolds for tissue engineering capable of sustained growth factor delivery. J Controll Release 64: 91-102. doi: 10.1016/S0168-3659(99)00138-8
![]() |
[11] |
Peters MC, Polverini PJ, Mooney DJ (2002) Engineering vascular networks in porous polymer matrices. J Biomed Mater Res A 60: 668-678. doi: 10.1002/jbm.10134
![]() |
[12] |
Wang L, Fan H, Zhang ZY, et al. (2010) Osteogenesis and angiogenesis of tissue-engineered bone constructed by prevascularized β-tricalcium phosphate scaffold and mesenchymal stem cells. Biomaterials 31: 9452-9461. doi: 10.1016/j.biomaterials.2010.08.036
![]() |
[13] |
Yu H, VandeVord PJ, Gong W, et al. (2008) Promotion of osteogenesis in tissue-engineered bone by pre-seeding endothelial progenitor cells-derived endothelial cells. J Orthop Res 26: 1147-1152. doi: 10.1002/jor.20609
![]() |
[14] |
Villars F, Bordenave L, Bareille R, et al. (2000) Effect of human endothelial cells on human bone marrow stromal cell phenotype: role of VEGF? J Cell Biochem 79: 672-685. doi: 10.1002/1097-4644(20001215)79:4<672::AID-JCB150>3.0.CO;2-2
![]() |
[15] |
Santos MI, Reis RL (2010) Vascularization in bone tissue engineering: physiology, current strategies, major hurdles and future challenges. Macromol Biosci 10: 12-27. doi: 10.1002/mabi.200900107
![]() |
[16] |
Villars F, Guillotin B, Amedee T, et al. (2002) Effect of HUVEC on human osteoprogenitor cell differentiation needs heterotypic gap junction communication. Am J Physiol-Cell Ph 282: C775-C85. doi: 10.1152/ajpcell.00310.2001
![]() |
[17] |
Stegen S, van Gastel N, Carmeliet G (2015) Bringing new life to damaged bone: the importance of angiogenesis in bone repair and regeneration. Bone 70: 19-27. doi: 10.1016/j.bone.2014.09.017
![]() |
[18] |
Ghanaati S, Fuchs S, Webber MJ, et al. (2011) Rapid vascularization of starch–poly (caprolactone) in vivo by outgrowth endothelial cells in co-culture with primary osteoblasts. J Tissue Eng Regen M 5: e136-e143. doi: 10.1002/term.373
![]() |
[19] |
Guillotin B, Bareille R, Bourget C, et al. (2008) Interaction between human umbilical vein endothelial cells and human osteoprogenitors triggers pleiotropic effect that may support osteoblastic function. Bone 42: 1080-1091. doi: 10.1016/j.bone.2008.01.025
![]() |
[20] |
Unger RE, Sartoris A, Peters K, et al. (2007) Tissue-like self-assembly in cocultures of endothelial cells and osteoblasts and the formation of microcapillary-like structures on three-dimensional porous biomaterials. Biomaterials 28: 3965-3976. doi: 10.1016/j.biomaterials.2007.05.032
![]() |
[21] | Ma JL, van den Beucken JJJP, Yang F, et al. (2011) Coculture of osteoblasts and endothelial cells: optimization of culture medium and cell ratio. Tissue Eng Part C 17: 349-357. |
[22] |
Black AF, Berthod F, L'Heureux N, et al. (1998) In vitro reconstruction of a human capillary-like network in a tissue-engineered skin equivalent. FASEB J 12: 1331-1340. doi: 10.1096/fasebj.12.13.1331
![]() |
[23] |
Chiu LLY, Montgomery M, Liang Y, et al. (2012) Perfusable branching microvessel bed for vascularization of engineered tissues. Proc Natl Acad Sci USA 109: E3414-E3423. doi: 10.1073/pnas.1210580109
![]() |
[24] |
Zheng Y, Chen J, Craven M, et al. (2012) In vitro microvessels for the study of angiogenesis and thrombosis. Proc Natl Acad Sci USA 109: 9342-9347. doi: 10.1073/pnas.1201240109
![]() |
[25] |
Chen YC, Lin RZ, Qi H, et al. (2012) Functional human vascular network generated in photocrosslinkable gelatin methacrylate hydrogels. Adv Funct Mater 22: 2027-2039. doi: 10.1002/adfm.201101662
![]() |
[26] |
Cuchiara MP, Gould DJ, McHale MK, et al. (2012) Integration of self-assembled microvascular networks with microfabricated PEG-based hydrogels. Adv Funct Mater 22: 4511-4518. doi: 10.1002/adfm.201200976
![]() |
[27] |
Chrobak KM, Potter DR, Tien J (2006) Formation of perfused, functional microvascular tubes in vitro. Microvasc Res 71: 185-196. doi: 10.1016/j.mvr.2006.02.005
![]() |
[28] |
Price GM, Wong KHK, Truslow JG, et al. (2010) Effect of mechanical factors on the function of engineered human blood microvessels in microfluidic collagen gels. Biomaterials 31: 6182-6189. doi: 10.1016/j.biomaterials.2010.04.041
![]() |
[29] |
Nichol JW, Koshy ST, Bae H, et al. (2010) Cell-laden microengineered gelatin methacrylate hydrogels. Biomaterials 31: 5536-5544. doi: 10.1016/j.biomaterials.2010.03.064
![]() |
[30] | Park JH, Chung BG, Lee WG, et al. (2010) Microporous cell-laden hydrogels for engineered tissue constructs. Biotechnol Bioeng 106: 138-148. |
[31] |
Sadr N, Zhu M, Osaki T, et al. (2011) SAM-based cell transfer to photopatterned hydrogels for microengineering vascular-like structures. Biomaterials 32: 7479-7490. doi: 10.1016/j.biomaterials.2011.06.034
![]() |
[32] |
Therriault D, White SR, Lewis JA (2003) Chaotic mixing in three-dimensional microvascular networks fabricated by direct-write assembly. Nat Mater 2: 265-271. doi: 10.1038/nmat863
![]() |
[33] |
Golden AP, Tien J (2007) Fabrication of microfluidic hydrogels using molded gelatin as a sacrificial element. Lab Chip 7: 720-725. doi: 10.1039/b618409j
![]() |
[34] |
Miller JS, Stevens KR, Yang MT, et al. (2012) Rapid casting of patterned vascular networks for perfusable engineered three-dimensional tissues. Nat Mater 11: 768-774. doi: 10.1038/nmat3357
![]() |
[35] |
Annabi N, Tamayol A, Uquillas JA, et al. (2014) 25th anniversary article: Rational design and applications of hydrogels in regenerative medicine. Adv Mater 26: 85-124. doi: 10.1002/adma.201303233
![]() |
[36] |
Bertassoni LE, Cardoso JC, Manoharan V, et al. (2014) Direct-write bioprinting of cell-laden methacrylated gelatin hydrogels. Biofabrication 6: 024105. doi: 10.1088/1758-5082/6/2/024105
![]() |
[37] |
Tan Y, Richards DJ, Trusk TC, et al. (2014) 3D printing facilitated scaffold-free tissue unit fabrication. Biofabrication 6: 024111. doi: 10.1088/1758-5082/6/2/024111
![]() |
[38] |
Wu W, DeConinck A, Lewis JA (2011) Omnidirectional printing of 3D microvascular networks. Adv Mater 23: H178-H183. doi: 10.1002/adma.201004625
![]() |
[39] |
Lee VK, Kim DY, Ngo H, et al. (2014) Creating perfused functional vascular channels using 3D bio-printing technology. Biomaterials 35: 8092-8102. doi: 10.1016/j.biomaterials.2014.05.083
![]() |
[40] |
Miller JS, Stevens KR, Yang MT, et al. (2012) Rapid casting of patterned vascular networks for perfusable engineered three-dimensional tissues. Nat Mater 11: 768-774. doi: 10.1038/nmat3357
![]() |
[41] |
Kolesky DB, Truby RL, Gladman AS, et al. (2014) 3D bioprinting of vascularized, heterogeneous cell-laden tissue constructs. Adv Mater 26: 3124-3130. doi: 10.1002/adma.201305506
![]() |
[42] |
Skardal A, Zhang J, McCoard L, et al. (2010) Photocrosslinkable hyaluronan-gelatin hydrogels for two-step bioprinting. Tissue Eng Part A 16: 2675-2685. doi: 10.1089/ten.tea.2009.0798
![]() |
[43] |
Gao Q, He Y, Fu J-z, et al. (2015) Coaxial nozzle-assisted 3D bioprinting with built-in microchannels for nutrients delivery. Biomaterials 61: 203-215. doi: 10.1016/j.biomaterials.2015.05.031
![]() |
[44] |
Yang L, Shridhar SV, Gerwitz M, et al. (2016) An in vitro vascular chip using 3D printing-enabled hydrogel casting. Biofabrication 8: 035015. doi: 10.1088/1758-5090/8/3/035015
![]() |
[45] |
Tocchio A, Tamplenizza M, Martello F, et al. (2015) Versatile fabrication of vascularizable scaffolds for large tissue engineering in bioreactor. Biomaterials 45: 124-131. doi: 10.1016/j.biomaterials.2014.12.031
![]() |
[46] |
Sawyer SW, Shridhar SV, Zhang K, et al. (2018) Perfusion directed 3D mineral formation within cell-laden hydrogels. Biofabrication 10: 035013. doi: 10.1088/1758-5090/aacb42
![]() |
[47] |
Sladkova M, De Peppo GM (2014) Bioreactor systems for human bone tissue engineering. Processes 2: 494-525. doi: 10.3390/pr2020494
![]() |
[48] |
Rice JJ, Martino MM, De Laporte L, et al. (2013) Engineering the regenerative microenvironment with biomaterials. Adv Healthc Mater 2: 57-71. doi: 10.1002/adhm.201200197
![]() |
[49] |
Cartmell SH, Porter BD, García AJ, et al. (2003) Effects of medium perfusion rate on cell-seeded three-dimensional bone constructs in vitro. Tissue Eng 9: 1197-1203. doi: 10.1089/10763270360728107
![]() |
[50] |
Albrecht LD, Sawyer SW, Soman P (2016) Developing 3D scaffolds in the field of tissue engineering to treat complex bone defects. 3D Print Addit Manuf 3: 106-112. doi: 10.1089/3dp.2016.0006
![]() |
[51] |
Hutmacher DW (2001) Scaffold design and fabrication technologies for engineering tissues—state of the art and future perspectives. J Biomater Sci Poly Ed 12: 107-124. doi: 10.1163/156856201744489
![]() |
[52] |
Burg KJL, Porter S, Kellam JF (2000) Biomaterial developments for bone tissue engineering. Biomaterials 21: 2347-2359. doi: 10.1016/S0142-9612(00)00102-2
![]() |
[53] |
Reichert JC, Hutmacher DW (2011) Bone tissue engineering. Tissue Engineering Heidelberg: Springer, 431-456. doi: 10.1007/978-3-642-02824-3_21
![]() |
[54] |
Bose S, Vahabzadeh S, Bandyopadhyay A (2013) Bone tissue engineering using 3D printing. Mater Today 16: 496-504. doi: 10.1016/j.mattod.2013.11.017
![]() |
[55] |
Stevens MM (2008) Biomaterials for bone tissue engineering. Mater Today 11: 18-25. doi: 10.1016/S1369-7021(08)70086-5
![]() |
[56] |
Baranski JD, Chaturvedi RR, Stevens KR, et al. (2013) Geometric control of vascular networks to enhance engineered tissue integration and function. Proc Natl Acad Sci USA 110: 7586-7591. doi: 10.1073/pnas.1217796110
![]() |
[57] |
Lee VK, Lanzi AM, Ngo H, et al. (2014) Generation of multi-scale vascular network system within 3D hydrogel using 3D bio-printing technology. Cell Mol Bioeng 7: 460-472. doi: 10.1007/s12195-014-0340-0
![]() |
[58] |
Sawyer S, Oest M, Margulies B, et al. (2016) Behavior of encapsulated saos-2 cells within gelatin methacrylate hydrogels. J Tissue Sci Eng 7: 1000173. doi: 10.4172/2157-7552.1000173
![]() |
[59] |
Sawyer SW, Dong P, Venn S, et al. (2017) Conductive gelatin methacrylate-poly (aniline) hydrogel for cell encapsulation. Biomed Phys Eng Express 4: 015005. doi: 10.1088/2057-1976/aa91f9
![]() |
[60] |
Mikos AG, Sarakinos G, Lyman MD, et al. (1993) Prevascularization of porous biodegradable polymers. Biotechnol Bioeng 42: 716-723. doi: 10.1002/bit.260420606
![]() |
![]() |
![]() |
Benchmark | BKS | LD | SCC | LPT | SPT | LTRPAO | LTRPOM |
10×10–1 | 637 | 702 | 702 | 674 | 683 | 674 | 682 |
10×10–2 | 588 | 629 | 629 | 658 | 624 | 639 | 626 |
10×10–3 | 598 | 711 | 711 | 698 | 706 | 708 | 749 |
10×10–4 | 577 | 690 | 690 | 668 | 680 | 689 | 710 |
10×10–5 | 640 | 685 | 685 | 723 | 707 | 707 | 746 |
10×10–6 | 538 | 668 | 668 | 666 | 660 | 665 | 678 |
15×15–1 | 937 | 958 | 958 | 946 | 995 | 944 | 948 |
15×15–2 | 918 | 998 | 998 | 1011 | 1013 | 981 | 1019 |
15×15–3 | 871 | 1013 | 1013 | 933 | 933 | 905 | 925 |
15×15–4 | 934 | 1064 | 1064 | 1055 | 1055 | 1063 | 1067 |
15×15–5 | 946 | 978 | 978 | 973 | 1024 | 986 | 1012 |
15×15–6 | 933 | 1043 | 1043 | 983 | 987 | 972 | 1009 |
20×20–1 | 1155 | 1290 | 1290 | 1230 | 1234 | 1314 | 1252 |
20×20–2 | 1241 | 1277 | 1277 | 1267 | 1316 | 1277 | 1287 |
20×20–3 | 1257 | 1391 | 1391 | 1375 | 1366 | 1386 | 1398 |
20×20–4 | 1248 | 1289 | 1289 | 1282 | 1340 | 1280 | 1337 |
20×20–5 | 1256 | 1276 | 1276 | 1279 | 1286 | 1305 | 1293 |
20×20–6 | 1204 | 1260 | 1260 | 1247 | 1254 | 1246 | 1251 |
10×10–1' | - | 632 | 631 | 634 | 671 | 650 | 664 |
10×10–2' | - | 527 | 574 | 562 | 579 | 533 | 543 |
10×10–3' | - | 650 | 669 | 646 | 668 | 650 | 655 |
10×10–4' | - | 584 | 605 | 622 | 591 | 615 | 609 |
10×10–5' | - | 639 | 665 | 692 | 651 | 670 | 659 |
10×10–6' | - | 661 | 660 | 660 | 660 | 693 | 662 |
15×15–1' | - | 923 | 883 | 909 | 911 | 908 | 908 |
15×15–2' | - | 996 | 970 | 965 | 975 | 992 | 976 |
15×15–3' | - | 898 | 855 | 870 | 854 | 861 | 869 |
15×15–4' | - | 1082 | 1047 | 1053 | 1059 | 1048 | 1073 |
15×15–5' | - | 938 | 895 | 927 | 901 | 928 | 969 |
15×15–6' | - | 925 | 972 | 909 | 942 | 916 | 917 |
20×20–1' | - | 1136 | 1144 | 1170 | 1135 | 1131 | 1155 |
20×20–2' | - | 1282 | 1303 | 1284 | 1262 | 1280 | 1279 |
20×20–3' | - | 1320 | 1306 | 1297 | 1303 | 1296 | 1321 |
20×20–4' | - | 1268 | 1260 | 1267 | 1309 | 1254 | 1280 |
20×20–5' | - | 1219 | 1187 | 1266 | 1233 | 1198 | 1214 |
20×20–6' | - | 1192 | 1233 | 1192 | 1202 | 1219 | 1190 |
Total time(s) | - | 120.9 | 122.6 | 145.8 | 145.2 | 172.6 | 174.4 |
Benchmark | LB | LD | SCC | LPT | SPT | LTRPAO | LTRPOM | DRSA1 | DRSA2 | DRSA3 | DRSA4 | DRSA5 |
10×10–1 | 984.3 | 1382 | 1382 | 1410 | 1409 | 1436 | 1397 | 1421 | 1434 | 1397 | 1405 | 1427 |
10×10–2 | 933 | 1447 | 1447 | 1452 | 1489 | 1480 | 1429 | 1458 | 1453 | 1458 | 1427 | 1446 |
10×10–3 | 949.6 | 1452 | 1452 | 1443 | 1432 | 1483 | 1461.4 | 1485 | 1442 | 1421 | 1453 | 1427 |
10×10–4 | 1060 | 1588 | 1588 | 1569 | 1598 | 1570 | 1516 | 1548 | 1572 | 1548 | 1610 | 1598 |
10×10–5 | 927 | 1418 | 1418 | 1436 | 1433 | 1418.6 | 1404 | 1396.6 | 1438.6 | 1408 | 1396.6 | 1401 |
10×10–6 | 919.2 | 1429 | 1429 | 1406 | 1494.7 | 1421 | 1430 | 1454 | 1450 | 1425 | 1421 | 1430 |
15×15–1 | 1471.9 | 2193 | 2193 | 2231 | 2159 | 2234 | 2217 | 2230 | 2196 | 2238 | 2204 | 2216 |
15×15–2 | 1463.3 | 2225 | 2225 | 2206 | 2188 | 2256 | 2207 | 2255 | 2218 | 2255 | 2204 | 2171 |
15×15–3 | 1342.5 | 2030 | 2030 | 2130 | 2101 | 2045 | 2100 | 2083 | 2065 | 2049 | 2076 | 2039 |
15×15–4 | 1161.2 | 2083 | 2083 | 2005 | 2039 | 2026 | 2043 | 2064 | 2096 | 2039.1 | 2047 | 2029 |
15×15–5 | 1379.1 | 2194 | 2194 | 2227 | 2204 | 2199 | 2199 | 2162 | 2175 | 2162 | 2168.1 | 2155 |
15×15–6 | 1311.5 | 2058 | 2058 | 2085 | 2068 | 2117 | 2075 | 2088 | 2053 | 2088 | 2079 | 2049 |
20×20–1 | 1912.6 | 2946 | 2946 | 2892 | 2927 | 2968 | 2948 | 2932 | 2944 | 2903 | 2904 | 2897 |
20×20–2 | 1842.9 | 2890 | 2890 | 2879 | 2877 | 2925 | 2888 | 2910 | 2867 | 2904 | 2896 | 2861 |
20×20–3 | 1797.4 | 2719 | 2719 | 2690 | 2723 | 2725 | 2737 | 2729 | 2714 | 2704 | 2725 | 2717 |
20×20–4 | 1800.4 | 2764 | 2764 | 2737 | 2757 | 2764 | 2776 | 2762 | 2753.2 | 2771 | 2781 | 2787 |
20×20–5 | 2001.9 | 2981 | 2981 | 2952 | 2936 | 2947 | 2961 | 2944 | 2990 | 2933 | 2949 | 2986 |
20×20–6 | 1906.9 | 2906 | 2906 | 2868 | 2954 | 2957 | 2894 | 2898 | 2931 | 2909 | 3000 | 2973 |
Total time (s) | - | 1819.2 | 1783.1 | 1893.8 | 1785.9 | 1901.3 | 1919.9 | 1808.1 | 1792.4 | 1796.4 | 1804.4 | 1804.4 |
Benchmark | BKS | LD | SCC | LPT | SPT | LTRPAO | LTRPOM |
10×10–1 | 637 | 702 | 702 | 674 | 683 | 674 | 682 |
10×10–2 | 588 | 629 | 629 | 658 | 624 | 639 | 626 |
10×10–3 | 598 | 711 | 711 | 698 | 706 | 708 | 749 |
10×10–4 | 577 | 690 | 690 | 668 | 680 | 689 | 710 |
10×10–5 | 640 | 685 | 685 | 723 | 707 | 707 | 746 |
10×10–6 | 538 | 668 | 668 | 666 | 660 | 665 | 678 |
15×15–1 | 937 | 958 | 958 | 946 | 995 | 944 | 948 |
15×15–2 | 918 | 998 | 998 | 1011 | 1013 | 981 | 1019 |
15×15–3 | 871 | 1013 | 1013 | 933 | 933 | 905 | 925 |
15×15–4 | 934 | 1064 | 1064 | 1055 | 1055 | 1063 | 1067 |
15×15–5 | 946 | 978 | 978 | 973 | 1024 | 986 | 1012 |
15×15–6 | 933 | 1043 | 1043 | 983 | 987 | 972 | 1009 |
20×20–1 | 1155 | 1290 | 1290 | 1230 | 1234 | 1314 | 1252 |
20×20–2 | 1241 | 1277 | 1277 | 1267 | 1316 | 1277 | 1287 |
20×20–3 | 1257 | 1391 | 1391 | 1375 | 1366 | 1386 | 1398 |
20×20–4 | 1248 | 1289 | 1289 | 1282 | 1340 | 1280 | 1337 |
20×20–5 | 1256 | 1276 | 1276 | 1279 | 1286 | 1305 | 1293 |
20×20–6 | 1204 | 1260 | 1260 | 1247 | 1254 | 1246 | 1251 |
10×10–1' | - | 632 | 631 | 634 | 671 | 650 | 664 |
10×10–2' | - | 527 | 574 | 562 | 579 | 533 | 543 |
10×10–3' | - | 650 | 669 | 646 | 668 | 650 | 655 |
10×10–4' | - | 584 | 605 | 622 | 591 | 615 | 609 |
10×10–5' | - | 639 | 665 | 692 | 651 | 670 | 659 |
10×10–6' | - | 661 | 660 | 660 | 660 | 693 | 662 |
15×15–1' | - | 923 | 883 | 909 | 911 | 908 | 908 |
15×15–2' | - | 996 | 970 | 965 | 975 | 992 | 976 |
15×15–3' | - | 898 | 855 | 870 | 854 | 861 | 869 |
15×15–4' | - | 1082 | 1047 | 1053 | 1059 | 1048 | 1073 |
15×15–5' | - | 938 | 895 | 927 | 901 | 928 | 969 |
15×15–6' | - | 925 | 972 | 909 | 942 | 916 | 917 |
20×20–1' | - | 1136 | 1144 | 1170 | 1135 | 1131 | 1155 |
20×20–2' | - | 1282 | 1303 | 1284 | 1262 | 1280 | 1279 |
20×20–3' | - | 1320 | 1306 | 1297 | 1303 | 1296 | 1321 |
20×20–4' | - | 1268 | 1260 | 1267 | 1309 | 1254 | 1280 |
20×20–5' | - | 1219 | 1187 | 1266 | 1233 | 1198 | 1214 |
20×20–6' | - | 1192 | 1233 | 1192 | 1202 | 1219 | 1190 |
Total time(s) | - | 120.9 | 122.6 | 145.8 | 145.2 | 172.6 | 174.4 |
Benchmark | LB | LD | SCC | LPT | SPT | LTRPAO | LTRPOM | DRSA1 | DRSA2 | DRSA3 | DRSA4 | DRSA5 |
10×10–1 | 984.3 | 1382 | 1382 | 1410 | 1409 | 1436 | 1397 | 1421 | 1434 | 1397 | 1405 | 1427 |
10×10–2 | 933 | 1447 | 1447 | 1452 | 1489 | 1480 | 1429 | 1458 | 1453 | 1458 | 1427 | 1446 |
10×10–3 | 949.6 | 1452 | 1452 | 1443 | 1432 | 1483 | 1461.4 | 1485 | 1442 | 1421 | 1453 | 1427 |
10×10–4 | 1060 | 1588 | 1588 | 1569 | 1598 | 1570 | 1516 | 1548 | 1572 | 1548 | 1610 | 1598 |
10×10–5 | 927 | 1418 | 1418 | 1436 | 1433 | 1418.6 | 1404 | 1396.6 | 1438.6 | 1408 | 1396.6 | 1401 |
10×10–6 | 919.2 | 1429 | 1429 | 1406 | 1494.7 | 1421 | 1430 | 1454 | 1450 | 1425 | 1421 | 1430 |
15×15–1 | 1471.9 | 2193 | 2193 | 2231 | 2159 | 2234 | 2217 | 2230 | 2196 | 2238 | 2204 | 2216 |
15×15–2 | 1463.3 | 2225 | 2225 | 2206 | 2188 | 2256 | 2207 | 2255 | 2218 | 2255 | 2204 | 2171 |
15×15–3 | 1342.5 | 2030 | 2030 | 2130 | 2101 | 2045 | 2100 | 2083 | 2065 | 2049 | 2076 | 2039 |
15×15–4 | 1161.2 | 2083 | 2083 | 2005 | 2039 | 2026 | 2043 | 2064 | 2096 | 2039.1 | 2047 | 2029 |
15×15–5 | 1379.1 | 2194 | 2194 | 2227 | 2204 | 2199 | 2199 | 2162 | 2175 | 2162 | 2168.1 | 2155 |
15×15–6 | 1311.5 | 2058 | 2058 | 2085 | 2068 | 2117 | 2075 | 2088 | 2053 | 2088 | 2079 | 2049 |
20×20–1 | 1912.6 | 2946 | 2946 | 2892 | 2927 | 2968 | 2948 | 2932 | 2944 | 2903 | 2904 | 2897 |
20×20–2 | 1842.9 | 2890 | 2890 | 2879 | 2877 | 2925 | 2888 | 2910 | 2867 | 2904 | 2896 | 2861 |
20×20–3 | 1797.4 | 2719 | 2719 | 2690 | 2723 | 2725 | 2737 | 2729 | 2714 | 2704 | 2725 | 2717 |
20×20–4 | 1800.4 | 2764 | 2764 | 2737 | 2757 | 2764 | 2776 | 2762 | 2753.2 | 2771 | 2781 | 2787 |
20×20–5 | 2001.9 | 2981 | 2981 | 2952 | 2936 | 2947 | 2961 | 2944 | 2990 | 2933 | 2949 | 2986 |
20×20–6 | 1906.9 | 2906 | 2906 | 2868 | 2954 | 2957 | 2894 | 2898 | 2931 | 2909 | 3000 | 2973 |
Total time (s) | - | 1819.2 | 1783.1 | 1893.8 | 1785.9 | 1901.3 | 1919.9 | 1808.1 | 1792.4 | 1796.4 | 1804.4 | 1804.4 |