English

运筹学学报

• 运筹学 • 上一篇    下一篇

机器带不可用时间限制的简单线性恶化供应链排序问题

范静, 鲁习文   

  1. 1. 上海第二工业大学文理学部, 上海 201209; 2. 华东理工大学理学院, 上海 200237
  • 收稿日期:2016-02-01 出版日期:2016-12-15 发布日期:2016-12-15
  • 通讯作者: 范静 fanjing@sspu.edu.cn
  • 基金资助:

    国家自然科学基金青年项目(No. 1601316), 上海第二工业大学青年教师培养科研项目(No. 201513)

Supply chain scheduling problem under simple linear deterioration on a single-machine with an unavailability constraint

FAN Jing, LU Xiwen   

  1. 1. College of Arts and Sciences, Shanghai Polytechnic University, Shanghai 201209, China; 2. School of Science, East China University of Science and Technology, Shanghai 200237, China
  • Received:2016-02-01 Online:2016-12-15 Published:2016-12-15

PDF

501

摘要：

研究的单机供应链排序问题中, 机器有一个不可用时间限制, 工件的加工时间与恶化率及其开工时间有关, 且工件的加工不可恢复. 一个或多个完工工件可组成一个发送批由车辆发送给客户, 且在机器不可用时间限制之前完工的工件必须在限制开始之时或之前完成发送. 问题的目标是最小化总发送时间与总发送费用之和. 证明问题是NP-难的, 提出了伪多项式时间的动态规划算法. 进一步, 在确定问题目标函数值的上界及下界之后, 设计了一个完全多项式时间近似方案(FPTAS).

关键词: 简单线性恶化, 不可用时间限制, 供应链排序, 动态规划算法, 完全多项式时间近似方案

Abstract:

We study a single-machine supply chain scheduling problem with one unavailability constraint, in which the actual processing time of a job depends on the deteriorating operator and the beginning time of processing and the interrupted job is non-resumable. The sufficient available vehicles without capacity limit deliver batches of completed jobs to the customer. And the completed jobs before the unavailability interval must be delivered before or by the start time of the unavailability interval. The objective is to minimize the sum of total delivery time and total delivery cost. We show that the problem is NP-hard, and present a pseudo-polynomial-time dynamic programming. Moreover, we achieve a full polynomial time approximation scheme (FPTAS) based on the lower bound and the upper bound of the objective function value of the problem.

Key words: simple linear deterioration, unavailability constraint, supply chain scheduling, dynamic programming algorithm, full polynomial time approximation scheme