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

A pseudo-polynomial time algorithm for solving the resource dependent assignment problem

DISCRETE APPLIED MATHEMATICS 2015年 182卷 115-121页

作者： Shabtay, Dvir Steiner, George Yedidsion, Liron Ben Gurion Univ Negev Dept Ind Engn & Management IL-84105 Beer Sheva Israel McMaster Univ DeGroote Sch Business Operat Management Area Hamilton ON Canada Technion Israel Inst Technol Fac Ind Engn & Management IL-32000 Haifa Israel

In this paper the resource dependent assignment problem (RDAP) is considered. In the RDAP the cost of assigning agent j to task i is a multiplication of task i's cost parameter by a cost function of agent j and the cost function of agent j is a linear function of the amount of resource allocated to the agent. A solution for the RDAP problem is defined by the assignment of agents to tasks and by a resource allocation to each agent. The quality of a solution is measured by two criteria. The first criterion is the total assignment cost and the second one is the total weighted resource consumption. Yedidsion et al. showed that the bicriteria variations of the problem are all NP-hard for any given set of task costs. However, whether these problems are strongly or ordinarily NP-hard remained an open question. In this paper we close this gap by providing pseudo-polynomial time algorithms for solving these problems. (C) 2013 Elsevier B.V. All rights reserved.

关键词： Assignment problem pseudo-polynomial time algorithm Resource allocation Bicriteria optimization

来源：评论

学校读者我要写书评

暂无评论

A pseudo-polynomial time algorithm for solving the resource dependent assignment problem

A pseudo-polynomial time algorithm for solving the resource ...

引用

8th International Colloquium on Graphs and Optimization (GO)

关键词： Assignment problem pseudo-polynomial time algorithm Resource allocation Bicriteria optimization

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

Efficient Folding algorithms for Convex Polyhedra

引用

DISCRETE & COMPUTATIONAL GEOMETRY 2023年第4期70卷 1499-1522页

作者： Kamata, Tonan Kadoguchi, Akira Horiyama, Takashi Uehara, Ryuhei Japan Adv Inst Sci & Technol JAIST Sch Informat Sci Nomi Ishikawa Japan Intelligent Vis & Image Syst IVIS Tokyo Japan Hokkaido Univ Fac Informat Sci & Technol Sapporo Hokkaido Japan

We investigate a folding problem that inquires whether a polygon P can be folded, without overlap or gaps, onto a polyhedron Q for given P and Q. An efficient algorithm for this problem when Q is a box was recently developed. We extend this idea to a class of convex polyhedra, which includes the five regular polyhedra, known as Platonic solids. Our algorithms use a common technique, which we call stamping. When we apply this technique, we use two special vertices shared by both P and Q (that is, there exist two vertices of P that are also vertices of Q). All convex polyhedra and their developments have such vertices, except a special class of tetrahedra, the tetramonohedra. We develop two algorithms for the problem as follows. For a given Q, when Q is not a tetramonohedron, we use the first algorithm which solves the folding problem for a certain class of convex polyhedra. On the other hand, if Q is a tetramonohedron, we use the second algorithm to handle this special case. Combining these algorithms, we can conclude that the folding problem can be solved in pseudo-polynomial time when Q is a polyhedron in a certain class of convex polyhedra that includes regular polyhedra.

关键词： Computational origami Folding problem pseudo-polynomial time algorithm Regular polyhedron (Platonic Stamping

来源：评论

学校读者我要写书评

暂无评论

Faster Minimization of Tardy Processing time on a Single Machine

引用

algorithmICA 2022年第5期84卷 1341-1356页

作者： Bringmann, Karl Fischer, Nick Hermelin, Danny Shabtay, Dvir Wellnitz, Philip Saarland Univ Saarland Informat Campus SIC Saarbrucken Germany Saarland Informat Campus SIC Max Planck Inst Informat Saarbrucken Germany Ben Gurion Univ Negev Dept Ind Engn & Management Beer Sheva Israel

This paper is concerned with the 1 parallel to Sigma p(j)U(j) problem, the problem of minimizing the total processing time of tardy jobs on a single machine. This is not only a fundamental scheduling problem, but also an important problem from a theoretical point of view as it generalizes the Subset Sum problem and is closely related to the 0/1-Knapsack problem. The problem is well-known to be NP-hard, but only in a weak sense, meaning it admits pseudo-polynomial time algorithms. The best known running time follows from the famous Lawler and Moore algorithm that solves a more general weighted version in O (P . n) time, where P is the total processing time of all n jobs in the input. This algorithm has been developed in the late 60s, and has yet to be improved to date. In this paper we develop two new algorithms for problem, each improving on Lawler and Moore's algorithm in a different scenario. Our first algorithm runs in (O) over tilde (P-7/4) time, and outperforms Lawler and Moore's algorithm in instances where n = (omega) over tilde (P-3/4). Our second algorithm runs in (O) over tilde (min {P . D-#, P+D}) time, where D-# is the number of different due dates in the instance, and D is the sum of all different due dates. This algorithm improves on Lawler and Moore's algorithm when n = (omega) over tilde (D-#) or n = (omega) over tilde (D/P). Further, it extends the known (O) over tilde ( P ) algorithm for the single due date special case of 1 parallel to Sigma p(j) U-j in a natural way. Both algorithms rely on basic primitive operations between sets of integers and vectors of integers for the speedup in their running times. The second algorithm relies on fast polynomial multiplication as its main engine, and can be easily extended to the case of a fixed number of machines. For the first algorithm we define a new "skewed" version of (max. min)-Convolution which is interesting in its own right.

关键词： Single machine scheduling Tardy processing time pseudo-polynomial time algorithm Fast polynomial multiplication (max, min)-Convolution

来源：评论

学校读者我要写书评

暂无评论

On the tractability of hard scheduling problems with generalized due-dates with respect to the number of different due-dates

引用

JOURNAL OF SCHEDULING 2022年第5期25卷 577-587页

作者： Mosheiov, Gur Oron, Daniel Shabtay, Dvir Hebrew Univ Jerusalem Sch Business Adm Jerusalem Israel Univ Sydney Sch Business Sydney NSW 2006 Australia Ben Gurion Univ Negev Dept Ind Engn & Management Beer Sheva Israel

We study two NP-hard single-machine scheduling problems with generalized due-dates. In such problems, due-dates are associated with positions in the job sequence rather than with jobs. Accordingly, the job that is assigned to position j in the job processing order (job sequence), is assigned with a predefined due-date, delta(j). In the first problem, the objective consists of finding a job schedule that minimizes the maximal absolute lateness, while in the second problem, we aim to maximize the weighted number of jobs completed exactly at their due-date. Both problems are known to be strongly NP-hard when the instance includes an arbitrary number of different due-dates. Our objective is to study the tractability of both problems with respect to the number of different due-dates in the instance, nu(d). We show that both problems remain NP-hard even when nu(d) = 2, and are solvable in pseudo-polynomial time when the value of nu(d) is upper bounded by a constant. To complement our results, we show that both problems are fixed parameterized tractable (FPT) when we combine the two parameters of number of different due-dates (nu(d)) and number of different processing times (nu(p)).

关键词： Scheduling Single machine Generalized due-dates NP-hard pseudo-polynomial time algorithm Parameterized complexity

来源：评论

学校读者我要写书评

暂无评论

Two-agent parallel-machine scheduling with rejection

引用

THEORETICAL COMPUTER SCIENCE 2017年 703卷 66-75页

作者： Li, Dawei Lu, Xiwen East China Univ Sci & Technol Sch Sci Shanghai 200237 Peoples R China

We study the two-agent scheduling with rejection on two parallel machines. There are two competing agents A and B with job families J(A) and J(B), respectively. A job in J(A) or J(B) is either rejected, in which case a rejection penalty will be incurred, or accepted and processed on one of the two parallel machines. The objective is to minimize the sum of the given objective function f(A) of the accepted A-jobs and the total rejection penalty of the rejected A-jobs subject to an upper bound on the sum of the given objective function f(B) of the accepted B-jobs and the total rejection penalty of the rejected B-jobs, where f(A) and f(B) are non-decreasing functions on the completion time of the accepted A-jobs and accepted B-jobs, respectively. We consider four scheduling problems associated with different combinations of the two agents' objective functions, f(A) = Sigma C-j(A) and f(B) is an element of {C-max(B), L-max(B), Sigma C-j(B), Sigma W(j)(B)Uj(B)}. When (f(A), f (B) ) = (Sigma C-j(A),C-max(B)), we provide two pseudo-polynomial time algorithms and a fully polynomial-time approximation scheme (FPTAS). For the other problems, we give a pseudo-polynomial time algorithm, respectively. (C) 2017 Elsevier B.V. All rights reserved.

关键词： Agent scheduling Parallel machines Rejection pseudo-polynomial time algorithm FPTAS

来源：评论

学校读者我要写书评

暂无评论

Proportionate flow-shop scheduling with rejection

引用

JOURNAL OF THE OPERATIONAL RESEARCH SOCIETY 2016年第5期67卷 752-769页

作者： Shabtay, Dvir Oron, Daniel Ben Gurion Univ Negev IL-84105 Beer Sheva Israel Univ Sydney Sydney NSW 2006 Australia

In many heavily loaded manufacturing systems, managers routinely make use of outsourcing options in order to maintain reasonable Quality of Service for customers. Thus, there is a strong need to provide tools for managers to economically coordinate sourcing and scheduling decisions. Our main aim is to provide such tools for an important set of flow-shop scheduling problems where rejection (outsourcing) is allowed and processing times are machine independent. Our scheduling problems are essentially bicriteria problems, which combine a scheduling objective and the total outsourcing cost. We study several problems which differ according to the scheduling criterion considered. Moreover, each problem is divided into four different variations depending on the way the two criteria are dealt with. For example, in one variation the two criteria are aggregated into a single objective function;in two other variations the aim consists of minimizing one criterion subject to ensuring that the value of the other criterion will not exceed a predefined threshold. From a theoretical point of view, a computational complexity classification is provided for all variations of the problems under consideration. Moreover, optimization algorithms have been constructed to solve all problem variations, and approximation schemes have been developed for solving hard variations. Those schemes enable managers to solve large instances of hard variations while controlling the maximal gap between the obtained solution and the (unknown) optimal solution.

关键词： scheduling with rejection proportionate flow-shop pseudo-polynomial time algorithm FPTAS

来源：评论

学校读者我要写书评

暂无评论

Approximation algorithm for the balanced 2-connected k-partition problem

引用

THEORETICAL COMPUTER SCIENCE 2016年第Part3期609卷 627-638页

作者： Wu, Di Zhang, Zhao Wu, Weili Xinjiang Univ Coll Math & Syst Sci Urumqi 830046 Xinjiang Peoples R China Zhejiang Normal Univ Coll Math Phys & Informat Engn Jinhua 321004 Zhejiang Peoples R China Univ Texas Dallas Dept Comp Sci Richardson TX 75080 USA

For two positive integers m, k and a connected graph G = (V, E) with a nonnegative vertex weight function w, the balanced m-connected k-partition problem, denoted as BCm P-k, is to find a partition of V into k disjoint nonempty vertex subsets (V-1, V-2,..., V-k) such that each G[V-i] (the subgraph of G induced by V-i) is m-connected, and min(1 <= i <= k){w(V-i)} is maximized. The optimal value of BCm P-k on graph G is denoted as beta(m)*(G, k), that is, beta(m)*(G, k) = max min(1 <= i <= k){w(V-i)}, where the maximum is taken over all m-connected k-partition of G. In this paper, we study the BC2 P-k problem on interval graphs, and obtain the following results. (1) For k = 2, a 4/3-approximation algorithm is given for BC2P2 on 4-connected interval graphs. (2) In the case that there exists a vertex v with weight at least W/k, where W is the total weight of the graph, we prove that the BC2Pk problem on a 2k-connected interval graph G can be reduced to the BC2Pk-1 problem on the (2k - 1)-connected interval graph G - v. In the case that every vertex has weight at most W/k, we prove a lower bound beta(2)* (G, k) >= W/(2k - 1) for 2k-connected interval graph G. (3) Assuming that weight w is integral, a pseudo-polynomial time algorithm is obtained. Combining this pseudo-polynomial time algorithm with the above lower bound, a fully polynomial time approximation scheme (FPTAS) is obtained for the BC2Pk problem on 2k-connected interval graphs. (C) 2015 Elsevier B.V. All rights reserved.

关键词： Balanced m-connected k-partition Interval graph pseudo-polynomial time algorithm FPTAS

来源：评论

学校读者我要写书评

暂无评论

Supply chain scheduling with receiving deadlines and non-linear penalty

引用

JOURNAL OF THE OPERATIONAL RESEARCH SOCIETY 2015年第3期66卷 380-391页

作者： Wang, Gang Lei, Lei Lee, Kangbok Kean Univ Union NJ 07083 USA Rutgers State Univ New Brunswick NJ 08903 USA CUNY New York NY 10021 USA

We study the operations scheduling problem with delivery deadlines in a three-stage supply chain process consisting of (1) heterogeneous suppliers, (2) capacitated processing centres (PCs), and (3) a network of business customers. The suppliers make and ship semi-finished products to the PCs where products are finalized and packaged before they are shipped to customers. Each business customer has an order quantity to fulfil and a specified delivery date, and the customer network has a required service level so that if the total quantity delivered to the network falls below a given targeted fill rate, a non-linear penalty will apply. Since the PCs are capacitated and both shipping and production operations are non-instantaneous, not all the customer orders may be fulfilled on time. The optimization problem is therefore to select a subset of customers whose orders can be fulfilled on time and a subset of suppliers to ensure the supplies to minimize the total cost, which includes processing cost, shipping cost, cost of unfilled orders (if any), and a non-linear penalty if the target service level is not met. The general version of this problem is difficult because of its combinatorial nature. In this paper, we solve a special case of this problem when the number of PCs equals one, and develop a dynamic programming-based algorithm that identifies the optimal subset of customer orders to be fulfilled under each given utilization level of the PC capacity. We then construct a cost function of a recursive form, and prove that the resulting search algorithm always converges to the optimal solution within pseudo-polynomial time. Two numerical examples are presented to test the computational performance of the proposed algorithm.

关键词： operations scheduling capacitated facilities deadline constraints dynamic programming pseudo-polynomial time algorithm

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：