In this paper we consider a single-machine scheduling model with deteriorating jobs and simultaneous learning, and we introduce polynomial solutions for single machine makespan minimization, total flow times minimizat...In this paper we consider a single-machine scheduling model with deteriorating jobs and simultaneous learning, and we introduce polynomial solutions for single machine makespan minimization, total flow times minimization and maximum lateness minimization corresponding to the first and second special cases of our model under some agreeable conditions. However, corresponding to the third special case of our model, we show that the optimal schedules may be different from those of the classical version for the above objective functions.展开更多
Apache Spark provides a well-known Map Reduce computing framework,aiming to fast-process big data analytics in data-parallel manners.With this platform,large input data are divided into data partitions.Each data parti...Apache Spark provides a well-known Map Reduce computing framework,aiming to fast-process big data analytics in data-parallel manners.With this platform,large input data are divided into data partitions.Each data partition is processed by multiple computation tasks concurrently.Outputs of these computation tasks are transferred among multiple computers via the network.However,such a distributed computing framework suffers from system overheads,inevitably caused by communication and disk I/O operations.System overheads take up a large proportion of the Job Completion Time(JCT).We observed that excessive computational resources incurs considerable system overheads,prolonging the JCT.The over-allocation of individual jobs not only prolongs their own JCTs,but also likely makes other jobs suffer from under-allocation.Thus,the average JCT is suboptimal,too.To address this problem,we propose a prediction model to estimate the changing JCT of a single Spark job.With the support of the prediction method,we designed a heuristic algorithm to balance the resource allocation of multiple Spark jobs,aiming to minimize the average JCT in multiple-job cases.We implemented the prediction model and resource allocation method in Re B,a Resource-Balancer based on Apache Spark.Experimental results showed that Re B significantly outperformed the traditional max-min fairness and shortest-job-optimal methods.The average JCT was decreased by around 10%–30%compared to the existing solutions.展开更多
Cloud service providers generally co-locate online services and batch jobs onto the same computer cluster,where the resources can be pooled in order to maximize data center resource utilization.Due to resource competi...Cloud service providers generally co-locate online services and batch jobs onto the same computer cluster,where the resources can be pooled in order to maximize data center resource utilization.Due to resource competition between batch jobs and online services,co-location frequently impairs the performance of online services.This study presents a quality of service(QoS)prediction-based schedulingmodel(QPSM)for co-locatedworkloads.The performance prediction of QPSM consists of two parts:the prediction of an online service’s QoS anomaly based on XGBoost and the prediction of the completion time of an offline batch job based on randomforest.On-line service QoS anomaly prediction is used to evaluate the influence of batch jobmix on on-line service performance,and batch job completion time prediction is utilized to reduce the total waiting time of batch jobs.When the same number of batch jobs are scheduled in experiments using typical test sets such as CloudSuite,the scheduling time required by QPSM is reduced by about 6 h on average compared with the first-come,first-served strategy and by about 11 h compared with the random scheduling strategy.Compared with the non-co-located situation,QPSM can improve CPU resource utilization by 12.15% and memory resource utilization by 5.7% on average.Experiments show that the QPSM scheduling strategy proposed in this study can effectively guarantee the quality of online services and further improve cluster resource utilization.展开更多
In order to analyze and process the large graphs with high cost efficiency,researchers have developed a number of out-of-core graph processing systems in recent years based on just one commodity computer.On the other ...In order to analyze and process the large graphs with high cost efficiency,researchers have developed a number of out-of-core graph processing systems in recent years based on just one commodity computer.On the other hand,with the rapidly growing need of analyzing graphs in the real-world,graph processing systems have to efficiently handle massive concurrent graph processing(CGP)jobs.Unfortunately,due to the inherent design for single graph processing job,existing out-of-core graph processing systems usually incur unnecessary data accesses and severe competition of I/O bandwidth when handling the CGP jobs.In this paper,we propose GraphCP,a disk I/O optimized out-of-core graph processing system that efficiently supports the processing of CGP jobs.GraphCP proposes a benefit-aware sharing execution model to share the I/O access and processing of graph data among the CGP jobs and adaptively schedule the graph data loading based on the states of vertices,which efficiently overcomes above challenges faced by existing out-of-core graph processing systems.Moreover,GraphCP adopts a dependency-based future-vertex updating model so as to reduce disk I/Os in the future iterations.In addition,GraphCP organizes the graph data with a Source-Sorted Sub-Block graph representation for better processing capacity and I/O access locality.Extensive evaluation results show that GraphCP is 20.5×and 8.9×faster than two out-of-core graph processing systems GridGraph and GraphZ,and 3.5×and 1.7×faster than two state-of-art concurrent graph processing systems Seraph and GraphSO.展开更多
This paper addresses a multi-agent scheduling problem with uniform parallel machines owned by a resource agent and competing jobs with dynamic arrival times that belong to different consumer agents.All agents are self...This paper addresses a multi-agent scheduling problem with uniform parallel machines owned by a resource agent and competing jobs with dynamic arrival times that belong to different consumer agents.All agents are self-interested and rational with the aim of maximizing their own objectives,resulting in intense resource competition among consumer agents and strategic behaviors of unwillingness to disclose private information.Within the context,a centralized scheduling approach is unfeasible,and a decentralized approach is considered to deal with the targeted problem.This study aims to generate a stable and collaborative solution with high social welfare while simultaneously accommodating consumer agents’preferences under incomplete information.For this purpose,a dynamic iterative auction-based approach based on a decentralized decision-making procedure is developed.In the proposed approach,a dynamic auction procedure is established for dynamic jobs participating in a realtime auction,and a straightforward and easy-to-implement bidding strategy without price is presented to reduce the complexity of bid determination.In addition,an adaptive Hungarian algorithm is applied to solve the winner determination problem efficiently.A theoretical analysis is conducted to prove that the proposed approach is individually rational and that the myopic bidding strategy is a weakly dominant strategy for consumer agents submitting bids.Extensive computational experiments demonstrate that the developed approach achieves high-quality solutions and exhibits considerable stability on largescale problems with numerous consumer agents and jobs.A further multi-agent scheduling problem considering multiple resource agents will be studied in future work.展开更多
With the rapid urbanization of Chinese cities,access to jobs and amenities is becoming increasingly valued in household＇s choice of residential locations.In this paper,we estimate the implicit value of access to jobs...With the rapid urbanization of Chinese cities,access to jobs and amenities is becoming increasingly valued in household＇s choice of residential locations.In this paper,we estimate the implicit value of access to jobs and amenities in Beijing using the hedonic pricing model.The spatial distributions of jobs and amenities in the Beijing Metropolitan Area are quite centralized,supporting the traditional monocentric model in the urban economics literature.Accessibility indices are developed to measure the accessibilities to jobs and amenities of 129 Jiedaos（residential zones）.We then employ the hedonic pricing equations to estimate the capitalization effects of these accessibility indices in the prices of new residential properties.The empirical results show that the accessibility indices are important determinants of residential property prices in Beijing,which means that urban residents have a willingness to pay for access to high quality amenities.展开更多
文摘In this paper we consider a single-machine scheduling model with deteriorating jobs and simultaneous learning, and we introduce polynomial solutions for single machine makespan minimization, total flow times minimization and maximum lateness minimization corresponding to the first and second special cases of our model under some agreeable conditions. However, corresponding to the third special case of our model, we show that the optimal schedules may be different from those of the classical version for the above objective functions.
基金supported in part by the National Key R&D Program of China(No.2018YFB2101100)the National Natural Science Foundation of China(Nos.61932001 and61872376)Hunan Provincial Innovation Foundation For Postgraduate.
文摘Apache Spark provides a well-known Map Reduce computing framework,aiming to fast-process big data analytics in data-parallel manners.With this platform,large input data are divided into data partitions.Each data partition is processed by multiple computation tasks concurrently.Outputs of these computation tasks are transferred among multiple computers via the network.However,such a distributed computing framework suffers from system overheads,inevitably caused by communication and disk I/O operations.System overheads take up a large proportion of the Job Completion Time(JCT).We observed that excessive computational resources incurs considerable system overheads,prolonging the JCT.The over-allocation of individual jobs not only prolongs their own JCTs,but also likely makes other jobs suffer from under-allocation.Thus,the average JCT is suboptimal,too.To address this problem,we propose a prediction model to estimate the changing JCT of a single Spark job.With the support of the prediction method,we designed a heuristic algorithm to balance the resource allocation of multiple Spark jobs,aiming to minimize the average JCT in multiple-job cases.We implemented the prediction model and resource allocation method in Re B,a Resource-Balancer based on Apache Spark.Experimental results showed that Re B significantly outperformed the traditional max-min fairness and shortest-job-optimal methods.The average JCT was decreased by around 10%–30%compared to the existing solutions.
基金supported by the NationalNatural Science Foundation of China(No.61972118)the Key R&D Program of Zhejiang Province(No.2023C01028).
文摘Cloud service providers generally co-locate online services and batch jobs onto the same computer cluster,where the resources can be pooled in order to maximize data center resource utilization.Due to resource competition between batch jobs and online services,co-location frequently impairs the performance of online services.This study presents a quality of service(QoS)prediction-based schedulingmodel(QPSM)for co-locatedworkloads.The performance prediction of QPSM consists of two parts:the prediction of an online service’s QoS anomaly based on XGBoost and the prediction of the completion time of an offline batch job based on randomforest.On-line service QoS anomaly prediction is used to evaluate the influence of batch jobmix on on-line service performance,and batch job completion time prediction is utilized to reduce the total waiting time of batch jobs.When the same number of batch jobs are scheduled in experiments using typical test sets such as CloudSuite,the scheduling time required by QPSM is reduced by about 6 h on average compared with the first-come,first-served strategy and by about 11 h compared with the random scheduling strategy.Compared with the non-co-located situation,QPSM can improve CPU resource utilization by 12.15% and memory resource utilization by 5.7% on average.Experiments show that the QPSM scheduling strategy proposed in this study can effectively guarantee the quality of online services and further improve cluster resource utilization.
基金supported by the National Natural Science Foundation of China(Grant Nos.61832020,61821003 and U1705261)National Defense Preliminary Research Project(No.31511010202)+3 种基金the Fundamental Research Funds for the Central Universities,the Open Project Program of Wuhan National Laboratory for Optoelectronics(No.2022WNLOKF017)the Natural Science Foundation of Fujian Province(No.2020J01493)Zhejiang provincial“Ten Thousand Talents Program”(No.2021R52007)Center-initiated Research Project of Zhejiang Lab(No.2021DA0AM01).
文摘In order to analyze and process the large graphs with high cost efficiency,researchers have developed a number of out-of-core graph processing systems in recent years based on just one commodity computer.On the other hand,with the rapidly growing need of analyzing graphs in the real-world,graph processing systems have to efficiently handle massive concurrent graph processing(CGP)jobs.Unfortunately,due to the inherent design for single graph processing job,existing out-of-core graph processing systems usually incur unnecessary data accesses and severe competition of I/O bandwidth when handling the CGP jobs.In this paper,we propose GraphCP,a disk I/O optimized out-of-core graph processing system that efficiently supports the processing of CGP jobs.GraphCP proposes a benefit-aware sharing execution model to share the I/O access and processing of graph data among the CGP jobs and adaptively schedule the graph data loading based on the states of vertices,which efficiently overcomes above challenges faced by existing out-of-core graph processing systems.Moreover,GraphCP adopts a dependency-based future-vertex updating model so as to reduce disk I/Os in the future iterations.In addition,GraphCP organizes the graph data with a Source-Sorted Sub-Block graph representation for better processing capacity and I/O access locality.Extensive evaluation results show that GraphCP is 20.5×and 8.9×faster than two out-of-core graph processing systems GridGraph and GraphZ,and 3.5×and 1.7×faster than two state-of-art concurrent graph processing systems Seraph and GraphSO.
基金supported by the National Natural Science Foundation of China(51975482)the China Scholarship Council.
文摘This paper addresses a multi-agent scheduling problem with uniform parallel machines owned by a resource agent and competing jobs with dynamic arrival times that belong to different consumer agents.All agents are self-interested and rational with the aim of maximizing their own objectives,resulting in intense resource competition among consumer agents and strategic behaviors of unwillingness to disclose private information.Within the context,a centralized scheduling approach is unfeasible,and a decentralized approach is considered to deal with the targeted problem.This study aims to generate a stable and collaborative solution with high social welfare while simultaneously accommodating consumer agents’preferences under incomplete information.For this purpose,a dynamic iterative auction-based approach based on a decentralized decision-making procedure is developed.In the proposed approach,a dynamic auction procedure is established for dynamic jobs participating in a realtime auction,and a straightforward and easy-to-implement bidding strategy without price is presented to reduce the complexity of bid determination.In addition,an adaptive Hungarian algorithm is applied to solve the winner determination problem efficiently.A theoretical analysis is conducted to prove that the proposed approach is individually rational and that the myopic bidding strategy is a weakly dominant strategy for consumer agents submitting bids.Extensive computational experiments demonstrate that the developed approach achieves high-quality solutions and exhibits considerable stability on largescale problems with numerous consumer agents and jobs.A further multi-agent scheduling problem considering multiple resource agents will be studied in future work.
基金Supported by the National Natural Science Foundation of China(No 70973065)
文摘With the rapid urbanization of Chinese cities,access to jobs and amenities is becoming increasingly valued in household＇s choice of residential locations.In this paper,we estimate the implicit value of access to jobs and amenities in Beijing using the hedonic pricing model.The spatial distributions of jobs and amenities in the Beijing Metropolitan Area are quite centralized,supporting the traditional monocentric model in the urban economics literature.Accessibility indices are developed to measure the accessibilities to jobs and amenities of 129 Jiedaos（residential zones）.We then employ the hedonic pricing equations to estimate the capitalization effects of these accessibility indices in the prices of new residential properties.The empirical results show that the accessibility indices are important determinants of residential property prices in Beijing,which means that urban residents have a willingness to pay for access to high quality amenities.
