In the rescheduling on a single machine,a set of original jobs has already been scheduled to minimize some cost objective,when a new set of jobs arrives and creates a disruption.The decision maker needs to insert the ...In the rescheduling on a single machine,a set of original jobs has already been scheduled to minimize some cost objective,when a new set of jobs arrives and creates a disruption.The decision maker needs to insert the new jobs into the existing schedule without excessively disrupting it.In this paper,we consider hierarchical optimization between the scheduling cost of all the jobs and the degree of this disruption.For every problem,we provide either a polynomial time algorithm or an intractable result.展开更多
Decreasing the flow completion time(FCT) and increasing the throughput are two fundamental targets in datacenter networks(DCNs), but current mechanisms mostly focus on one of the problems. In this paper, we propose OF...Decreasing the flow completion time(FCT) and increasing the throughput are two fundamental targets in datacenter networks(DCNs), but current mechanisms mostly focus on one of the problems. In this paper, we propose OFMPC, an Open Flow based Multi Path Cooperation framework, to decrease FCT and increase the network throughput. OFMPC partitions the end-to-end transmission paths into two classes, which are low delay paths(LDPs) and high throughput paths(HTPs), respectively. Short flows are assigned to LDPs to avoid long queueing delay, while long flows are assigned to HTPs to guarantee their throughput. Meanwhile, a dynamic scheduling mechanism is presented to improve network efficiency. We evaluate OFMPC in Mininet emulator and a testbed, and the experimental results show that OFMPC can effectively decrease FCT. Besides, OFMPC also increases the throughput up to more than 84% of bisection bandwidth.展开更多
A batch is a subset of jobs which must be processed jointly in either serial or parallel form. For the single machine, batching, total completion time scheduling problems, the algorithmic aspects have been extensively...A batch is a subset of jobs which must be processed jointly in either serial or parallel form. For the single machine, batching, total completion time scheduling problems, the algorithmic aspects have been extensively studied in the literature. This paper presents the optimal hatching structures of the problems on the batching ways： all jobs in exactly N（arbitrary fix batch number and 1 〈 N 〈 n） batches.展开更多
This paper proposes a hybrid optimization to solve the scheduling of household power consumption for Step and Time-of-Use (TOU) tariff system. The target function is the cost of electricity, and the optimization objec...This paper proposes a hybrid optimization to solve the scheduling of household power consumption for Step and Time-of-Use (TOU) tariff system. The target function is the cost of electricity, and the optimization object is total instantaneous power within a billing period. The control variables are starting moments of each household appliance. The optimization procedure is divided into two stages. Firstly, the prerequisite for minimal cost is calculated through mathematical analysis and generalized function theory. Secondly, the solution is obtained by using a heuristic algorithm in which the result of the first stage is considered to reduce the searching space. And an evaluation methodology is deduced to evaluate the optimization. The computer simulation demonstrates that the proposed approach can reduce the cost of electricity evidently in the sense of probability. The approach shows great value for embedded applications.展开更多
Nowadays, the study of myths is rather neglected as a field of research in sociology. There is a void that this paper would like to contribute to filling. It outlines a theoretical and empirical sociological approach ...Nowadays, the study of myths is rather neglected as a field of research in sociology. There is a void that this paper would like to contribute to filling. It outlines a theoretical and empirical sociological approach to social myths as a major component of collective imaginaries and a universal sociological mechanism through time and space. The article recalls the major functions performed by myths in every society （modem as well as ＂primitive＂）, introduces new concepts, and sets forth an analytical framework designed to account for the emergence, the reproduction, and the decline of myths, as sacralised collective representations.展开更多
Ia this paper, we consider a semi on-line version on two uniform machines Mi, i = 1, 2, where the processing time of the largest job is known in advance. A speed si（s1 = 1, 1 ≤s2 = s） is associated with machine Mi....Ia this paper, we consider a semi on-line version on two uniform machines Mi, i = 1, 2, where the processing time of the largest job is known in advance. A speed si（s1 = 1, 1 ≤s2 = s） is associated with machine Mi. Our goal is to maximize the Cmin. We give a Cmin 2 algorithm and prove its competitive ratio is at most 2s＋1/s＋1 We also claim the Cmin 2 algorithm is tight and the gap between the competitive ratio of Cmin2 algorithm and the optimal value is not greater than 0.555. It is obvious that our result coincides with that given by He for s =1.展开更多
This paper considers two parallel machine scheduling problems, where the objectives of both problems are to minimize the makespan, and the jobs arrive over time, on two uniform machines with speeds 1 and s （s 〉 1）,...This paper considers two parallel machine scheduling problems, where the objectives of both problems are to minimize the makespan, and the jobs arrive over time, on two uniform machines with speeds 1 and s （s 〉 1）, and on m identical machines, respectively. For the first problem, the authors show that the on-line LPT algorithm has a competitive ratio of （1 ＋ √5）/2 ≈ 1.6180 and the bound is tight. Furthermore, the authors prove that the on-line LPT algorithm has the best possible competitive ratio if s ≥ 1.8020. For the second problem, the authors present a lower bound of （15 - √17）/8 ≈ 1.3596 on the competitive ratio of any deterministic on-line algorithm. This improves a previous result of 1.3473.展开更多
基金Supported by the NSFC(10671183)Supported by the Science Foundation of Henan University of Technology(07XJC002)+1 种基金Supported by the NSF of the Education Department of Henan Province(2008A11004)Supported by the NSF of Henan Province(082300410190)
文摘In the rescheduling on a single machine,a set of original jobs has already been scheduled to minimize some cost objective,when a new set of jobs arrives and creates a disruption.The decision maker needs to insert the new jobs into the existing schedule without excessively disrupting it.In this paper,we consider hierarchical optimization between the scheduling cost of all the jobs and the degree of this disruption.For every problem,we provide either a polynomial time algorithm or an intractable result.
基金supported by the State Key Development Program for Basic Research of China under Grant No.2012CB315806the National Natural Science Foundation of China under Grant Nos.61103225 and 61379149+1 种基金Jiangsu Province Natural Science Foundation of China under Grant No.BK20140070Jiangsu Future Networks Innovation Institute Prospective Research Project on Future Networks under Grant No.BY2013095-1-06
文摘Decreasing the flow completion time(FCT) and increasing the throughput are two fundamental targets in datacenter networks(DCNs), but current mechanisms mostly focus on one of the problems. In this paper, we propose OFMPC, an Open Flow based Multi Path Cooperation framework, to decrease FCT and increase the network throughput. OFMPC partitions the end-to-end transmission paths into two classes, which are low delay paths(LDPs) and high throughput paths(HTPs), respectively. Short flows are assigned to LDPs to avoid long queueing delay, while long flows are assigned to HTPs to guarantee their throughput. Meanwhile, a dynamic scheduling mechanism is presented to improve network efficiency. We evaluate OFMPC in Mininet emulator and a testbed, and the experimental results show that OFMPC can effectively decrease FCT. Besides, OFMPC also increases the throughput up to more than 84% of bisection bandwidth.
基金Supported by the NSF of Henan Province(082300410070)
文摘A batch is a subset of jobs which must be processed jointly in either serial or parallel form. For the single machine, batching, total completion time scheduling problems, the algorithmic aspects have been extensively studied in the literature. This paper presents the optimal hatching structures of the problems on the batching ways： all jobs in exactly N（arbitrary fix batch number and 1 〈 N 〈 n） batches.
文摘This paper proposes a hybrid optimization to solve the scheduling of household power consumption for Step and Time-of-Use (TOU) tariff system. The target function is the cost of electricity, and the optimization object is total instantaneous power within a billing period. The control variables are starting moments of each household appliance. The optimization procedure is divided into two stages. Firstly, the prerequisite for minimal cost is calculated through mathematical analysis and generalized function theory. Secondly, the solution is obtained by using a heuristic algorithm in which the result of the first stage is considered to reduce the searching space. And an evaluation methodology is deduced to evaluate the optimization. The computer simulation demonstrates that the proposed approach can reduce the cost of electricity evidently in the sense of probability. The approach shows great value for embedded applications.
文摘Nowadays, the study of myths is rather neglected as a field of research in sociology. There is a void that this paper would like to contribute to filling. It outlines a theoretical and empirical sociological approach to social myths as a major component of collective imaginaries and a universal sociological mechanism through time and space. The article recalls the major functions performed by myths in every society （modem as well as ＂primitive＂）, introduces new concepts, and sets forth an analytical framework designed to account for the emergence, the reproduction, and the decline of myths, as sacralised collective representations.
文摘Ia this paper, we consider a semi on-line version on two uniform machines Mi, i = 1, 2, where the processing time of the largest job is known in advance. A speed si（s1 = 1, 1 ≤s2 = s） is associated with machine Mi. Our goal is to maximize the Cmin. We give a Cmin 2 algorithm and prove its competitive ratio is at most 2s＋1/s＋1 We also claim the Cmin 2 algorithm is tight and the gap between the competitive ratio of Cmin2 algorithm and the optimal value is not greater than 0.555. It is obvious that our result coincides with that given by He for s =1.
基金supported by the Special Funds of the National Natural Science Foundation of China under Grant No.61340045the Specialized Research Fund for the Doctoral Program of Higher Education of China under Grant No.20123705110003Innovation Project of Shangdong Graduate Education under Grant No.SDYC13036
文摘This paper considers two parallel machine scheduling problems, where the objectives of both problems are to minimize the makespan, and the jobs arrive over time, on two uniform machines with speeds 1 and s （s 〉 1）, and on m identical machines, respectively. For the first problem, the authors show that the on-line LPT algorithm has a competitive ratio of （1 ＋ √5）/2 ≈ 1.6180 and the bound is tight. Furthermore, the authors prove that the on-line LPT algorithm has the best possible competitive ratio if s ≥ 1.8020. For the second problem, the authors present a lower bound of （15 - √17）/8 ≈ 1.3596 on the competitive ratio of any deterministic on-line algorithm. This improves a previous result of 1.3473.
