随机订单干扰下考虑合并决策的供应链网络调度研究

为满足客户个性化需求的快速响应，企业需具备柔性的外部供应链网络结构，以协同方式共同完成产品生产。本文考虑具有交互特征的多个不同类型协同供应链网络，构建生产成本、库存成本、等待成本以及订单延期交货成本最小化的目标函数，并设计合并决策判断变量构建同类订单在相同协同企业处的开始时间约束。此外，模型中考虑确定订单以及随机订单两种类型订单，并设计随机订单在区间时间段中离散时间点的到达概率。为获取协同供应链网络生产调度优化策略，基于随机订单到达与否的场景构建四个子决策模型，并进一步设计判断提前安排随机订单协同生产和不提前安排随机订单协同生产不同调度策略下成本差异的主决策模型。仿真结果表明合并决策在带来生产成本效益的同时也引起了部分订单的延期交货，且不同类型的协同供应链网络对随机订单的抗干扰能力存在一定程度的差异。     

平行机作业环境下的订单分配与排序

针对一类平行机作业环境下的订单分配与排序问题,从整体的角度协同优化供应链中的订单分配、生产调度和分批运输调度。以完成所有订单的总订货提前期与生产运输总成本的加权和最小化为目标,构建了问题的数学模型。将基于向量组编码结构的禁忌搜索算法与基于动态规划方法的启发式算法相结合,设计了一种混合优化算法以求解问题。对不同策略和不同算法进行比较,数据实验结果显示了订单分配与排序策略的优越性及所提算法的有效性。     

顾客可选末端交付方式和时间窗的城市配送动态订单接受优化研究

在顾客可以自选末端交付方式和配送时间窗的情境下，为及时决策是否接受顾客配送订单，构建了城市配送动态订单接受决策框架，定义了配送路径预规划、配送需求评估、订单接受策略调整和路径全局优化四个阶段，建立了基于时间窗偏差阈值的配送需求评估方法，设计了全部接受、交付方式静态分配和服务选项动态分配三种订单接受策略调整算法。仿真表明：服务选项动态分配算法能够获取更高的利润，在单批次配送任务较多的情形下还具有更好的时间性能；随着时间窗宽度逐渐增加，自提柜交付收益和行驶里程逐渐减少，而送货上门交付收益和利润逐渐增加；时间窗偏差阈值对配送服务利润影响明显，但不存在趋势性关系；仿真算例显示，送货上门交付收益较高的时间窗偏差阈值，往往会获取更高的利润。     

随机抽样算法在多项目调度中的应用

针对资源约束下的多项目调度问题,扩展了单项目进度生产机制,并在此基础上设计了多项目调度的随机抽样算法。通过对比分析,说明不同的任务优先规则对随机抽样算法具有不同的影响,其中采用MINSLK等优先规则的随机抽样算法能够有效地缩短项目平均工期。与其他多项目调度启发式算法的比较和统计检验,说明随机抽样算法显著优于这些常用的启发式算法。     

考虑时间序列关联的订单选择决策比较研究

在不同计划期的订单之间有可能存在时间序列关联,而现有生产计划模型大多不考虑这一关联关系对订单选择决策的影响.针对这一问题,以按单生产方式为背景,基于时间序列关联规则,建立了一个权衡当前与未来利润的订单选择决策模型,而将不考虑时序关联关系的订单选择模型作为比较研究的Benchmark问题.在数值仿真实验中,设计了一个动态随机的订单到达流,采用分阶段求解策略,以权重优先算法针对不同决策情景,分别基于两个模型进行决策并比较其决策结果.数据显示,在订单流中存在关联性的情况下,考虑时序关联关系的决策模型较优,证明在生产计划中考虑需求在时间方向上的关联性是必要的.     

时间窗口约束下基于改进蚁群算法的协同制造调度研究

与传统调度模式不同，协同制造模式下企业之间的调度模式极其复杂。协同企业间的加工工序路线并不固定，且不同类型产品具有不同的加工路线网络。为此本文针对平衡型、瓶颈型、跳跃型、混合型四类具有典型特点的协同制造网络G_p进行分析和设计；考虑制造企业同类产品合并加工策略，构建基于连续加工量的分段生产成本函数；通过设计合理的订单最早交货时间和最晚交货时间，对订单交货进行时间窗口约束，并在此基础上构建了由制造商生产成本W_c^m、订单等待W_s^k（Q_k， T'_k）和提前完工库存成本W_s^k（Q_k， T″_k）、延期惩罚成本构成W_l^k（Q_k， T'″_k）的目标函数。为求解该模型，创新性将蒙特卡洛思想引入蚁群算法，提高蚂蚁选择合理性，避免局部最优；同时，采用移动窗口[min， max]奖励机制，并且对信息素奖励乘以平衡系数k（N）提高奖励可信度，加快搜索速度并提高求解性能。仿真结果表明，本文构建调度模型合理，可以获得优化的调度结果；同时，本文提出的蚁群改进寻优算法具有良好的求解速度和收敛性，算法具有较好的稳定性。     

基于3D打印技术的备件生产与运输协同调度问题研究

基于3D打印的智能制造技术已经成为推动备件供应链转型升级的重要手段。在此背景下，本文研究“随时需要随时生产+即时配送”新型模式下的计划性维修备件的供应链协同问题。生产与运输协同调度问题在制造业领域普遍存在，属于NP-Hard问题。本文研究带时间窗的生产与运输协同调度问题，建立混合整数规划模型，根据Dantzig-Wolfe分解原理分别建立主问题和子问题数学优化模型，并采用改进的分支定价算法进行求解。在求解过程中，首先，构造可行解，基于可行路径调用CPLEX优化软件对主问题求解；其次，针对子问题的求解，根据研究问题的属性设计占优原则和加速策略，并对求得的非整数解进行分支；最后，通过对多组规模算例进行测试，数值实验结果表明：1)验证了所建立模型和改进算法的有效性；2)通过求解时间对比可知所使用加速策略能够将算法效率提高10倍左右；3)通过将生产和运输协同决策与实际运作中的分阶段决策结果对比，本文设计的方案可以将目标函数值平均优化50.33%。本研究不仅能够有效解决新型备件生产模式下的生产与运输协同调度问题，而且可以为企业实际运营决策提供科学依据，实现降本增效的目标。     

大数据驱动的决策范式转变——以个性化O2O即时物流调度为例

大数据环境下传统的决策范式正转变为基于数据的决策范式，本文以O2O即时服务这种新型商业模式为情景，研究大数据驱动的新决策范式下的O2O即时物流调度模型.本文跨域融合物流部门、其他运营部门以及外部环境信息构成全景式数据，同时放宽传统决策范式的经典假设，实现从无差异化配送时间到个性化配送时间的转变，以及需求服从先验分布到考虑未来需求时空属性的转变.本文融合机器学习和运筹优化方法，实现新决策范式下的O2O即时物流调度模型.在预测层面，构建个性化众包配送时间预测模型和基于订单集时空相似性的需求场景预测算法；在决策层面，同时考虑个性化预测模型的点估计及其不确定性，并考虑未来订单集的时空分布，构建考虑预测不确定性的调度模型，同时设计同步预测和决策算法求解.本文与中国主流的O2O商超平台合作，通过基于真实数据的模拟仿真，验证了新决策范式下的O2O即时物流调度模型的可行性和有效性.相较于传统的决策范式，本文提出的模型能实现更精准的供需匹配，降低延误订单数、平均配送时间和配送成本.     

考虑交货因素的热轧无缝钢管订单排程模型与算法

无缝钢管的市场需求具有多品种、小批量的特点，为了在满足客户需求的同时保证高效连续化生产，文章在满足生产工艺特征的基础上将配送地址和交货期等合同因素引入热轧无缝钢管订单排程问题中，建立了以适期交货、订单集中生产配送和最小化机器设备调整为优化目标的订单排程优化模型，并设计了两阶段求解算法：首先，以订单交货期与配送地址差异最小为目标，基于凝聚策略设计了订单聚类算法，将具有相同工艺约束、相似合同要求的订单进行聚类，并形成初始轧制计划；然后，以设备调整和提前/拖期最小为目标，设计混合变邻域搜索算法，对初始轧制批次进行排程优化。基于实际订单数据的实验结果表明，模型和算法对问题的描述和求解是可行有效的。     

B2C电子商务环境下订单拣选与配送联合调度优化

如何在顾客下单后协调好拣选和配送环节,在最短的时间、以较低的成本将商品从货架上拣出、打包后配送到顾客手中,已成为B2C电子商务物流管理中亟待解决的问题。本文尝试以最小化订单履行时间为目标,构建非线性拣选与配送联合调度模型,以解决订单拣选顺序、拣选作业方式、车辆行驶线路等联合决策。为求解此NP难问题,设计了三阶段启发式算法：首先采用“聚类-路径优化”思想,依据顾客位置进行配送方案确认;然后采用基于相似度聚类的订单分批规则对每条配送线路的订单进行分批合并;最后调整拣选任务与配送线路顺序。通过数据实验对模型进行验证,并与传统拣选与配送分开优化的结果进行对比。结果表明,三阶段算法能够有效缩短订单完成时间、降低配送车辆等待时间、改善配送资源利用率。     

Single-machine scheduling with periodic due dates to minimize the total earliness and tardy penalty

We consider a single-machine scheduling problem such that the due dates are assigned to each job depending on its order, and the lengths of the intervals between consecutive due dates are identical. The objective is to minimize the total penalty for the earliness and tardiness of each job. The early penalty proportionally increases according to the earliness amount, while the tardy penalty increases according to the step function. We show that the problem is strongly NP-hard, and furthermore, polynomially solvable if the two types of processing times exist.

     

Optimal Policy for a Stochastic Scheduling Problem with Applications to Surgical Scheduling

We consider the stochastic, single‐machine earliness/tardiness problem (SET), with the sequence of processing of the jobs and their due‐dates as decisions and the objective of minimizing the sum of the expected earliness and tardiness costs over all the jobs. In a recent paper, Baker ( 2014 ) shows the optimality of the Shortest‐Variance‐First (SVF) rule under the following two assumptions: (a) The processing duration of each job follows a normal distribution. (b) The earliness and tardiness cost parameters are the same for all the jobs. In this study, we consider problem SET under assumption (b). We generalize Baker's result by establishing the optimality of the SVF rule for more general distributions of the processing durations and a more general objective function. Specifically, we show that the SVF rule is optimal under the assumption of dilation ordering of the processing durations. Since convex ordering implies dilation ordering (under finite means), the SVF sequence is also optimal under convex ordering of the processing durations. We also study the effect of variability of the processing durations of the jobs on the optimal cost. An application of problem SET in surgical scheduling is discussed.     

A two-agent single machine scheduling problem with due-window assignment and a common flow-allowance

We study a single-machine scheduling model combining two competing agents and due-date assignment. The basic setting involves two agents who need to process their own sets of jobs, and compete on the use of a common processor. Our goal is to find the joint schedule that minimizes the value of the objective function of one agent, subject to an upper bound on the value of the objective function of the second agent. The scheduling measure considered in this paper is minimum total (earliness, tardiness and due-date) cost, based on common flow allowance, i.e., due-dates are defined as linear functions of the job processing times. We introduce a simple polynomial time solution for this problem (linear in the number of jobs), as well as to its extension to a multi-agent setting. We further extend the model to that of a due-window assignment based on common flow allowance.     

混合离散差分进化算法在单机批处理调度中的应用

本文研究单机批处理调度问题,批处理机有批次容量限制,批处理时间由每个批次所含作业中的最长作业处理时间决定。每个作业具有不同的大小、处理时间、提前拖期惩罚权重,所有作业具有公共交货期,且交货期无限晚。目标函数为最小化所有作业的加权提前拖期惩罚之和。该问题已被证明为NP难题,本研究找到了其最优解具有的一些性质,在此基础上利用它们提出了一种动态规划(DP)与差分进化(DE)算法相结合的混合离散差分进化(HDDE)算法来求解该问题,通过与传统的遗传算法、模拟退火算法和迭代贪婪算法进行对比,HDDE算法显示了更加强大的全局搜索能力。     

A fast FPTAS for single machine scheduling problem of minimizing total weighted earliness and tardiness about a large common due date

We address the single machine scheduling problem to minimize the total weighted earliness and tardiness about a nonrestrictive common due date. This is a basic problem with applications to the just-in-time manufacturing. The problem is linked to a Boolean programming problem with a quadratic objective function, known as the half-product. An approach to developing a fast fully polynomial-time approximation scheme (FPTAS) for the problem is identified and implemented. The running time matches the best known running time for an FPTAS for minimizing a half-product with no additive constant.     

A note on pre-emptive scheduling with earliness and tardiness costs

The option of pre-emption seems to have escaped the attention of existing literature on scheduling problems with earliness and tardiness costs. This note presents an attempt to accommodate pre-emption in such settings. The focus is on models with a common due date for all jobs under different cost structures ( job dependent versus job independent), and different objectives ( minsum and minmax). It appears that only one of these cases is not polynomially solvable: the case of minsum objective and job-dependent ( linear) cost. An exact dynamic programming algorithm is introduced for this problem, as well as an efficient heuristic, which is shown to perform extremely well in our numerical tests.     

Integrated supply,production and distribution scheduling under disruption risks

This paper presents a bi-objective stochastic mixed integer programming approach for a joint selection of suppliers and scheduling of production and distribution in a multi-echelon supply chain subject to local and regional disruption risks. Two conflicting problem objectives are minimization of cost and maximization of service level. The three shipping methods are considered for distribution of products: batch shipping with a single shipment of different customer orders, batch shipping with multiple shipments of different customer orders and individual shipping of each customer order immediately after its completion. The stochastic combinatorial optimization problem is formulated as a time-indexed mixed integer program with the weighted-sum aggregation of the two objective functions. The supply portfolio is determined by binary selection and fractional allocation variables while time-indexed assignment variables determine the production and distribution schedules. The problem formulation incorporates supply–production, production–distribution and supply–distribution coordinating constraints to efficiently coordinate supply, production and distribution schedules. Numerical examples modelled after an electronics supply chain and computational results are presented and some managerial insights are reported. The findings indicate that for all shipping methods, the service-oriented supply portfolio is more diversified than the cost-oriented portfolio and the more cost-oriented decision-making, the more delayed the expected supply, production and distribution schedules.     

Minmax common flow-allowance problems with convex resource allocation and position-dependent workloads

We study minmax due-date based on common flow-allowance assignment and scheduling problems on a single machine, and extend known results in scheduling theory by considering convex resource allocation. The total cost function of a given job consists of its earliness, tardiness and flow-allowance cost components. Thus, the common flow-allowance and the actual jobs’ processing times are decision variables, implying that the due-dates and actual processing times can be controlled by allocating additional resource to the job operations. Consequently, our goal is to optimize a cost function by seeking the optimal job sequence, the optimal job-dependent due-dates along with the actual processing times. In all addressed problems we aim to minimize the maximal cost among all the jobs subject to a constraint on the resource consumption. We start by analyzing and solving the problem with position-independent workloads and then proceed to position-dependent workloads. Finally, the results are generalized to the method of common due-window. For all studied problems closed form solutions are provided, leading to polynomial time solutions.

     

Experimental earliness/tardiness production planning with the due window system

In order to use the philosophy of JIT to improve the production planning method of MRP-II, we propose the experimental software system of the earliness/tardiness produc tion planning problem with due window. By means of the approaches and model reported in this paper, the optimal production planning can be achieved. The recommended model extends the problem of due window from the shop scheduling level into the aggregated planning level of mass manufacturing systems. Simulation results have demonstrated that the experimental software is a useful tool for the production management of repetitive manufacturing enterprises.