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

Efficient resource constrained scheduling Using Parallel Two-Phase Branch-and-Bound Heuristics

IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS 2017年第5期28卷 1299-1314页

作者： Chen, Mingsong Bao, Yongxiang Fu, Xin Pu, Geguang Wei, Tongquan East China Normal Univ Shanghai Key Lab Trustworthy Comp Shanghai 200062 Peoples R China Univ Houston Dept Elect & Comp Engn Houston TX 77204 USA

Branch-and-bound (B&B) approaches are widely investigated in resource constrained scheduling (RCS). However, due to the lack of approaches that can generate a tight schedule at the beginning of the search, B&B approaches usually start with a large initial search space, which makes the following search of an optimal schedule time-consuming. To address this problem, this paper proposes a parallel two-phase B&B approach that can drastically reduce the overall RCS time. This paper makes three major contributions: i) it proposes three partial-search heuristics that can quickly find a tight schedule to compact the initial search space;ii) it presents a two-phase search framework that supports the efficient parallel search of an optimal schedule;iii) it investigates various bound sharing and speculation techniques among collaborative tasks to further improve the parallel search performance at different search phases. The experimental results based on well-established benchmarks demonstrate the efficacy of our proposed approach.

关键词： resource constrained scheduling branch-and-bound parallel two-phase pruning high-level synthesis

来源：评论

学校读者我要写书评

暂无评论

Distributed optimisation method for multi-resource constrained scheduling in coal supply chains

引用

INTERNATIONAL JOURNAL OF PRODUCTION RESEARCH 2013年第9期51卷 2740-2759页

作者： Thomas, Anu Singh, Gaurav Krishnamoorthy, Mohan Venkateswaran, Jayendran Indian Inst Technol IITB Monash Res Acad Bombay 400076 Maharashtra India CSIRO Math Informat & Stat Clayton Vic 3168 Australia Indian Inst Technol Bombay 400076 Maharashtra India

We consider an integrated planning and scheduling problem motivated by the coal supply chains in Australia. The problem considers production planning of several independent mines. The mines need trains to complete delivery of coal by the arrival of ships at the terminal. The trains, on the other hand, are in limited supply and therefore the mines need to share this common resource. For this problem, we present a mixed integer programming formulation which minimises total weighted earliness, tardiness and operational costs. We also present a distributed algorithm based on the Lagrangian relaxation, which incorporates the volume and Wedelin algorithms. The strength of our distributed algorithm is demonstrated by an extensive computational experiment on several randomly generated instances.

关键词： distributed optimisation integrated scheduling coal logistics resource constrained scheduling Wedelin algorithm

来源：评论

学校读者我要写书评

暂无评论

Efficient resource constrained scheduling Using Parallel Structure-Aware Pruning Techniques

引用

IEEE TRANSACTIONS ON COMPUTERS 2016年第7期65卷 2059-2073页

作者： Chen, Mingsong Zhang, Xinqian Pu, Geguang Fu, Xin Mishra, Prabhat E China Normal Univ Shanghai Key Lab Trustworthy Comp Shanghai 200062 Peoples R China Univ Houston Dept Elect & Comp Engn Houston TX 77204 USA Univ Florida Dept Comp & Informat Sci & Engn Gainesville FL 32611 USA

Branch-and-bound approaches are promising in pruning fruitless search space during the resource constrained scheduling. However, such approaches only compare the estimated upper and lower bounds of an incomplete schedule to the length of the best feasible schedule at that iteration, which does not fully exploit the potential of the pruning during the search. Aiming to improve the performance of resource constrained scheduling, this paper proposes a parallel structure-aware pruning approach that can traverse the search space significantly faster than state-of-the-art branch-and-bound techniques. This paper makes three major contributions: i) it proposes an efficient pruning technique using the structural scheduling information of the obtained best feasible schedules;ii) it investigates how to perform parallel search to enable efficient multi-directional search and generation of effective fences by tuning the operation enumeration order;and iii) it presents a framework that supports the sharing of minimum upper-bound and fence information among different search tasks to enable efficient parallel structure-aware pruning. The experimental results demonstrate that our parallel pruning approach can drastically reduce the overall resource constrained scheduling time under a wide variety of resource constraints.

关键词： resource constrained scheduling branch-and-bound parallel pruning structure-aware pruning

来源：评论

学校读者我要写书评

暂无评论

Tight approximations for resource constrained scheduling and bin packing

引用

DISCRETE APPLIED MATHEMATICS 1997年第1-3期79卷 223-245页

作者： Srivastav, A Stangier, P UNIV COLOGNE ZENTRUM PARALLELES RECHNEND-50931 COLOGNEGERMANY

We consider the following resource constrained scheduling problem. We are given m identical processors, s resources R-1, ..., R-s with upper bounds b(1), ..., b(s), n independent jobs T-1, ..., T-n of unit length, where each job T-j has a start time r(j) is an element of N, requires one processor and an amount R-i(j) is an element of {0, 1} of resource R-i, i = 1, ..., s. The optimization problem is to schedule the jobs at discrete times in N subject to the processor, resource and start-time constraints so that the latest scheduling time is minimum. Multidimensional bin packing is a special case of this problem. resource constrained scheduling can be relaxed in a natural way when one allows the scheduling of fraction of jobs. Let C-opt (resp. C) be the minimum schedule size for the integral (resp. fractional scheduling). While the computation of C-opt is a NP-hard problem, C can be computed by linear programming in polynomial time. In case of zero start times Rock and Schmidt (1983) showed for the integral problem a polynomial-time approximation within (m/2)C-opt and de la Vega and Lueker (1981), improving a classical result of Garey et al. (1976), gave for every is an element of > 0 a linear time algorithm with an asymptotic approximation guarantee of (s + epsilon)C-opt. The main contributions of this paper include the first polynomial-time algorithm approximating C-opt for every epsilon is an element of(0, 1) within a factor of 1 + epsilon for instances with b(i) = Omega(epsilon(-2)log(Cs)) for all i and m = Omega(epsilon(-2) logC), and a proof that the achieved approximation under the given conditions is best possible, unless P = NP. Furthermore, in some cases we give for every fixed alpha > 1 a parallel 2 alpha-factor approximation algorithm.

关键词： resource constrained scheduling multidimensional bin packing randomized algorithm derandomization approximation algorithm chromatic index

来源：评论

学校读者我要写书评

暂无评论

A resource constrained scheduling problem with multiple independent producers and a single linking constraint: A coal supply chain example

引用

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH 2014年第3期236卷 946-956页

作者： Thomas, Anu Venkateswaran, Jayendran Singh, Gaurav Krishnamoorthy, Mohan Indian Inst Technol IITB Monash Res Acad Bombay 400076 Maharashtra India Indian Inst Technol Bombay 400076 Maharashtra India CSIRO Computat Informat Clayton Vic 3168 Australia

This paper examines a resource constrained production planning and scheduling problem motivated by the coal supply chain. In this problem, multiple independent producers are connected with a resource availability (or, linking) constraint. A general description of such problems is provided, before decomposing the problem into two levels. In the first level, we deal with production planning and in the second level, we deal with tactical resource scheduling. A real-world coal supply chain example is presented to anchor the approach. The overall problem can be formulated as an integrated mixed integer programming model which, in several cases, struggles to find even a feasible solution in reasonable amount of time. This paper discusses a distributed decision making approach based on column generation (CG). Computational experiments show that, the CG scheme has significant advantages over the integrated model and a Lagrangian relaxation scheme proposed by Thomas et al. (2013). This paper concludes with detailed discussions on the results and future research directions. (C) 2013 Elsevier B.V. All rights reserved.

关键词： Distributed decision making Coordinated scheduling resource constrained scheduling Column generation Job scheduling

来源：评论

学校读者我要写书评

暂无评论

OBJECT-ORIENTED INTERACTION IN resource constrained scheduling

引用

INFORMATION PROCESSING LETTERS 1990年第2期36卷 65-67页

作者： BIRO, M Comp. and Autom. Inst. Hung. Acad. Sci. Budapest Kende u 13-17 H-1111 Hungary

resource constrained scheduling is an area of operations research in which the availability of high resolution graphics hardware and software increases the demand for visual interactive modeling tools. Most practical resource constrained problems belong to the NP-complete class, so their solutions are usually sought using heuristic techniques. A discussion of ideas related to the object-oriented graphical representation of resource constrained schedules highlights the apparent link between resource constrained scheduling and 2-dimensional bin-packing theory. Two graph theoretical problems are formulated and shown to be useful when constructing a graphical representation for a schedule. The 2 graph theoretical problems are interval chromatic number and graph acyclic orientability with weighted diameter K.

关键词： Computational complexity computer graphics resource constrained scheduling two-dimensional bin-packing graph coloring

来源：评论

学校读者我要写书评

暂无评论

AN EXCHANGE HEURISTIC FOR resource constrained scheduling WITH CONSIDERATION GIVEN TO OPPORTUNITIES FOR PARALLEL-PROCESSING

引用

PRODUCTION PLANNING & CONTROL 1995年第2期6卷 140-150页

作者： YOO, J YANG, TY IGNIZIO, JP UNIV HOUSTON DEPT IND ENGNHOUSTONTX 77204 UNIV VIRGINIA DEPT SYST ENGNCHARLOTTESVILLEVA 22903

This paper describes a heuristic which produces efficient makespans for resource-constrained scheduling problems with parallel processing capabilities. This heuristic was initially developed for the scheduling of army battalion training exercises. The original heuristic has also been successfully applied to solve problems in project scheduling with limited resources, generalized job shop scheduling, and resource-constrained scheduling. The exchange heuristic requires an initial feasible solution upon which it improves the makespan by efficiently and systematically shuffling activities while maintaining feasibility. The method has recently been modified twice, termed the intelligent version and naive version, respectively, such that its ability to reduce the initial makespan is enhanced. In this study, it is shown that the heuristic, in both the modified intelligent version and original version, can be applied to resource-constrained scheduling problems with processing The performance of the intelligent version is compared to the original version in four different resource-constrained (parallel processing) problems of varied complexity. Results show that the modified heuristic produces significantly better makespans than the original heuristic when sufficient numbers of activities are involved in each precedence relationship. However there is a cost of increased CPU time associated with the improved makespan performance.

关键词： scheduling resource constrained scheduling PARALLEL PROCESSING HEURISTIC ALGORITHM NONLINEAR SEARCH TECHNIQUE

来源：评论

学校读者我要写书评

暂无评论

Efficient Two-Phase Approaches for Branch-and-Bound Style resource constrained scheduling

Efficient Two-Phase Approaches for Branch-and-Bound Style Re...

引用

27th International Conference on VLSI Design / 13th International Conference on Embedded Systems (VLSID)

作者： Chen, Mingsong Gu, Fan Zhou, Lei Pu, Geguang Liu, Xiao E China Normal Univ Shanghai Key Lab Trustworthy Comp Shanghai 200062 Peoples R China

ISBN: (纸本)9781479925124

In high-level synthesis (HLS), the resource constrained scheduling (RCS) tries to explore a time-minimum schedule for low-level hardware implementations under specific resource constraints. To achieve such an optimal schedule quickly, branch-and-bound (B&B) approaches are widely investigated to prune the fruitless search space. However, due to the lack of approaches that can obtain a tight initial feasible schedule, RCS generally starts with an incompact search space, which is not time-efficient. This paper proposes an efficient two-phase approach, which can quickly shrink the search space using a smaller upper-bound for efficient B&B RCS search. The experimental results demonstrate that our approach can drastically reduce the overall RCS time.

关键词： Branch-and-Bound High-Level Synthesis resource constrained scheduling

来源：评论

学校读者我要写书评

暂无评论

Evolutionary algorithms for the resource constrained scheduling problem

Evolutionary algorithms for the resource constrained schedul...

引用

30th International Conference on Information Technology Interfaces

作者： Frankola, Toni Golub, Marin Jakobovic, Domagoj Univ Zagreb Fac Elect Engn & Comp Zagreb 41000 Croatia

ISBN: (纸本)9789537138127

This paper investigates the use of evolutionary algorithms for solving resource constrained scheduling problem which belongs to the class of NP complete problems. The problem involves finding optimal sequence of activities with given resource constraints. Evolutionary algorithms used in this paper are genetic algorithms and genetic programming, for which adequate scheduling mechanisms are defined. Presented solutions are compared with existing heuristics or optimal results.

关键词： resource constrained scheduling priority scheduling genetic programming

来源：评论

学校读者我要写书评

暂无评论

A parallel approximation algorithm for resource constrained scheduling and bin packing 4th

A parallel approximation algorithm for resource constrained ...

引用

4th International Symposium on Solving Irregularly Structured Problems in Parallel (IRREGULAR 97)

作者： Srivastav, A Stangier, P Humboldt Univ Inst Informat D-10099 Berlin Germany Univ Cologne Zentrum Paralleles Rech D-50931 Cologne Germany

ISBN: (纸本)3540631380

(1) We consider the following classical resource constrained scheduling problem. Given m identical processors, s resources R-1,..., R-s with upper bounds b(1),..., b(s), n independent jobs T-1,...,T-n of unit length, where each job requires one processor and an amount R-i(j) is an element of {0, 1} of resource R-i, i = 1,..., s, the optimization problem is to schedule the jobs at discrete times in (1,..., n) subject to the processor and resource constraints so that the latest scheduling time is minimum. Note that multidimensional bin packing is a special case of this problem. We give for every fixed alpha > 1 the first parallel 2 alpha-factor approximation algorithm and show that there cannot exist a polynomial-time approximation algorithm achieving an approximation factor better than 4/3, unless P = NP.

关键词： resource constrained scheduling multidimensional bin packing derandomization logcn wise independence NC approximation algorithm

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：