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

fully polynomial-time approximation scheme for single machine scheduling with proportional-linear deteriorating jobs

引用

ENGINEERING OPTIMIZATION 2019年第11期51卷 1938-1943页

作者： Zhao, Chuanli Hsu, Chou-Jung Shenyang Normal Univ Sch Math & Syst Sci Shenyang Peoples R China Nan Kai Univ Technol Dept Ind Engn & Management Caotun Nantou Taiwan

This article considers a single machine scheduling problem in which the processing time of a job is a linear increasing function of its starting time. The objective is to minimize the weighted number of tardy jobs. A ... 详细信息

关键词： Scheduling single machine deteriorating jobs fully polynomial-time approximation scheme

来源：评论

学校读者我要写书评

暂无评论

A fully polynomial time approximation scheme for scheduling on parallel identical two-stage openshops

引用

JOURNAL OF COMBINATORIAL OPTIMIZATION 2019年第2期37卷 668-684页

作者： Dong, Jianming Jin, Ruyan Hu, Jueliang Lin, Guohui Zhejiang Sci Tech Univ Dept Math Hangzhou 310018 Zhejiang Peoples R China Univ Alberta Dept Comp Sci Edmonton AB T6G 2E8 Canada

A two-stage openshop consists of a machine in the first stage and a machine in the second stage;a job processed on the two-stage openshop means it is processed non-preemptively by each of the two machines, in whichever order. We consider the scheduling problem at the availability of multiple parallel identical two-stage openshops, with the goal to minimize the makespan. By uncovering the important role of the critical job in the optimal schedule on a two-stage openshop, we propose to sort the jobs in the novel critical-job order, and use this order to design a pseudo-polynomial time dynamic programming exact algorithm to solve our scheduling problem with any fixed number of two-stage openshops. Afterwards, using the standard scaling technique, we develop the dynamic programming algorithm into a fully polynomial-time approximation scheme. These results improve previously proposed constant ratio approximation algorithms.

关键词： Scheduling Two-stage openshop Makespan Dynamic programming fully polynomial-time approximation scheme

来源：评论

学校读者我要写书评

暂无评论

Packing squares independently

引用

THEORETICAL COMPUTER SCIENCE 2025年 1024卷

作者： Wu, Wei Halman, Nir Hu, Yannan Yagiura, Mutsunori Shizuoka Univ Grad Sch Integrated Sci & Technol 3-5-1 JohokuChuo Ku Hamamatsu Shizuoka 4328561 Japan Nagoya Univ Grad Sch Informat Furo ChoChikusa Ku Nagoya Aichi 4648601 Japan Bar Ilan Univ Alexander Kofkin Fac Engn IL-5290002 Ramat Gan Israel Tokyo Univ Sci Dept Appl Math 1-3 KagurazakaShinjuku Ku Tokyo 1628601 Japan

Given a set of squares and a strip with bounded width and infinite height, we consider a square strip packaging problem, which we call the square independent packing problem (SIPP), to minimize the strip height so that all the squares are packed into independent cells separated by horizontal and vertical partitions. For the SIPP, we first investigate efficient solution representations and propose a compact representation that reduces the search space from Omega(n!) to O(2n), with n the number of given squares, while guaranteeing that there exists a solution representation that corresponds to an optimal solution. Based on the solution representation, we show that the problem is NP-hard. To solve the SIPP, we propose a dynamic programming method that can be extended to a fully polynomial-time approximation scheme (FPTAS). We also propose three mathematical programming formulations based on different solution representations and confirm their performance through computational experiments with a mathematical programming solver. Finally, we discuss several extensions that are relevant to practical applications.

关键词： Strip packing Dynamic programming Complexity fully polynomial-time approximation scheme

来源：评论

学校读者我要写书评

暂无评论

Scheduling with step learning and job rejection

引用

OPERATIONAL RESEARCH 2025年第1期25卷 1-18页

作者： Song, Jiaxin Miao, Cuixia Kong, Fanyu Qufu Normal Univ Sch Math Sci Qufu 273165 Shandong Peoples R China Nanjing Univ Informat Sci & Technol Sch Management Sci & Engn Nanjing 210044 Jiangsu Peoples R China Qufu Normal Univ Inst Operat Res Rizhao 276826 Shandong Peoples R China

This paper focuses on job scheduling with step learning and job rejection. The step learning model aims to reduce the processing time for jobs starting after a specific learning date. Our objective is to minimize the sum of the maximum completion time of accepted jobs and the total rejection penalty of rejected jobs. We examine special cases of processing times for both single-machine and parallel-machine scenarios. For the former, we design a pseudo-polynomial time algorithm, a 2-approximation algorithm and a fully polynomial-time approximation scheme (FPTAS) based on data rounding. For the latter, we present a fully polynomial-time approximation scheme achieved by trimming the state space. Additionally, for the general case of the single-machine problem, we propose a pseudo-polynomial time algorithm.

关键词： Scheduling Step learning Rejection penalty Pseudo-polynomial time algorithm fully polynomial-time approximation scheme approximation algorithm

来源：评论

学校读者我要写书评

暂无评论

An approximation algorithm for the two identical parallel machine problem under machine availability constraints

引用

JOURNAL OF INDUSTRIAL AND PRODUCTION ENGINEERING 2023年第1期40卷 54-67页

作者： Nguyen, Anh H. G. Sheen, Gwo-Ji Yeh, Yingchieh Natl Cent Univ Inst Ind Management Taoyuan Taiwan

This study addresses the scheduling problem of two identical parallel machines with the objective of minimizing the total completion time under the machine availability constraints. To the best of our knowledge, this study is the first to develop a fully polynomial-time approximation scheme (FPTAS), a solution method which has been neglected in past studies, to solve the studied problem. The FPTAS, which is based on a dynamic programming algorithm is developed by applying a trimming-the-state-space approach. Theoretical proofs of the error bound and the time complexity for the proposed FPTAS are also provided. The computational results indicate that the proposed FPTAS performs more efficiently than a dynamic programming algorithm in terms of both run time and problem size. The error bound of the FPTAS is demonstrated to be within the pre-specified error bound.

关键词： Parallel machine scheduling machine availability constraints dynamic programming algorithm fully polynomial-time approximation scheme trimming-the-state-space approach

来源：评论

学校读者我要写书评

暂无评论

Price Optimization Under the Finite-Mixture Logit Model

引用

MANAGEMENT SCIENCE 2022年第10期68卷 7480-7496页

作者： van de Geer, Ruben den Boer, Arnoud V. Beat Res BV NL-1012 WX Amsterdam Netherlands Univ Amsterdam Korteweg Vries Inst Math NL-1098 XG Amsterdam Netherlands Univ Amsterdam Amsterdam Business Sch NL-1018 TV Amsterdam Netherlands

We consider price optimization under the finite-mixture logit model. This model assumes that customers belong to one of a number of customer segments, where each customer segment chooses according to a multinomial logit model with segment-specific parameters. We reformulate the corresponding price optimization problem and develop a novel characterization. Leveraging this new characterization, we construct an algorithm that obtains prices at which the revenue is guaranteed to be at least (1- epsilon) times the maximum attainable revenue for any prespecified epsilon > 0. Existing global optimization methods require exponential time in the number of products to obtain such a result, which practically means that the prices of only a handful of products can be optimized. The running time of our algorithm, however, is exponential in the number of customer segments and only polynomial in the number of products. This is of great practical value, because in applications, the number of products can be very large, whereas it has been found in various contexts that a low number of segments is sufficient to capture customer heterogeneity appropriately. The results of our numerical study show that (i) ignoring customer segmentation can be detrimental for the obtained revenue, (ii) heuristics for optimization can get stuck in local optima, and (iii) our algorithm runs fast on a broad range of problem instances.

关键词： price optimization finite-mixture logit model fully polynomial-time approximation scheme

来源：评论

学校读者我要写书评

暂无评论

An approximation algorithm for a supply-chain scheduling problem with an assignable common due window and holding time

引用

JOURNAL OF COMBINATORIAL OPTIMIZATION 2022年第4期44卷 2167-2179页

作者： Zhang, Long Zhang, Yuzhong Bai, Qingguo Qufu Normal Univ Inst Operat Res Sch Management Rizhao 276826 Shandong Peoples R China

This paper studies single machine scheduling with batch deliveries, where a common due window for all jobs has to be determined, not given in advance. The objective is to minimize the overall cost for the process and delivery. Concretely, it includes the penalty of a job being early or tardy, the cost for holding and delivering a job, and the cost incurred by a late starting or a long duration of the common due window. Observing the NP-hardness, we provide an optimal algorithm of the problem and convert it to a fully polynomial time approximation scheme for a special case.

关键词： Supply chain scheduling Due window assignment Holding time approximation algorithm fully polynomial-time approximation scheme

来源：评论

学校读者我要写书评

暂无评论

approximation issues of fractional knapsack with penalties: a note

引用

4OR-A QUARTERLY JOURNAL OF OPERATIONS RESEARCH 2022年第2期20卷 209-216页

作者： Kovalev, Sergey INSEEC U Res Ctr INSEEC Sch Business & Econ 25 Rue Univ F-69007 Lyon France

Malaguti et al. introduce (Eur J Oper Res 273:874-888, 2019) the Fractional Knapsack Problem with Penalties, which is similar to the classical 0-1 Knapsack problem, except that each of the n variables associated with one of the n items can take any value from the interval [0, 1], and values other than 0 and 1 are penalized. They state that the problem is NP-hard in the ordinary sense as a generalization of the classical 0-1 knapsack problem and develop a fully polynomial-time approximation scheme for the case of non-negative non-decreasing profit functions. It is demonstrated that, unless P = NP, no polynomial-time approximation algorithm with any approximation ratio exists for the case of polynomially defined, polynomially computable, discontinuous and non-monotone penalty functions even if there is a single item. A fully polynomial-time approximation scheme which is roughly n times faster than the one of Malaguti et al. for the same case is also presented.

关键词： Knapsack problem Computational complexity fully polynomial-time approximation scheme

来源：评论

学校读者我要写书评

暂无评论

SINGLE-MACHINE PARETO-SCHEDULING WITH MULTIPLE WEIGHTING VECTORS FOR MINIMIZING THE TOTAL WEIGHTED LATE WORKS

引用

JOURNAL OF INDUSTRIAL AND MANAGEMENT OPTIMIZATION 2021年第1期19卷 456-471页

作者： Guo, Shuen Geng, Zhichao Yuan, Jinjiang Zhengzhou Univ Sch Math & Stat Zhengzhou 450001 Henan Peoples R China

In this paper, we study the single-machine Pareto-scheduling of jobs with multiple weighting vectors for minimizing the total weighted late works. Each weighting vector has its corresponding weighted late work. The goal of the problem is to find the Pareto-frontier for the weighted late works of the multiple weighting vectors. When the number of weighting vectors is arbitrary, it is implied in the literature that the problem is unary NP-hard. Then we concentrate on our research under the assumption that the number of weighting vectors is a constant. For this problem, we present a dynamic programming algorithm running in pseudo-polynomial time and a fully polynomial-time approximation scheme (FPTAS).

关键词： Key words and phrases Scheduling multiple weights weighted late work Pareto-frontier fully polynomial-time approximation scheme

来源：评论

学校读者我要写书评

暂无评论

Minimum shared-power edge cut

引用

NETWORKS 2020年第3期75卷 321-333页

作者： Cabello, Sergio Jain, Kshitij Lubiw, Anna Mondal, Debajyoti Univ Ljubljana Dept Math Ljubljana Slovenia IMFM Ljubljana Slovenia Borealis AI Waterloo ON Canada Univ Waterloo Sch Comp Sci Waterloo ON Canada Univ Saskatchewan Dept Comp Sci Saskatoon SK Canada

We introduce a problem called minimum shared-power edge cut (MSPEC). The input to the problem is an undirected edge-weighted graph with distinguished vertices s and t, and the goal is to find an s-t cut by assigning "powers" at the vertices and removing an edge if the sum of the powers at its endpoints is at least its weight. The objective is to minimize the sum of the assigned powers. MSPEC is a graph generalization of a barrier coverage problem in a wireless sensor network: given a set of unit disks with centers in a rectangle, what is the minimum total amount by which we must shrink the disks to permit an intruder to cross the rectangle undetected, that is, without entering any disk. This is a more sophisticated measure of barrier coverage than the minimum number of disks whose removal breaks the barrier. We develop a fully polynomial time approximation scheme for MSPEC. We give polynomial time algorithms for the special cases where the edge weights are uniform, or the power values are restricted to a bounded set. Although MSPEC is related to network flow and matching problems, its computational complexity (in P or NP-hard) remains open.

关键词： activation network barrier coverage fully polynomial-time approximation scheme s-t cut wireless network

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：