共查询到15条相似文献,搜索用时 109 毫秒
1.
本文研究自由作业环境下的供应链排序问题,研究供应链的上游如何安排工件在自由作业机器上加工,把加工完毕的工件分批发送给下游,使得生产排序费用和发送费用总和最少.这里,生产排序费用是用工件送到时间的函数来表示;发送费用是由发送的固定费用和与运输路径有关的变化费用所组成.本文研究以工件最大送到时间为生产排序费用的自由作业供应链排序问题,在指出问题的NP困难性后,用动态规划算法构造多项式时间近似算法,并分析算法的性能比.本文最后还对特殊情形进行了讨论. 相似文献
2.
本文研究一类集成工件生产和发送的排序模型.在该模型中,供应链的上游首先将工件安排在自由作业机器上加工,然后把加工完毕的工件分批发送给下游.问题是寻找生产和发送相连的排序,使得生产排序费用和发送费用总和最少.这里,生产排序费用是以工件带权送到时间和表示;发送费用由固定费用和与运输路径有关的变化费用组成.在指出问题的NP困难性后,本文用动态规划算法构造了一致条件下的多项式时间近似算法,并分析算法的性能比.本文最后还讨论了该问题的其它情形. 相似文献
3.
4.
研究工件带就绪时间的单机供应链排序问题,即工件到达后按何种顺序在机器上加工,并将完工工件如何由运输工具发送给客户,使得生产费用与发送费用总和最少.这里,每个工件的生产费用为工件的发送时刻,多个工件可组成一批一次发送给客户,发送费用与发送次数成正比.对于工件允许中断加工的问题,基于SRPT规则给出多项式时间的动态规划算法求解最优序;对于工件不允许中断加工的问题,证明问题是强NP难的,并提出了性能比为2的近似算法. 相似文献
5.
6.
研究的单机供应链排序问题中, 机器有一个不可用时间限制, 工件的加工时间与恶化率及其开工时间有关, 且工件的加工不可恢复. 一个或多个完工工件可组成一个发送批由车辆发送给客户, 且在机器不可用时间限制之前完工的工件必须在限制开始之时或之前完成发送. 问题的目标是最小化总发送时间与总发送费用之和. 证明问题是NP-难的, 提出了伪多项式时间的动态规划算法. 进一步, 在确定问题目标函数值的上界及下界之后, 设计了一个完全多项式时间近似方案(FPTAS). 相似文献
7.
8.
9.
10.
11.
在单机供应链排序问题中, 机器会有多个长度确定的不可用时间段,它仅可以在可用时间段内加工工件,且每个可用时间段的长度不大于给定的常数.多个完工工件可组成一批由一个容量无限制的运输工具发送给客户.问题的目标是如何 安排工件的加工、发送以及不可用时间段,以使总发送时间与总发送费用之和达到最小. 对于工件加工可恢复的情况,可在多项式时间 O(n^2) 内得到最优序. 对于工件加工不可恢复的情况,证明了问题是强NP-难的, 并提出了~2-近似算法. 相似文献
12.
M. Zandieh S. Molla-Alizadeh-Zavardehi 《Journal of Computational and Applied Mathematics》2009,230(2):546-558
Traditional scheduling problems assume that there are always infinitely many resources for delivering finished jobs to their destinations, and no time is needed for their transportation, so that finished products can be transported to customers without delay. So, for coordination of these two different activities in the implementation of a supply chain solution, we studied the problem of synchronizing production and air transportation scheduling using mathematical programming models. The overall problem is decomposed into two sub-problems, which consists of air transportation allocation problem and a single machine scheduling problem which they are considered together. We have taken into consideration different constraints and assumptions in our modeling such as special flights, delivery tardiness and no delivery tardiness. For these purposes, a variety of models have been proposed to minimize supply chain total cost which encompass transportation, makespan, delivery earliness tardiness and departure time earliness tardiness costs. 相似文献
13.
《数学季刊》2015,(3)
In this paper, we study a new scheduling and outsourcing model with multiple customers in which jobs can be processed by either in-house machine or outsourcing machine.All processed jobs have to be delivered in batches to their respective customers and each shipment incurs a delivery cost as well as a fixed amount of time. We discuss three commonly used objective functions, analyze their complexity and solve them by dynamic programming algorithms. 相似文献
14.
The Coordination of Scheduling and Batch Deliveries 总被引:2,自引:0,他引:2
This paper considers several scheduling problems where deliveries are made in batches with each batch delivered to the customer
in a single shipment. Various scheduling costs, which are based on the delivery times of the jobs, are considered. The objective
is to minimize the scheduling cost plus the delivery cost, and both single and parallel machine environments are considered.
For many combinations of these, we either provide efficient algorithms that minimize total cost or show that the problem is
intractable. Our work has implications for the coordination of scheduling with batch delivery decisions to improve customer
service. 相似文献
15.
In this paper, an integrated due date assignment and production and batch delivery scheduling problem for make-to-order production system and multiple customers is addressed. Consider a supply chain scheduling problem in which n orders (jobs) have to be scheduled on a single machine and delivered to K customers or to other machines for further processing in batches. A common due date is assigned to all the jobs of each customer and the number of jobs in delivery batches is constrained by the batch size. The objective is to minimize the sum of the total weighted number of tardy jobs, the total due date assignment costs and the total batch delivery costs. The problem is NP-hard. We formulate the problem as an Integer Programming (IP) model. Also, in this paper, a Heuristic Algorithm (HA) and a Branch and Bound (B&B) method for solving this problem are presented. Computational tests are used to demonstrate the efficiency of the developed methods. 相似文献