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

An Approximation algorithm for Unrelated Parallel Machine Scheduling Under TOU Electricity Tariffs

IEEE TRANSACTIONS ON AUTOMATION SCIENCE AND ENGINEERING 2021年第2期18卷 743-756页

作者： Pei, Zhi Wan, Mingzhong Jiang, Zhong-Zhong Wang, Ziteng Dai, Xu Zhejiang Univ Technol Coll Mech Engn Hangzhou 310023 Peoples R China Northeastern Univ Sch Business Adm Shenyang 110167 Peoples R China Northeastern Univ Inst Behav & Serv Operat Management Shenyang 110167 Peoples R China Northeastern Univ Key Lab Data Analyt & Optimizat Smart Ind Minist Educ Shenyang 110167 Peoples R China Northern Illinois Univ Dept Ind & Syst Engn De Kalb IL 60115 USA

In an era of sustainable development, considerable emphasis has been put onto energy saving, environment friendly, and social welfare as well as productivity in the manufacturing sector. In this work, an unrelated parallel manufacturing setting with time-of-use (TOU) electricity price is explored, with an aim to reduce the electricity cost and increase productivity simultaneously. A nonlinear mathematical programming model is formulated to exploit the special structure of the scheduling problem, where the quadratic constraints are reformulated as second-order-cone (SOC) constraints, and several tailored cutting planes are introduced to further tighten the feasible region of the problem. Then, the original scheduling problem is transformed into several single-machine scheduling problems with TOU electricity price, which could be relaxed as a single-objective programming problem, and it could be solved rapidly via commercial solvers, such as CPLEX. Based on the optimal solution of the relaxed problem, an approximate algorithm is proposed, where a special rounding technique is employed to assign jobs to the unrelated parallel machines in a local search manner. Furthermore, a lower bound model is constructed by eliminating the nonpreemption constraint, and an iteration-based algorithm is devised to obtain the optimal solution of the lower bound problem. Meanwhile, a dispatch rule-based approach is proposed to provide an upper bound of the scheduling problem with TOU constraint. In the numerical analysis section, the proposed approximate algorithm is validated through extensive testing on various scales of instances, different emphasis on productivity and electricity price, and under two typical TOU electricity pricing policies. It is observed that the gap between the proposed approximate algorithm and CPLEX is mostly within 4%, and the lower/upper bound methods could obtain a relaxed/feasible solution within 0.01 s. Note to Practitioners-Energy saving together with prod

关键词： Job shop scheduling Parallel machines Approximation algorithms Single machine scheduling Pricing Productivity approximate algorithm cutting plane lower bound second-order-cone (SOC) time-of-use (TOU) unrelated parallel machine scheduling

来源：评论

学校读者我要写书评

暂无评论

Event-Participant and Incremental Planning over Event-Based Social Networks

引用

IEEE TRANSACTIONS ON KNOWLEDGE AND DATA ENGINEERING 2021年第2期33卷 474-488页

作者： Cheng, Yurong Yuan, Ye Chen, Lei Giraud-Carrier, Christophe Wang, Guoren Li, Boyang Sch Comp Sci & Technol Beijing Inst Technol Beijing 100811 Peoples R China Northeastern Univ Sch Comp Sci & Engn Qinhuangdao 066004 Hebei Peoples R China Hong Kong Univ Sci & Technol Dept Comp Sci & Engn Hong Kong Peoples R China Brigham Young Univ Dept Comp Sci Provo UT 84602 USA

In recent years, online Event Based Social Network (EBSN) platforms have become increasingly popular. One typical task of EBSN platforms is to help users make suitable and personalized plans for participating in different interesting social events. Existing techniques either ignore the minimum-participant requirement constraint for each event, which is crucially needed for some events to be held successfully, or assume that events would not change once announced. In this paper, we address the above inadequacies of existing EBSN techniques. We formally define the Global Event Planning with Constraints (GEPC) problem, and its incremental variant. Since these problems are NP-hard, and provide approximate solutions. Finally, we verify the effectiveness and efficiency of our proposed algorithms through extensive experiments over real and synthetic datasets.

关键词： Planning event-based social networks incremental planning approximate algorithm

来源：评论

学校读者我要写书评

暂无评论

Inconsistencies in bond market quotes: Is it the wrong model or the wrong data?

引用

JOURNAL OF COMPUTATIONAL SCIENCE 2018年 24卷 255-265页

作者： Lapshin, Victor Natl Res Univ Higher Sch Econ Moscow Russia

We use the linear programming approach to quantify quote inconsistencies in risk-free bond markets. We present an algorithm to identify whether an inconsistency is probably due to the insufficient framework flexibility, the insufficient data quality, or the non-homogeneity of the dataset. In the latter case we study the problem of filtering out some instruments so that the remaining dataset be homogeneous. We show that the traditional filtering approach performs unacceptably poor and propose new algorithms. We find that the bonds, which get mispriced the most by a fitting algorithm, surprisingly are not the bonds, which cause the inconsistencies. (C) 2017 Elsevier B.V. All rights reserved.

关键词： Quote inconsistency Data filtering Risk-free bonds Linear inequality system approximate algorithm

来源：评论

学校读者我要写书评

暂无评论

Numerical results for a fourth-order nonlinear wave equation of Kirchhoff type with a viscoelastic term

引用

NUMERICAL METHODS FOR PARTIAL DIFFERENTIAL EQUATIONS 2022年第5期38卷 1319-1344页

作者： Le Thi Mai Thanh Tran Trinh Manh Dung Nguyen Huu Nhan Le Thi Phuong Ngoc Nguyen Thanh Long Univ Sci Dept Math & Comp Sci Ho Chi Minh City Vietnam Vietnam Natl Univ 227 Nguyen Van Cu StrDist 5 Ho Chi Minh City Vietnam Nguyen Tat Thanh Univ Dept Math Ho Chi Minh City Vietnam Univ Khanh Hoa Dept Math Nha Trang City Vietnam

In this paper, numerical results for a fourth-order nonlinear wave equation of Kirchhoff type with a viscoelastic term are established. First, the existence and uniqueness of a solution is proved by applying the Faedo-Galerkin method and the weak compact method. Next, an algorithm to the initial boundary value problem for a nonlinear evolution equation of fourth order is studied where the spatial-variable discretization and time-variable discretization are constructed to approximate derivatives by the difference schemes. Finally, the numerical results are shown to present the errors of proposed algorithm. Simulations of the approximate solution and the exact solution are also visualized.

关键词： approximate algorithm difference schemes Faedo- Galerkin method numerical results the fourth-order wave equations

来源：评论

学校读者我要写书评

暂无评论

Fast and accurate algorithms for protein side-chain packing

引用

JOURNAL OF THE ACM 2006年第4期53卷 533-557页

作者： Xu, Jinbo Berger, Bonnie Toyota Technol Inst Chicago IL 60637 USA MIT Comp Sci & Artificial Intelligence Lab 32G594 Cambridge MA 02139 USA Univ Waterloo Sch Comp Sci Ming Lis Grp Waterloo ON N2L 3G1 Canada

This article studies the protein side-chain packing problem using the tree-decomposition of a protein structure. To obtain fast and accurate protein side-chain packing, protein structures are modeled using a geometric neighborhood graph, which can be easily decomposed into smaller blocks. Therefore, the side-chain assignment of the whole protein can be assembled from the assignment of the small blocks. Although we will show that the side-chain packing problem is still NP-hard, we can achieve a tree-decomposition-based globally optimal algorithm with time complexity of O(Nn(rot)(tw+1)) and several polynomial-time approximation schemes (PTAS), where N is the number of residues contained in the protein, n(rot) the average number of rotamers for each residue, and tw = O(N-2/3 log N) the treewidth of the protein structure graph. Experimental results indicate that after Goldstein dead-end elimination is conducted, n(rot) is very small and tw is equal to 3 or 4 most of the time. Based on the globally optimal algorithm, we developed a protein side-chain assignment program TreePack, which runs up to 90 times faster than SCWRL 3.0, a widely-used side-chain packing program, on some large test proteins in the SCWRL benchmark database and an average of five times faster on all the test proteins in this database. There are also some real-world instances that TreePack can solve but that SCWRL 3.0 cannot. The TreePack program is available at http://***/similar to jinbo/***.

关键词： algorithms theory protein side-chain packing tree decomposition approximate algorithm polynomial-time approximation scheme

来源：评论

学校读者我要写书评

暂无评论

In-Order Packet Scheduling in Optical Switch With Wavelength Division Multiplexing and Electronic Buffer

引用

IEEE TRANSACTIONS ON COMMUNICATIONS 2014年第6期62卷 1983-1994页

作者： Liu, Lin Zhang, Zhenghao Yang, Yuanyuan SUNY Stony Brook Dept Elect & Comp Engn Stony Brook NY 11794 USA Florida State Univ Dept Comp Sci Tallahassee FL 32306 USA

Optical switches are widely considered the most promising candidate to provide ultra-high speed interconnections for future communication and computing systems. Due to the difficulty in implementing an all-optical buffer, optical switches with electronic buffers have been proposed recently. Among these switches, the optical cut-through (OpCut) switch has the capability to achieve low latency and minimize optical-electronic-optical (O/E/O) conversions. We studied the packet-scheduling problem in single-wavelength OpCut switches in our previous work. In this paper, we consider the wavelength division multiplexed (WDM) case. While WDM makes much higher bandwidth possible, it also increases the complexity of the switch architecture, as well as packet scheduling. Our goal is to schedule as many as possible packets to the switch output in each time slot and to maintain the packet order at the same time. While we prove that such an optimal scheduling problem is NP-hard and inapproximable in polynomial time within any constant factor by reducing the set packing problem to it, we present an approximation algorithm that maintains packet order and approximates the optimal scheduling within a factor of root 2Nk with regard to the number of packets transmitted, where N is the switch size, and k is the number of wavelengths multiplexed on each fiber. This result is in line with the best known approximation algorithm for set packing problem. Based on the approximation algorithm, we also give practical schedulers that can be implemented in the fast optical switches. Simulation results show that the schedulers achieve close performance to the ideal WDM output-queued switch in terms of packet delay under various traffic models.

关键词： Optical switch optical interconnects electronic buffer packet scheduling approximate algorithm

来源：评论

学校读者我要写书评

暂无评论

An approximation algorithm for alignment of multiple sequences using motif discovery

引用

JOURNAL OF COMBINATORIAL OPTIMIZATION 1999年第2-3期3卷 247-275页

作者： Parida, L Floratos, A Rigoutsos, I IBM Corp Thomas J Watson Res Ctr Computat Biol Ctr Yorktown Heights NY 10598 USA

Given a set of N sequence, the Multiple Sequence Alignment problem is to align these N sequences, possibly with gaps, that brings out the best commonality of the N sequences. The quality of the alignment is usually measured by penalizing the mis-matches and gaps, and rewarding the matches with appropriate weight functions. However for larger values of N, additional constraints are required to give meaningful alignments. We identify a user-controlled parameter, an alignment number K (2 less than or equal to K less than or equal to N): this additional requirement constrains the alignment to have at least K sequences agree on a character, whenever possible, in the alignment. We identify a natural optimization problem for this approach called the K-MSA problem. We show that the problem is MAX SNP hard. We give a natural extension of this problem that incorporates "biological relevance" by using motifs (common patterns in the sequences) and give an approximation algorithm for this problem in terms of the motifs in the data. MUSCA is an implementation of this approach and our experimental results indicate that this approach is efficient, particularly on large numbers of long sequences, and gives good alignments when tested on biological data such as DNA and protein sequences.

关键词： multiple sequence alignment alignment number protein sequences motif discovery MAX SNP hard approximate algorithm set covering problem

来源：评论

学校读者我要写书评

暂无评论

Differentially private k-center problems

引用

OPTIMIZATION LETTERS 2024年第8期18卷 1791-1809页

作者： Yuan, Fan Xu, Dachuan Du, Donglei Li, Min Chinese Acad Sci Acad Math & Syst Sci Beijing 100190 Peoples R China Beijing Univ Technol Beijing Inst Sci & Engn Comp Beijing 100124 Peoples R China Univ New Brunswick Fac Management Fredericton NB E3B 5A3 Canada Shandong Normal Univ Sch Math & Stat Jinan 250014 Peoples R China

Data privacy has become one of the most important concerns in the big data era. Because of its broad applications in machine learning and data analysis, many algorithms and theoretical results have been established for privacy clustering problems, such as k-means and k-median problems with privacy protection. However, there is little work on privacy protection in k-center clustering. Our research focuses on the k-center problem, its distributed variant, and the distributed k-center problem under differential privacy constraints. These problems model the concept of safeguarding the privacy of individual input elements, with the integration of differential privacy aimed at ensuring the security of individual information during data processing and analysis. We propose three approximation algorithms for these problems, respectively, and achieve a constant factor approximation ratio.

关键词： Differentially privacy Clustering problem approximate algorithm Distributed k-center problem Distributed k-center problem with outliers

来源：评论

学校读者我要写书评

暂无评论

An analytic model for capacity planning of prisons in the Netherlands

引用

JOURNAL OF THE OPERATIONAL RESEARCH SOCIETY 2000年第11期51卷 1228-1237页

作者： Korporaal, R Ridder, A Kloprogge, P Dekker, R Erasmus Univ Inst Econometr NL-3000 DR Rotterdam Netherlands Vrije Univ Amsterdam Amsterdam Netherlands Point Log Syst Rotterdam Netherlands

In this paper we describe a decision support system developed to help in assessing the need for various types of prison cells. In particular we predict the probability that a criminal has to be sent home because of a shortage of cells. The problem is modelled through a queuing network with blocking after service. The main objective of our study is to describe our analytical method and an approximate algorithm to solve this network. Through simulation studies we evaluate our method. Both the analytic and the simulation tool are elements of the decision support system.

关键词： capacity planning prisons queuing network approximate algorithm

来源：评论

学校读者我要写书评

暂无评论

Pricing and allocation algorithm designs in dynamic ridesharing system

引用

THEORETICAL COMPUTER SCIENCE 2020年 803卷 94-104页

作者： Zhang, Chaoli Xie, Jiapeng Wu, Fan Gao, Xiaofeng Chen, Guihai Shanghai Jiao Tong Univ Shanghai Peoples R China

Traffic congestion and car pollution are becoming serious plagues nowadays. High travel cost brings a great burden to people and society. A ridesharing system mitigates traffic congestion and car pollution by allowing passengers to share their travel costs with others. Traditional ridesharing platforms usually require passengers to submit their plans in advance and then design schedules for the drivers who would like to offer a ride. Nowadays, with the development of the smartphone technology, dynamic ridesharing systems enable passengers request a car anytime and anywhere. This paper mainly considers the problems of how to allocate passengers to drivers, how to charge the passengers and how to design feasible schedules for the driver in such online environment. The allocation problem is modeled as an online weighted matching problem with the graph changing over time. Firstly, we give a fair pricing method which is easy to be understood and accepted by the passengers. We develop a greedy algorithm called LioMAx_GRE for the purpose of maximizing liquidity and an algorithm called UTIMAX for the purpose of maximizing utility. LIQMAx_GRE achieves a competitive ratio of 1/lambda+1, where lambda is the maximal number of passengers a car can take. In general, we prove that no online algorithm can have a good guarantee for the design goal of maximizing utility. Innovatively, UTIMAX considers not only the current maximal utility, but also the opportunity cost, which is the utility contributed by occupying a seat. It reflects the utility in the future and thus can be used to handle the difficulty in online design. We prove that, our algorithm has a competitive ratio of 1/3 in a special case. The schedule problem is NP-hard and we design a heuristic nearest neighbor algorithm to solve it. (C) 2019 Published by Elsevier B.V.

关键词： Ridesharing Online algorithm design approximate algorithm Dynamic system Pricing Allocation

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：