检索结果-内蒙古大学图书馆

A cross-entropy-based population-learning algorithm for discrete-continuous scheduling with continuous resource discretisation

引用

NEUROCOMPUTING 2010年第4-6期73卷 655-660页

作者： Jedrzejowicz, Piotr Skakovski, Aleksander Gdynia Maritime Univ Dept Nav PL-81225 Gdynia Poland Gdynia Maritime Univ Chair Informat Syst PL-81225 Gdynia Poland

The problem of scheduling nonpreemtable tasks on parallel identical machines under constraint on discrete resource and requiring, additionally, renewable continuous resource to minimize the schedule length is considered in the paper. A continuous resource is divisible continuously and is allocated to tasks from given intervals in amounts unknown in advance. Task processing rate depends on the allocated amount of the continuous resource. To eliminate time-consuming optimal continuous resource allocation, a problem Theta(Z) with continuous resource discretisation is introduced. Because Theta(Z) is NP-hard a population-learning algorithm (PLA2) is proposed to tackle the problem. PLA2 is a population-based approach which takes advantage of the features common to the social education system rather than to the evolutionary processes. The proposed approach is based on the idea of constructing the hybrid algorithm integrating different optimization techniques complementing each other and producing a synergetic effect. Experimental results proved that PLA2 excels known algorithms for solving the considered problem. (C) 2009 Elsevier B.V. All rights reserved.

关键词： discrete-continuous scheduling Evolutionary computation Population-learning algorithm

来源：评论

学校读者我要写书评

暂无评论

Tabu list management methods for a discrete-continuous scheduling problem

引用

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH 2002年第2期137卷 288-302页

作者： Józefowska, J Waligóra, G Weglarz, J Poznan Univ Tech Inst Comp Sci PL-60965 Poznan Poland

A problem of scheduling jobs on parallel, identical machines under an additional continuous resource to minimize the makespan is considered. Jobs are non-preemtable and independent and all are available at the start of the process. The total amount of the continuous resource available at a time is limited and the resource is a renewable one. Each job simultaneously requires for its processing a machine and an amount (unknown in advance) of the continuous resource. Processing rate of a job depends on the amount of the resource allotted to this job at a time. The problem is to find a sequence of jobs on machines and, simultaneously, a continuous resource allocation that minimizes the makespan. The tabu search (TS) metaheuristic is presented to attack the problem, Three different tabu list management methods: the tabu navigation method (TNM), the cancellation sequence method (CSM) and the reverse elimination method (REM) are discussed and examined. A computational experiment is described and the results obtained for the methods tested are compared to optimal solutions. A few conclusions and final remarks are presented. (C) 2002 Published by Elsevier Science B.V.

关键词： discrete-continuous scheduling makespan tabu search tabu navigation method cancellation sequence method reverse elimination method

来源：评论

学校读者我要写书评

暂无评论

Resource level minimization in the discrete-continuous scheduling

引用

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH 2010年第1期203卷 32-41页

作者： Gorczyca, Mateusz Janiak, Adam Wroclaw Univ Technol Inst Comp Sci Automat & Robot PL-50372 Wroclaw Poland

A discrete-continuous problem of non-preemptive task scheduling on identical parallel processors is considered. Tasks are described by means of a dynamic model, in which the speed of the task performance depends on the amount of a single continuously divisible renewable resource allotted to this task over time. An upper bound on the completion time of all the tasks is given. The criterion is to minimize the maximum resource consumption at each time instant, Le., the resource level. This problem has been observed in many industrial applications. where a continuously divisible resource such as gas, fuel, electric, hydraulic or pneumatic power, etc., has to be distributed among the processing units over time, and it affects their productivity. The problem consists of two interrelated subproblems: task sequencing on processors (discrete subproblem) and resource allocation among the tasks (continuous subproblem). An optimal resource allocation algorithm for a given sequence of tasks is presented and computationally tested. Furthermore, approximation algorithms are proposed, and their theoretical and experimental worst-case performances are analyzed. Computer experiments confirmed the efficiency of all the algorithms. (C) 2009 Elsevier B.V. All rights reserved.

关键词： scheduling discrete-continuous scheduling

来源：评论

学校读者我要写书评

暂无评论

Local search metaheuristics for discrete-continuous scheduling problems

引用

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH 1998年第2期107卷 354-370页

作者： Jozefowska, J Mika, M Rozycki, R Waligora, G Weglarz, J Poznan Univ Tech Inst Comp Sci PL-60965 Poznan Poland Poznan Supercomp & Networking Ctr Poznan Poland

Problems of scheduling nonpreemptable jobs which require simultaneously a machine from a set of parallel, identical machines and a continuous, renewable resource are considered. For each job there are known: its processing speed as a continuous, concave function of a continuous resource allotted at a time and its processing demand, The optimization criterion is the schedule length. The problem can be decomposed into two interrelated subproblems: (i) to sequence jobs on machines, and (ii) to find an optimal (continuous) resource allocation among jobs already sequenced. Problem (ii) can be formulated as a convex programming problem with linear constraints and solved using proper solvers. Thus, the problem remains to generate a set of all feasible sequences of jobs on machines (this guarantees finding an optimal schedule in the general case). However, the cardinality of this set grows exponentially with the number of jobs. Thus, we propose to use heuristic search methods defined on the space of feasible sequences. Three metaheuristics: tabu search (TS), simulated annealing (SA) and genetic algorithm (GA) have been implemented and compared computationally with a random sampling technique. The computational experiment has been carried out on an SGI PowerChallenge XL computer with 12 RISC R8000 processors. Some directions for further research have been pointed out. (C) 1998 Elsevier Science B.V. All rights reserved.

关键词： discrete-continuous scheduling heuristics simulated annealing tabu search genetic algorithms

来源：评论

学校读者我要写书评

暂无评论

On a methodology for discrete-continuous scheduling

引用

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH 1998年第2期107卷 338-353页

作者： Jozefowska, J Weglarz, J Poznan Tech Univ Inst Comp Sci PL-60965 Poznan Poland

discrete-continuous problems of scheduling nonpreemptable jobs on parallel machines are considered. The problems arise e.g. when jobs are assigned to multiple parallel processors driven by a common electric, hydraulic or pneumatic power source. Existing models have assumed job processing rates as a function of the number of jobs currently being processed, or equivalently the number of machines currently in operation, In this paper a more general model is proposed in which processing rates of a job assigned to a machine depend on the amount of a continuous, i.e. continuously divisible resource (e.g. power) allotted to this job at a time. Thus the problem consists of two interrelated subproblems: (i) to sequence jobs on machines, and (ii) to allocate the continuous resource among jobs already sequenced. We provide a comprehensive analysis of the problem. This includes properties of optimal schedules, efficiently (in particular analytically) solvable cases, formulations of the possibly simplest mathematical programming problems for finding optimal schedules in the general case, heuristics and the worst-case analysis. Although our objective function in this paper is to minimize makespan of a set of independent jobs, the presented methodology can be applied to other criteria, precedence-related jobs, and many resource types (apart from, or instead of machines). (C) 1998 Elsevier Science B.V. All rights reserved.

关键词： scheduling discrete-continuous scheduling

来源：评论

学校读者我要写书评

暂无评论

A cross-entropy-based population-learning algorithm for discrete-continuous scheduling with continuous resource discretisation

引用

12th International Conference on Knowledge-Based Intelligent Information and Engineering Systems

作者： Jedrzejowicz, Piotr Skakovski, Aleksander Gdynia Maritime Univ Dept Nav PL-81225 Gdynia Poland Gdynia Maritime Univ Chair Informat Syst PL-81225 Gdynia Poland

ISBN: (纸本)3540855629

关键词： discrete-continuous scheduling Evolutionary computation Population-learning algorithm

来源：评论

学校读者我要写书评

暂无评论

Island-based differential evolution algorithm for the discrete-continuous scheduling with continuous resource discretisation 18th

Island-based differential evolution algorithm for the discre...

引用

18th Annual International Conference on Knowledge-Based and Intelligent Information and Engineering Systems (KES)

作者： Jedrzejowicz, Piotr Skakovski, Aleksander Gdynia Maritime Univ Dept Nav Ul Morska 83F PL-81225 Gdynia Poland Gdynia Maritime Univ Chair Informat Syst PL-81225 Gdynia Poland

In the paper, we propose an island-based differential evolution algorithm (IBDEA) for solving the discrete-continuous scheduling problem (DCSP) with continuous resource discretisation - Theta(Z). The considered problem originates from DCSP, in which nonpreemtable tasks should be scheduled on parallel identical machines under constraint on discrete resource and requiring, additionally, a renewable continuous resource to minimize the schedule length. The continuous resource in DCSP is divisible continuously and is allocated to tasks from a given interval in amounts unknown in advance. Task processing rate depends on the allocated amount of the continuous resource. To eliminate time consuming optimal continuous resource allocation, an NP-hard problem Theta(Z) with continuous resource discretisation is introduced and sub-optimally solved by IBDEA. Experimental results show that IBDEA is able to find better solutions than an algorithm realizing only the differential evolution method and was able to improve best-known solutions to the considered problem. (C) 2014 Published by Elsevier B.V.

关键词： Differential Evolution method island model discrete-continuous scheduling discretisation

来源：评论

学校读者我要写书评

暂无评论

Population Learning with Differential Evolution for the discrete-continuous scheduling with continuous Resource Discretisation

Population Learning with Differential Evolution for the Disc...

引用

IEEE International Conference on Cybernetics (CYBCONF)

作者： Jedrzejowicz, Piotr Skakovski, Aleksander Gdynia Maritime Univ Chair Informat Syst Gdynia Poland Gdynia Maritime Univ Dept Navigat Gdynia Poland

ISBN: (纸本)9781467364690

In the paper, we consider a population learning algorithm denoted (PLA3), with the differential evolution method for solving the discrete-continuous scheduling problem (DCSP) with continuous resource discretisation - Theta(Z). The considered problem originates from DCSP, in which nonpreemtable tasks should be scheduled on parallel identical machines under constraint on discrete resource and requiring, additionally, a renewable continuous resource to minimize the schedule length. The continuous resource in DCSP is divisible continuously and is allocated to tasks from a given interval in amounts unknown in advance. Task processing rate depends on the allocated amount of the continuous resource. To eliminate time consuming optimal continuous resource allocation, an NP-hard problem Theta(Z) with continuous resource discretisation is introduced and sub-optimally solved by PLA3. Experimental results show that PLA3 was able to improve best-known solutions and excels its predecessor PLA2 in solving the considered problem.

关键词： Population Learning Algorithm Differential Evolution Method discrete-continuous scheduling Discretisation

来源：评论

学校读者我要写书评

暂无评论

A heuristic approach to allocating the continuous resource in discrete-continuous scheduling problems to minimize the makespan

引用

JOURNAL OF scheduling 2002年第6期5卷 487-499页

作者： Józefowska, J Mika, M Rózycki, R Waligóra, G Weglarz, J Poznan Univ Tech Inst Comp Sci PL-60965 Poznan Poland

A problem of scheduling jobs on parallel, identical machines under an additional continuous resource to minimize the makespan is considered. Jobs are non-preemtable and independent and all are available at the start of the process. The total amount of the continuous resource available at a time is limited and the resource is a renewable one. Each job simultaneously requires for its processing a machine and an amount (unknown in advance) of the continuous resource. The processing rate of a job depends on the amount of the resource allotted to this job at a time. The problem is to find a sequence of jobs on machines and, simultaneously, a continuous resource allocation which minimize the makespan. A heuristic approach to allocating the continuous resource is proposed. A tabu search algorithm to solve the considered problem is presented and the results for the algorithms with exact and heuristic procedures for allocating the continuous resource are compared on the basis of some computational experiments. Copyright (C) 2002 John Wiley Sons, Ltd.

关键词： discrete-continuous scheduling makespan mathematical programming problem heuristic tabu search

来源：评论

学校读者我要写书评

暂无评论

Island-based Differential Evolution Algorithm for the discrete-continuous scheduling with continuous Resource Discretisation

引用

Procedia Computer Science 2014年 35卷 111-117页

作者： Piotr Jędrzejowicz Aleksander Skakovski Chair of Information Systems Gdynia Maritime University ul. Morska 83F Gdynia 81-225 Poland Department of Navigation Gdynia Maritime University ul. Morska 83F Gdynia 81-225 Poland

In the paper, we propose an island-based differential evolution algorithm (IBDEA) for solving the discrete-continuous scheduling problem (DCSP) with continuous resource discretisation - Θ Z . The considered problem originates from DCSP, in which nonpreemtable tasks should be scheduled on parallel identical machines under constraint on discrete resource and requiring, additionally, a renewable continuous resource to minimize the schedule length. The continuous resource in DCSP is divisible continuously and is allocated to tasks from a given interval in amounts unknown in advance. Task processing rate depends on the allocated amount of the continuous resource. To eliminate time consuming optimal continuous resource allocation, an NP-hard problem Θ Z with continuous resource discretisation is introduced and sub-optimally solved by IBDEA. Experimental results show that IBDEA is able to find better solutions than an algorithm realizing only the differential evolution method and was able to improve best-known solutions to the considered problem.

关键词： Differential Evolution method island model discrete-continuous scheduling discretisation

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：