Parallel machine scheduling problems, which are important discrete optimization problems, may occur in many applications. For example, load balancing in network communication channel assignment, parallel processing in...Parallel machine scheduling problems, which are important discrete optimization problems, may occur in many applications. For example, load balancing in network communication channel assignment, parallel processing in large-size computing, task arrangement in flexible manufacturing systems, etc., are multiprocessor scheduling problem. In the traditional parallel machine scheduling problems, it is assumed that the problems are considered in offline or online environment. But in practice, problems are often not really offline or online but somehow in-between. This means that, with respect to the online problem, some further information about the tasks is available, which allows the improvement of the performance of the best possible algorithms. Problems of this class are called semi-online ones. In this paper, the semi-online problem P2|decr|lp (p>1) is considered where jobs come in non-increasing order of their processing times and the objective is to minimize the sum of the lp norm of every machine’s load. It is shown that LS algorithm is optimal for any lp norm, which extends the results known in the literature. Furthermore, randomized lower bounds for the problems P2|online|lp and P2|decr|lp are presented.展开更多
In the classical multiprocessor scheduling problems, it is assumed that the problems are considered in off\|line or on\|line environment. But in practice, problems are often not really off\|line or on\|line but someh...In the classical multiprocessor scheduling problems, it is assumed that the problems are considered in off\|line or on\|line environment. But in practice, problems are often not really off\|line or on\|line but somehow in between. This means that, with respect to the on\|line problem, some further information about the tasks is available, which allows the improvement of the performance of the best possible algorithms. Problems of this class are called semi on\|line ones. The authors studied two semi on\|line multiprocessor scheduling problems, in which, the total processing time of all tasks is known in advance, or all processing times lie in a given interval. They proposed approximation algorithms for minimizing the makespan and analyzed their performance guarantee. The algorithms improve the known results for 3 or more processor cases in the literature.展开更多
Bionic optimisation is one of the most popular and efficient applications of bionic engineering. As there are many different approaches and terms being used, we try to come up with a structuring of the strategies and ...Bionic optimisation is one of the most popular and efficient applications of bionic engineering. As there are many different approaches and terms being used, we try to come up with a structuring of the strategies and compare the efficiency of the different methods. The methods mostly proposed in literature may be classified into evolutionary, particle swarm and artificial neural net optimisation. Some related classes have to be mentioned as the non-sexual fern optimisation and the response surfaces, which are close to the neuron nets. To come up with a measure of the efficiency that allows to take into account some of the published results the technical optimisation problems were derived from the ones given in literature. They deal with elastic studies of frame structures, as the computing time for each individual is very short. General proposals, which approach to use may not be given. It seems to be a good idea to learn about the applicability of the different methods at different problem classes and then do the optimisation according to these experiences. Furthermore in many cases there is some evidence that switching from one method to another improves the performance. Finally the identification of the exact position of the optimum by gradient methods is often more efficient than long random walks around local maxima.展开更多
基金Project supported by the National Natural Science Foundation of China (Nos. 10271110 10301028) and the Teaching and Research Award Program for Outstanding Young Teachers in Higher Education Institutions of MOE+2 种基金 China Project supported by the National Natural Science Foundation of China (Nos. 10271110 10301028) and the Teaching and Research Award Program for Outstanding Young Teachers in Higher Education Institutions of MOE China
文摘Parallel machine scheduling problems, which are important discrete optimization problems, may occur in many applications. For example, load balancing in network communication channel assignment, parallel processing in large-size computing, task arrangement in flexible manufacturing systems, etc., are multiprocessor scheduling problem. In the traditional parallel machine scheduling problems, it is assumed that the problems are considered in offline or online environment. But in practice, problems are often not really offline or online but somehow in-between. This means that, with respect to the online problem, some further information about the tasks is available, which allows the improvement of the performance of the best possible algorithms. Problems of this class are called semi-online ones. In this paper, the semi-online problem P2|decr|lp (p>1) is considered where jobs come in non-increasing order of their processing times and the objective is to minimize the sum of the lp norm of every machine’s load. It is shown that LS algorithm is optimal for any lp norm, which extends the results known in the literature. Furthermore, randomized lower bounds for the problems P2|online|lp and P2|decr|lp are presented.
文摘In the classical multiprocessor scheduling problems, it is assumed that the problems are considered in off\|line or on\|line environment. But in practice, problems are often not really off\|line or on\|line but somehow in between. This means that, with respect to the on\|line problem, some further information about the tasks is available, which allows the improvement of the performance of the best possible algorithms. Problems of this class are called semi on\|line ones. The authors studied two semi on\|line multiprocessor scheduling problems, in which, the total processing time of all tasks is known in advance, or all processing times lie in a given interval. They proposed approximation algorithms for minimizing the makespan and analyzed their performance guarantee. The algorithms improve the known results for 3 or more processor cases in the literature.
文摘Bionic optimisation is one of the most popular and efficient applications of bionic engineering. As there are many different approaches and terms being used, we try to come up with a structuring of the strategies and compare the efficiency of the different methods. The methods mostly proposed in literature may be classified into evolutionary, particle swarm and artificial neural net optimisation. Some related classes have to be mentioned as the non-sexual fern optimisation and the response surfaces, which are close to the neuron nets. To come up with a measure of the efficiency that allows to take into account some of the published results the technical optimisation problems were derived from the ones given in literature. They deal with elastic studies of frame structures, as the computing time for each individual is very short. General proposals, which approach to use may not be given. It seems to be a good idea to learn about the applicability of the different methods at different problem classes and then do the optimisation according to these experiences. Furthermore in many cases there is some evidence that switching from one method to another improves the performance. Finally the identification of the exact position of the optimum by gradient methods is often more efficient than long random walks around local maxima.
