机器具有学习效应的供应链排序问题

研究了机器具有学习效应的供应链排序问题.有多个客户分布在不同位置,每个客户都有一定数量的工件需要在一台机器上进行加工.每个客户的工件在机器上加工时具有学习效应,即后面加工的工件实际加工时间是逐渐缩短的.工件生产完后需要运输到相应的客户处,每一批配送需要花费一定的时间和费用.这里研究了供应链排序理论中主要的四个目标函数,分析了这些问题的复杂性,对于一些情况给出了它们的最优算法.     

具有一般学习效应的单机排序问题

在具有学习效应的环境下,由于机器重复加工相同或相似的工件,因此以后加工的工件的加工时间变小.本文研究新的更一般的学习效应:Dejong学习效应.我们证明单机最大完工时间问题,总完工时间问题和两类多目标问题是多项式时间可解的.     

具有指数和位置学习效应的机器排序问题

本文考虑指数学习效应和位置学习效应同时发生的新的排序模型.工件的实际加工时间不仅依赖于已经加工过工件正常加工时间之和的指数函数,而且依赖于该工件所在的位置.单机排序情形下,对于最大完工时间和总完工时间最小化问题给出多项式时间算法.此外某些特殊情况下,总权完工时间和最大延迟最小化问题也给出了多项时间算法.流水机排序情形,对最大完工时间和总完工时间最小化问题在某些特殊情形下给出多项时间算法.     

与交货期有关的供应链排序问题

本文在供应链中把多制造商、多客户的生产和运输集成起来研究,解决工件带有交货期的供应链排序问题.以生产和运输的总费用达到最小作为目标,建立问题的集成排序模型,在分析解的最优性条件基础上,分别用工件的最大延迟和误工工件数作为排序目标,给出相应的动态规划算法,并分析算法的复杂性.     

同时具有学习效应和退化效应的单机排序问题

本文给出了一种同时具有一般化学习效应和退化效应的单机排序模型。在此模型中,工件的实际加工时间既与工件所在位置又与其开工时间有关,且工件在加工之后具有一个配送时间。其中学习效应是工件所在位置的函数,退化效应是工件开工时间的函数。证明了极小化最大完工时间和极小化总完工时间问题是多项式可解的,在满足一定的条件下,极小化加权总完工时间和极小化最大延误问题也是多项式可解的。推广了一些已有文献中的结论。     

具有安装时间和学习效应的单机排序问题

讨论了工件具有安装时间和学习效应的单机排序问题。安装时间是依赖于已加工完的工件的实际加工时间的简单函数,即p-s-d形式。工件的加工时间不仅与已完成工件的加工时间有关,还与工件的加工位置有关。证明了极小化最大完工时间,极小化完工时间k总和,极小化完工时间k次幂的和是多项式可解的,另外还证明了满足一定条件下的极小化加权完工时间和,极小化最大延误和极小化延迟时间和问题是多项式可解的。     

具有学习效应的排序对策

建立了具有学习效应的排序对策模型,在这类排序对策中,工件的实际加工时间不再是常数,而是关于工件位置的递减幂函数。当所有工件的正常加工时间相等时,松弛可行顺序的条件,相应的排序对策是均衡的,但不一定是凸对策。     

交货期可以指派的供应链排序问题

考虑了由一个制造商和多个客户组成的供应链系统.每个客户有多个订单交给制造商加工,且每个客户有一个可以接受的完工订单到达时间.制造商可以与客户进行协商来选定合适的交货期.完工的订单是采用直接运输方式分批配送的,每一批配送需要花费一定的时间和费用.目标是对每个订单指派合适的交货期,并且进行生产和配送的排序,以极小化总的交货期指派费用,订单误工费用与配送费用的和.考虑了多种情况,分别给出了相应的算法.     

一类具有学习效应和安装时间的单机排序问题

本文主要讨论了工件加工时间具有学习效应和安装时间的单机排序问题。工件的加工时间不仅与之前已加工完的工件加工时间有关,还与工件的加工位置有关。安装时间是依赖于已加工完的工件的实际加工时间的简单函数,即p-s-d形式。本文证明了极小化最大完工时间,极小化总完工时间,极小化完工时间的平方和问题具有多项式算法,也证明了极小化加权总完工时间,极小化最大延误和极小化总误工问题在某些条件下具有多项式算法。     

具有学习和退化效应的单机干扰管理问题

针对工件同时具有学习和退化效应、机器具有可用性限制这一问题,建立可预见性单机干扰管理模型。在这一模型中,工件的加工时间是既与工件所排的加工位置又与工件开始加工的时间有关的函数。同时,在生产过程中由于机器发生故障或定期维修等扰动事件导致机器在某段时间内不能加工工件。目标是在同时考虑原目标函数和由扰动造成的偏离函数的情况下,构建一个新的最优时间表序列。根据干扰度量函数的不同研究了两个问题,第一个问题的目标函数是极小化总完工时间与总误工时间的加权和;第二个问题的目标函数是极小化总完工时间与总提前时间的加权和。对于所研究的问题,首先证明了最优排序具有的性质,然后建立了相应的拟多项式时间动态规划算法。     

优化交货期窗口的两阶段供应链排序问题

研究一类优化交货期窗口的两阶段供应链排序问题. 优化交货期窗口是指交货期窗口的开始与结束时刻是决策变量, 不是输入常量. 两阶段是指工件先加工, 后运输: 加工阶段是一台加工机器逐个加工工件;运输阶段是无限台车辆分批运输完工的工件. 工件的开始运输时刻与完工时刻之差定义为工件的储存时间, 且有相应的储存费用. 若工件的运输完成时刻早于(晚于)交货期窗口的开始(结束)时刻, 则有相应的提前(延误)惩罚费用. 目标是极小化总提前惩罚费用、总延误惩罚费用、总储存费用、总运输费用以及与交货期窗口有关的费用之和. 针对单位时间的延误惩罚费用不超过单位时间的储存费用、单位时间的储存费用不超过单位时间的提前惩罚费用的情形, 给出了时间复杂性为O(n^{8})的动态规划算法.     

储存时间有上限的两阶段供应链排序问题

研究一类储存时间有上限的两阶段供应链排序问题.两阶段是指工件先加工,后运输:加工阶段是一台加工机器逐个加工工件;运输阶段是无限台车辆分批运输完工的工件.工件的运输完成时刻与完工时刻之差定义为工件的储存时间,且有相应的储存费用,且任意工件的储存时间都不超过某一常数.若工件的运输完成时刻早于(晚于)交货期窗口的开始(结束)时刻,则有相应的提前(延误)惩罚费用.目标是极小化总提前惩罚费用、总延误惩罚费用、总储存费用、总运输费用以及与交货期窗口有关的费用之和.先证明该问题是NP-难的,后对单位时间的储存费用不超过单位时间的延误惩罚费用的情形给出了伪多项式时间算法.     

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

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

具有多个不可用时间段的单机供应链排序问题

在单机供应链排序问题中, 机器会有多个长度确定的不可用时间段,它仅可以在可用时间段内加工工件,且每个可用时间段的长度不大于给定的常数.多个完工工件可组成一批由一个容量无限制的运输工具发送给客户.问题的目标是如何 安排工件的加工、发送以及不可用时间段,以使总发送时间与总发送费用之和达到最小. 对于工件加工可恢复的情况,可在多项式时间 O(n^2) 内得到最优序. 对于工件加工不可恢复的情况,证明了问题是强NP-难的, 并提出了~2-近似算法.     

具有可变配送费用和固定配送时刻的单机排序问题

研究了单机环境下生产与配送的协同排序问题.有多个工件需要在一台机器上进行加工,加工完的工件需要分批配送到一个客户.每批工件只能在固定的几个配送时刻出发,不同的配送时刻对应着不同的配送费用.我们的目标是找到生产与配送的协同排序,极小化排序的时间费用与配送费用的加权和.研究了排序理论中主要的四个目标函数,构建了单机情况下的具体模型,分析了问题的复杂性,对于配送费用单调非增的情况给出了它们的最优算法.     

Minimizing total tardiness in a scheduling problem with a learning effect

Minimizing of total tardiness is one of the most studied topics on single machine problems. Researchers develop a number of optimizing and heuristic methods to solve this NP-hard problem. In this paper, the problem of minimizing total tardiness is examined in a learning effect situation. The concept of learning effects describes the reduction of processing times arising from process repetition. A 0–1 integer programming model is developed to solve the problem. Also, a random search, the tabu search and the simulated annealing-based methods are proposed for the problem and the solutions of the large size problems with up to 1000 jobs are found by these methods. To the best of our knowledge, no works exists on the total tardiness problem with a learning effect tackled in this paper.     

A bicriteria flowshop scheduling with a learning effect

In many situations, a worker’s ability improves as a result of repeating the same or similar tasks; this phenomenon is known as the learning effect. In this paper the learning effect is considered in a two-machine flowshop. The objective is to find a sequence that minimizes a weighted sum of total completion time and makespan. Total completion time and makespan are widely used performance measures in scheduling literature. To solve this scheduling problem, an integer programming model with n² + 6n variables and 7n constraints where n is the number of jobs is formulated. Because of the lengthy computing time and high computing complexity of the integer programming model, the problem with up to 30 jobs can be solved. A heuristic algorithm and a tabu search based heuristic algorithm are presented to solve large size problems. Experimental results show that the proposed heuristic methods can solve this problem with up to 300 jobs rapidly. According to the best of our knowledge, no work exists on the bicriteria flowshop with a learning effect.     

Approximation algorithm for the on-line multi-customer two-level supply chain scheduling problem

A manufacturer has to process jobs released on-line and deliver them to customers. Preemption is allowed. Jobs are grouped into batches for delivery. The sum of the total flow time and the total delivery cost is minimized. Deliveries to different customers cannot be combined. We present an on-line algorithm with the competitive ratio bounded by 3+α$3+\alpha$, where α$\alpha$ is the ratio of the largest processing time to the smallest processing time.     

工件的运输和继列分批加工协作排序问题

近年来,工件的运输和加工协作排序问题在物流和供应链管理领域得到广泛关注. 讨论了先用 $\ m$ 台车辆将工件从等待区域运输到继列分批处理机处, 再进行分批加工的协作排序问题, 加工一批工件需要支付一定的费用, 目标为最小化工件的总完工时间与批的加工费用之和. 在工件的加工时间都相等的情况下, 如果工件运输方案确定, 给出了多项式时间的动态规划算法; 如果工件运输方案不确定, 证明了该问题是{\, NP}-难的, 给出了车辆返回时间 $\ t=0$ 时, 最差性能比等于 $\ 2-\frac{1}{m}$ 的近似算法.     

公平关切下参照价格效应的绿色供应链定价策略

以制造商主导的由一个制造商和一个零售商组成的绿色供应链为研究对象,基于消费者的参照价格构造了制造商公平关切、零售商公平关切和供应链成员均公平关切三种供应链模型,给出各模型下的最优定价策略,并分析了公平关切系数与消费者的参照价格效应对最优策略的影响。研究结果表明:公平关切系数与消费者的参照价格效应改变了产品的批发价格、绿色度水平和零售价格,且对供应链各成员以及整个供应链系统都产生了影响。