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

Integrated pricing and production scheduling of multiple customized products with a common base product

IISE TRANSACTIONS 2019年第12期51卷 1383-1401页

作者： Yue, Qing Chen, Zhi-Long Wan, Guohua Shanghai Univ Int Business & Econ Management Sch Shanghai Peoples R China Univ Maryland Robert H Smith Sch Business College Pk MD 20742 USA Shanghai Jiao Tong Univ Antai Coll Econ & Management Shanghai Peoples R China

Make-To-Order (MTO) is a popular production strategy commonly used by manufacturers selling customized products. Dynamic pricing is a popular tactical tool commonly used by sellers to match supply with demand when there is a limited capacity and high demand uncertainty over time. In this article, we consider joint pricing and production scheduling decisions faced by a manufacturer that uses an MTO strategy to sell a number of customized products made from a common base product. At the beginning of each period in a planning horizon, the manufacturer sets the price of the base product, which in turn sets the prices for the customized products accordingly. Given the prices, orders for the products arrive. In each period, together with the pricing decision, the manufacturer needs to make a production scheduling decision for processing accepted orders on a single production line. The manufacturer's objective is to maximize the total revenue of the processed orders minus a scheduling penalty over the planning horizon. Three specific problems with different order acceptance rules and objective functions are studied. In the first problem, the manufacturer has to accept all the incoming orders and treats the total weighted completion time of the orders as a part of the objective function. In the second problem, the manufacturer has to accept all incoming orders, but is allowed to complete some orders after their due dates with tardiness penalties. In the third problem, the manufacturer may reject some incoming orders, but must complete all the accepted orders by their due dates. We show that all these problems are NP-hard, propose optimal pseudo-polynomial-time dynamic programming algorithms and fully-polynomial-time approximation schemes for solving these problems, and conduct computational experiments to show the performance of the proposed algorithms. Furthermore, we derive several managerial insights through computational experiments.

关键词： Production scheduling dynamic pricing make-to-order dynamic programming fully polynomial time approximation scheme

来源：评论

学校读者我要写书评

暂无评论

Nonconvex piecewise linear knapsack problems

引用

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH 2009年第1期192卷 56-68页

作者： Kameshwaran, S. Narahari, Y. Indian Inst Sci Dept Comp Sci & Automat Elect Commerce Lab Bangalore 560012 Karnataka India Indian Sch Business Ctr Global Logist & Mfg Strategies Hyderabad 500032 Andhra Pradesh India

This paper considers the minimization version of a class of nonconvex knapsack problems with piecewise linear cost structure. The items to be included in the knapsack have a divisible quantity and a cost function. An item can be included partially ill the given quantity range and the cost is a nonconvex piecewise linear function of quantity. Given a demand, the optimization problem is to choose an optimal quantity for each item such that the demand is satisfied and the total cost is minimized. This problem and its close variants are encountered in manufacturing planning, supply chain design, volume discount procurement auctions, and many other contemporary applications. Two separate mixed integer linear programming formulations of this problem are proposed and are compared with existing formulations. Motivated by different scenarios in which the problem is useful, the following algorithms are developed: (1) a fast polynomial time, near-optimal heuristic using convex envelopes;(2) exact pseudo-polynomial time dynamic programming algorithms;(3) a 2-approximation algorithm;and (4) a fully polynomial time approximation scheme. A comprehensive test suite is developed to generate representative problem instances with different characteristics. Extensive computational experiments show that the proposed formulations and algorithms are faster than the existing techniques. (C) 2007 Elsevier B.V. All rights reserved.

关键词： Piecewise linear knapsack problem Precedence constrained knapsack problem Multiple choice knapsack problem Linear relaxation Dynamic programming Convex envelope approximation algorithm fully polynomial time approximation scheme

来源：评论

学校读者我要写书评

暂无评论

Two-agent scheduling with linear resource-dependent processing times

引用

NAVAL RESEARCH LOGISTICS 2020年第7期67卷 573-591页

作者： Wang, Dujuan Yu, Yugang Qiu, Huaxin Yin, Yunqiang Cheng, T. C. E. Sichuan Univ Sch Business Chengdu Peoples R China Univ Sci & Technol China Sch Management Hefei Peoples R China Dalian Univ Technol Sch Management Sci & Engn Dalian Peoples R China Univ Elect Sci & Technol China Sch Management & Econ Chengdu 611731 Peoples R China Hong Kong Polytech Univ Dept Logist & Maritime Studies Kowloon Hong Kong Peoples R China

This paper considers a two-agent scheduling problem with linear resource-dependent processing times, in which each agent has a set of jobs that compete with that of the other agent for the use of a common processing machine, and each agent aims to minimize the weighted number of its tardy jobs. To meet the due date requirements of the jobs of the two agents, additional amounts of a common resource, which may be in discrete or continuous quantities, can be allocated to the processing of the jobs to compress their processing durations. The actual processing time of a job is a linear function of the amount of the resource allocated to it. The objective is to determine the optimal job sequence and resource allocation strategy so as to minimize the weighted number of tardy jobs of one agent, while keeping the weighted number of tardy jobs of the other agent, and the total resource consumption cost within their respective predetermined limits. It is shown that the problem isNP-hard in the ordinary sense, and there does not exist a polynomial-time approximation algorithm with performance ratio unlessP=NP;however it admits a relaxed fully polynomial time approximation scheme. A proximal bundle algorithm based on Lagrangian relaxation is also presented to solve the problem approximately. To speed up convergence and produce sharp bounds, enhancement strategies including the design of a Tabu search algorithm and integration of a Lagrangian recovery heuristic into the algorithm are devised. Extensive numerical studies are conducted to assess the effectiveness and efficiency of the proposed algorithms.

关键词： fully polynomial time approximation scheme proximal bundle algorithm resource allocation two-agent scheduling

来源：评论

学校读者我要写书评

暂无评论

Parallel-Batch Scheduling With Deterioration and Group Technology

引用

IEEE ACCESS 2019年 7卷 119082-119086页

作者： Miao, Cuixia Qufu Normal Univ Sch Math Sci Qufu 273165 Shandong Peoples R China

Parallel-batch scheduling with deterioration and group technology is a modern scheduling model, in which the jobs are classified into groups by the similar production requirements, and setup time, which may be fixed or deterioration function of the starting time, is required between jobs of different groups. We consider this scheduling to minimize the makespan in this paper. Based on fully Batching Longest Deteriorating Rate, we show that our two single-machine scheduling problems are solved in polynomial time. Procedure Partition (A, F, rho) is useful for designing algorithm in combinational optimization. We use this procedure to present fully polynomial time approximation schemes for our two parallel-machine scheduling problems, which is the best algorithm as its' objective value can be fully close to the optimal value.

关键词： Parallel-batch scheduling deterioration group technology fully polynomial time approximation scheme

来源：评论

学校读者我要写书评

暂无评论

Approximate solution of a profit maximization constrained virtual business planning problem

引用

OMEGA-INTERNATIONAL JOURNAL OF MANAGEMENT SCIENCE 2015年第PartB期57卷 212-216页

作者： Dolgui, Alexandre Kovalev, Sergey Pesch, Erwin Ecole Mines St Etienne CNRS LIMOS UMR 6158 F-42023 St Etienne 2 France ECE Lyon INSEEC Business Sch F-69001 Lyon France Univ Siegen Inst Informat Syst D-57068 Siegen Germany

A virtual business problem is studied, in which a company-contractor outsources production to specialized subcontractors. Finances of the contractor and resource capacities of subcontractors are limited. The objective is to select subcontractors and distribute a part of the demanded production among them so that the profit of the contractor is maximized. A generalization of the knapsack problem, called Knapsack-of-Knapsacks (K-of-K), is used to model this situation, in which items have to be packed into small knapsacks and small knapsacks have to be packed into a large knapsack. A fully polynomial time approximation scheme is developed to solve the problem K-of-K. (C) 2015 Elsevier Ltd. All rights reserved.

关键词： Virtual business planning Knapsack problem Dynamic programming fully polynomial time approximation scheme

来源：评论

学校读者我要写书评

暂无评论

A simple FPTAS for a single-item capacitated economic lot-sizing problem with a monotone cost structure

引用

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH 2010年第2期200卷 621-624页

作者： Ng, C. T. Kovalyov, Mikhail Y. Cheng, T. C. E. Hong Kong Polytech Univ Dept Logist & Maritime Studies Kowloon Hong Kong Peoples R China Belarusian Stare Univ Minsk 220030 BELARUS Natl Acad Sci Belarus United Inst Informat Problems Minsk 220030 BELARUS

The single-item capacitated economic lot-sizing (CELS) problem is a fundamental problem of production and inventory management. The first fully polynomial approximation scheme (FPTAS) for this problem with concave cost functions was developed by Van Hoesel and Wagelmans [C.P.M. Van Hoesel, A.P.M. Wagelmans, fully polynomial approximation schemes for single-item capacitated economic lot-sizing problems, Mathematics of Operations Research 26 (2001) 339-357]. Chubanov et al. [S. Chubanov. M.Y. Kovalyov, E. Pesch, An FPTAS for a single-item capacitated economic lot-sizing problem, Mathematical Programming Series A 106 (2006) 453-466] later presented a sophisticated FPTAS for the general case of the CEUS problem with a monotone cost structure. In this paper, we present a better FPTAS for this case. The ideas and presentation of our FPTAS are simple and straightforward. Its running time is about n(4)/epsilon(2) times faster than that of Chubanov et al. [5], where n is the number of production periods and epsilon is the anticipated relative error of the approximate solution. (C) 2009 Elsevier B.V. All rights reserved.

关键词： Capacitated economic lot-sizing problem fully polynomial time approximation scheme

来源：评论

学校读者我要写书评

暂无评论

Due window assignment and scheduling on parallel machines: a FPTAS for a bottleneck criterion

引用

BULLETIN OF THE POLISH ACADEMY OF SCIENCES-TECHNICAL SCIENCES 2014年第4期62卷 805-808页

作者： Janiak, A. Janiak, W. Kovalyov, M. Y. Polish Acad Sci Syst Res Inst PL-01447 Warsaw Poland Int Univ Logist & Transport Wroclaw PL-51168 Wroclaw Poland Natl Acad Sci Belarus United Inst Informat Problems Minsk BELARUS

A fully polynomial time approximation scheme (FPTAS) with run time O(n(m)/epsilon(m-1)) is developed for a problem which combines common due window assignment and scheduling n jobs on m identical parallel machines. The problem criterion is bottleneck (min-max) such that the maximum cost, which includes job earliness, job tardiness and due window size costs, is minimized.

关键词： fully polynomial time approximation scheme scheduling due window assignment

来源：评论

学校读者我要写书评

暂无评论

A two stage scheduling with transportation and batching

引用

INFORMATION PROCESSING LETTERS 2012年第19期112卷 728-731页

作者： Zhu, Hongli Beihang Univ Sch Econ & Management Beijing 100191 Peoples R China

We investigate a two stage scheduling problem with transportation and batching, in which jobs are transported from holding area to the batching machine by in vehicles in the first stage. Each vehicle can transport only one job at a time. As the job is big and heavy in the steel industry, it is reasonable to assume that the vehicle capacity is unit. In the second stage, the botching machine can process up to a fixed number of jobs as a batch simultaneously. Each bath to be processed occurs a processing cost. Our objective is to minimize the makespan and processing cost. For m = 1, we present a polynomial time algorithm. For the general problem we prove that it is NP-hard in ordinary sense. Then we provide a pseudo-polynomial time algorithm and obtain a fully polynomial time approximation scheme. (C) 2012 Elsevier B.V. All rights reserved.

关键词： Scheduling Transportation NP-hard fully polynomial time approximation scheme

来源：评论

学校读者我要写书评

暂无评论

Single-Machine Scheduling with Step-Deteriorating Jobs and Rejection

引用

Journal of the Operations Research Society of China 2024年第4期12卷 1088-1102页

作者： Fan-Yu Kong Cui-Xia Miao Yu-Jia Huo Jia-Xin Song Yu-Zhong Zhang School of Mathematical Sciences Qufu Normal UniversityQufu273165ShandongChina Institute of Operations Research Qufu Normal UniversityRizhao276826ShandongChina

In this paper,we consider the single-machine scheduling with step-deteriorating jobs and *** job is either rejected by paying a rejection penalty,or accepted and processed on the single machine,and the actual processing time of each accepted job is a step function of its starting time and the common deteriorating *** objective is to minimize the makespan of the accepted jobs plus the total penalty of the rejected *** the case of common deteriorating penalty,we first show that the problem is NP-hard in the ordinary *** we present two pseudo-polynomial algorithms and a 2-approximation ***,we propose a fully polynomial time approximation *** the case of common normal processing time,we present two pseudo-polynomial time algorithms,a 2-approximation algorithm and a fully polynomial time approximation scheme.

关键词： Scheduling Step-deteriorating Rejection penalty NP-hard fully polynomial time approximation scheme

来源：评论

学校读者我要写书评

暂无评论

The TV advertisements scheduling problem

引用

OPTIMIZATION LETTERS 2019年第1期13卷 81-94页

作者： Diaz-Nunez, Fabian Halman, Nir Vasquez, Oscar C. Univ Santiago Chile Dept Ind Engn Santiago Chile Hebrew Univ Jerusalem Jerusalem Israel

A TV channel has a single advertisement break of duration h and a convex continuous function f[0,h] -> R+ representing the TV rating points within the advertisement break. Given n TV advertisements of different durations pj that sum up to h, and willingness to pay coefficients wj, the objective is to schedule them on the TV break in order to maximize the total revenue of the TV channel Sigma jwjcj-pjcjf(t)dt, where [cj-pj,cj) is the broadcast time interval of TV advertisement j. We show that this problem is NP-hard and propose a fully polynomial time approximation scheme, using a special dominance property of an optimal schedule and the technique of K-approximation sets and functions introduced by Halman et al. (Math Oper Res 34:674-685, 2009).

关键词： Scheduling TV rating points Dynamic programming fully polynomial time approximation scheme K-approximation sets and functions

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：