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

Customer order scheduling to minimize total weighted completion time

OMEGA-INTERNATIONAL JOURNAL OF MANAGEMENT SCIENCE 2007年第5期35卷 623-626页

作者： Wang, Guoqing Cheng, T. C. Edwin Jinan Univ Dept Business Adm Guangzhou Peoples R China Hong Kong Polytech Univ Dept Logist Kowloon Hong Kong Peoples R China

In this paper we study the scheduling problem in which each customer order consists of several jobs of different types, which are to be processed on m facilities. Each facility is dedicated to the processing of only one type of jobs. All jobs of an order have to be delivered to the customer at the same time. The objective is to schedule all the orders to minimize the total weighted order completion time. While the problem has been shown to be unary NP-hard, we develop a heuristics to tackle the problem and analyze its worst-case performance. (c) 2005 Published by Elsevier Ltd.

关键词： customer order scheduling linear programming relaxation approximation algorithm

来源：评论

学校读者我要写书评

暂无评论

Improved Approximation for Directed Cut Problems 07

Improved Approximation for Directed Cut Problems

引用

39th Annual ACM Symposium on Theory of Computing

作者： Agarwal, Amit Alon, Noga Charikar, Moses Princeton Univ Dept Comp Sci Princeton NJ 08540 USA

ISBN: (纸本)9781595936318

We present improved approximation algorithms for directed multicut and directed sparsest cut. The current best known approximation ratio for these problems is O(n(1/2)). We obtain an (O) over tilde (n(11/23))-approximation. Our algorithm works with the natural LP relaxation used in prior work. We use a randomized rounding algorithm with a more sophisticated charging scheme and analysis to obtain Our improvement. This also implies a (O) over tilde (n(11/23)) upper bound on the ratio between the maximum multicommodity flow kind minimum multicut in directed graphs.

关键词： approximation algorithm directed multicut directed sparsest cut linear programming relaxation

来源：评论

学校读者我要写书评

暂无评论

Approximating the two-level facility location problem via a quasi-greedy approach

引用

MATHEMATICAL programming 2006年第1期108卷 159-176页

作者： Zhang, Jiawei NYU Stern Sch Business IOMS Operat Management New York NY 10012 USA

We propose a quasi-greedy algorithm for approximating the classical uncapacitated 2-level facility location problem (2-LFLP). Our algorithm, unlike the standard greedy algorithm, selects a sub-optimal candidate at each step. It also relates the minimization 2-LFLP problem, in an interesting way, to the maximization version of the single level facility location problem. Another feature of our algorithm is that it combines the technique of randomized rounding with that of dual fitting. This new approach enables us to approximate the metric 2-LFLP in polynomial time with a ratio of 1.77, a significant improvement on the previously known approximation ratios. Moreover, our approach results in a local improvement procedure for the 2-LFLP, which is useful in improving the approximation guarantees for several other multi-level facility location problems. An additional result of our approach is an O(ln (n))-approximation algorithm for the non-metric 2-LFLP, where n is the number of clients. This is the first non-trivial approximation for a non-metric multi-level facility location problem.

关键词： two-level facility location approximation algorithm linear programming relaxation quasi-greedy approach

来源：评论

学校读者我要写书评

暂无评论

Approximation bounds for a general class of precedence constrained parallel machine scheduling problems

引用

SIAM JOURNAL ON COMPUTING 2006年第5期35卷 1241-1253页

作者： Queyranne, M Schulz, AS Univ British Columbia Sauder Sch Business Vancouver BC V6T 1Z2 Canada MIT Alfred P Sloan Sch Management Cambridge MA 02139 USA

An important class of scheduling problems concerns parallel machines and precedence constraints. We consider precedence delays, which associate with each precedence constraint a certain amount of time that must elapse between the completion and start times of the corresponding jobs. Together with ordinary precedence constraints, release dates and delivery times can be modeled in this manner. We present a 4-approximation algorithm for the total weighted completion time objective for this general class of problems. The algorithm is a rather simple form of list scheduling. The list is in order of job midpoints derived from a linear programming relaxation. Our analysis unifies and simplifies that of a number of special cases heretofore separately studied, while actually improving many of the former approximation results.

关键词： approximation algorithm linear programming relaxation performance guarantee precedence constraints scheduling

来源：评论

学校读者我要写书评

暂无评论

Approximating the two-level facility location problem via a quasi-greedy approach

Approximating the two-level facility location problem via a ...

引用

15th ACM-SIAM Symposium on Discrete Algorithms

作者： Zhang, Jiawei NYU Stern Sch Business IOMS Operat Management New York NY 10012 USA

关键词： two-level facility location approximation algorithm linear programming relaxation quasi-greedy approach

来源：评论

学校读者我要写书评

暂无评论

A novel LP-based Neighborhood search for general integer programs

A novel LP-based Neighborhood search for general integer pro...

引用

10th World Multi-Conference on Systemics, Cybernetics and Informatics/12th International Conference on Information Systems Analysis and Synthesis

作者： Zhang, Xinhui Hill, Raymond R. Wright State Univ Dept Biomed Ind & Human Factors Engn Dayton OH 45435 USA

ISBN: (纸本)9789806560710

This paper presents a novel solution methodology for general integer programs using a neighborhood search based on linear programming relaxation. The algorithm generates multiple linear programming solutions of maximal difference and uses them as targets for a neighborhood search to locate high-quality integer solutions. While multiple diverse solutions provide a good coverage of the solution landscape, the neighborhood search reduces the computational burden in searching for good integer solutions. Preliminary results on a set of benchmark problems have shown that the algorithm is computationally effective, providing multiple high-quality solutions at faster convergence rates than state-of-the-art commercial integer program solvers.

关键词： linear programming relaxation neighborhood search local branching integer programming

来源：评论

学校读者我要写书评

暂无评论

Single-machine scheduling with precedence constraints

引用

MATHEMATICS OF OPERATIONS RESEARCH 2005年第4期30卷 1005-1021页

作者： Correa, JR Schulz, AS Univ Adolfo Ibanez Sch Business Santiago Chile MIT Alfred P Sloan Sch Management Cambridge MA 02139 USA

We discuss the problem of sequencing precedence-constrained jobs on a single machine to minimize the average weighted completion time. This problem has attracted much attention in the mathematical programming community since Sidney's pioneering work in 1975 (Sidney, J. B. 1975. Decomposition algorithms for single machine scheduling with precedence relations and deferral costs. Operations Research 23 283-298). We look at the problem from a polyhedral perspective and uncover a relation between Sidney's decomposition theorem and different linear programming relaxations. More specifically, we present a generalization of Sidney's result, which particularly allows us to reason that virtually all known 2-approximation algorithms are consistent with his decomposition. Moreover, we establish a connection between the single-machine scheduling problem and the vertex cover problem. Indeed, in the special case of series-parallel precedence constraints, we prove that the sequencing problem can be seen 'as a special case of the vertex cover problem. We also. argue that this result is true for general precedence constraints if one can show that a certain integer program represents a valid formulation of the sequencing problem. Finally, we give a 3/2-approximation algorithm for two-dimensional partial orders, and we also provide a characterization of the active inequalities of a linear programming relaxation in completion time variables.

关键词： linear ordering scheduling vertex cover linear programming relaxation integer programming formulation approximation algorithm partial order

来源：评论

学校读者我要写书评

暂无评论

Approximation algorithms for the 0-extension problem

引用

SIAM JOURNAL ON COMPUTING 2004年第2期34卷 358-372页

作者： Calinescu, G Karloff, H Rabani, Y IIT Dept Comp Sci Chicago IL 60616 USA AT&T Labs Res Florham Pk NJ 07932 USA Technion Israel Inst Technol Dept Comp Sci IL-32000 Haifa Israel

In the 0-extension problem, we are given a weighted graph with some nodes marked as terminals and a semimetric on the set of terminals. Our goal is to assign the rest of the nodes to terminals so as to minimize the sum, over all edges, of the product of the edge's weight and the distance between the terminals to which its endpoints are assigned. This problem generalizes the multiway cut problem of Dahlhaus et al. [SIAM J. Comput., 23 (1994), pp. 864-894] and is closely related to the metric labeling problem introduced by Kleinberg and Tardos [Proceedings of the 40th IEEE Annual Symposium on Foundations of Computer Science, New York, 1999, pp. 14-23]. We present approximation algorithms for 0-Extension. In arbitrary graphs, we present a O(log k)-approximation algorithm, k being the number of terminals. We also give O(1)-approximation guarantees for weighted planar graphs. Our results are based on a natural metric relaxation of the problem previously considered by Karzanov [European J. Combin., 19 ( 1998), pp. 71-101]. It is similar in flavor to the linear programming relaxation of Garg, Vazirani, and Yannakakis [ SIAM J. Comput., 25 (1996), pp. 235-251] for the multicut problem, and similar to relaxations for other graph partitioning problems. We prove that the integrality ratio of the metric relaxation is at least c root lg k for a positive c for infinitely many k. Our results improve some of the results of Kleinberg and Tardos, and they further our understanding on how to use metric relaxations.

关键词： metric space approximation algorithm linear programming relaxation graph partitioning

来源：评论

学校读者我要写书评

暂无评论

Strong lower bounds for the prize collecting Steiner problem in graphs

引用

DISCRETE APPLIED MATHEMATICS 2004年第1-3期141卷 277-294页

作者： Lucena, A Resende, MGC Univ Fed Rio de Janeiro Dept Adm BR-22290240 Rio De Janeiro RJ Brazil AT&T Labs Res Internet & Network Syst Res Ctr Florham Pk NJ 07932 USA

In this paper, we present an integer programming formulation of the prize collecting Steiner problem in graphs (PCSPG) and describe an algorithm to obtain lower bounds for the problem. The algorithm is based on polyhedral cutting planes and is initiated with tests that attempt to reduce the size of the input graph. Computational experiments were carried out to evaluate the strength of the formulation through its linear programming relaxation. On 96 out of the 114 instances tested, integer solutions were found (thus generating optimal PCSPG solutions). (C) 2003 Elsevier B.V. All rights reserved.

关键词： prize collecting Steiner problem in graphs linear programming relaxation lower bound

来源：评论

学校读者我要写书评

暂无评论

Strong lower bounds for the prize collecting Steiner problem in graphs

Strong lower bounds for the prize collecting Steiner problem...

引用

Brazilian Symposium on Graphs, Algorithms and Combinatorics

作者： Lucena, A Resende, MGC Univ Fed Rio de Janeiro Dept Adm BR-22290240 Rio De Janeiro RJ Brazil AT&T Labs Res Internet & Network Syst Res Ctr Florham Pk NJ 07932 USA

关键词： prize collecting Steiner problem in graphs linear programming relaxation lower bound

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：