共查询到18条相似文献,搜索用时 187 毫秒
1.
研究含有批处理机的三台机器流水作业加工总长问题的计算复杂性.不仅考虑了批处理机容量有限的情形,还考虑了批处理机容量无限的情形.证明了当第二台机器是批处理机、其余两台机器是单机时,该问题是NP困难的.至此,含有批处理机的三台机器流水作业加工总长问题在所有情形下的计算复杂性得到了解决. 相似文献
2.
《应用数学与计算数学学报》2017,(4)
讨论一类三阶段流水作业的问题,第一阶段由m台同型机组成,第二阶段和第三阶段分别为1台批处理机,目标函数为最小加工全程.在同型机和两台批处理机上工件的加工时间分别相同情况下,给出了一般情况和几类特殊情况的算法. 相似文献
3.
讨论了并行工件同时加工排序问题,即n个同时到达的工件在m台批处理机上排序的问题.批处理机一次最多能加工B个工件.每批的加工时间等于该批中所含工件的加工时间的最大者.主要考虑B n的特殊情况,即每批可包含任意多个工件,目标函数是极小化总完工时间.首先对同型批处理机的情况给出了动态规划算法,算法的运行时间为O(m nm+1),并进一步将结论推广到同类批处理机的情况. 相似文献
4.
本文考虑了工件具有任意尺寸且机器有容量限制的混合分批平行机排序问题。在该问题中, 一个待加工的工件集需在多台平行批处理机上进行加工。每个工件有它的加工时间和尺寸, 每台机器可以同时处理多个工件, 称为一个批, 只要这些工件尺寸之和不超过其容量; 一个批的加工时间等于该批中工件的最大加工时间和总加工时间的加权和; 目标函数是极小化最大完工时间。该问题包含一维装箱问题为其特殊情形, 为强NP-困难的。对此给出了一个$\left( {2 + 2\alpha+\alpha^{2}}\right)$ -近似算法, 其中$\alpha$ 为给定的权重参数, 满足$0\leq\alpha\leq 1$ 。 相似文献
5.
研究了带服务等级约束的三台平行机在线排序问题.每台机器和每个工件的服务等级为1或者2,工件只能在等级不高于它的机器上加工,即等级为1的工件只能在等级为1的机器上加工,等级为2的工件可在所有机器上加工.每个工件的加工时间为一个单位,目标是极小化所有工件的总完工时间.考虑两种情形:当一台机器等级为1,两台机器等级为2时,给出了竞争比为17/14的最优在线算法;当两台机器等级为1,一台机器等级为2时,给出了竞争比为43/36的最优在线算法. 相似文献
6.
7.
本文研究下面情形的排序问题,两个代理商联合加工来自客户的一个工件集,每个代理商仅有一台单机用于加工工件,每个工件仅需被其中的一台单机无中断地加工一次.在完成分配工件的加工任务后,每个代理商将获得一定的收益并付出一定的加工费用.需要找出工件集的一个最优划分,使得两个代理商的净收益乘积最大.本文研究三个不同经典排序目标作为加工费用的两机合作排序模型,证明模型复杂性,分析最优解结构并设计动态规划算法. 相似文献
8.
9.
10.
11.
This paper considers a multi-stage dynamic hybrid flowshop in which some stage contains several identical batching machines and the other stages contain several identical discrete machines. Each discrete machine can process no more than one operation at a time, and each batching machine can process several jobs continuously in a batch. This problem has a strong practical background in the process industry. Since the problem is NP-hard, improved Lagrangian relaxation (LR) is developed where batch decomposition strategy is applied and mixed backward and forward dynamic programming is designed to solve batch-level subproblems with the case that each operation may have multiple predecessors and successors. Results of numerical experiments with up to 60 jobs show that the proposed algorithm can obtain better solutions in a reasonable computation time than traditional LR. 相似文献
12.
《European Journal of Operational Research》2003,147(3):644-656
This paper considers a scheduling problem in a two-machine flowshop of two batch processing machines. On each batch processing machine, jobs are processed in a batch, and each batch is allowed to contain jobs up to the maximum capacity of the associated machine. The scheduling problem is analyzed with respect to three due date related objectives including maximum tardiness, number of tardy jobs and total tardiness. In the analysis, several solution properties are characterized and based upon these properties, three efficient polynomial time algorithms are developed for minimizing the due date related measures. 相似文献
13.
并行分批排序起源于半导体芯片制造过程。在并行分批排序中,工件可成批加工,批加工机器最多可同时加工B个工件,批的加工时间为批中所有工件的最大工时。首先根据传统的机器环境和目标函数对并行分批排序已有成果进行分类介绍,主要为单机和平行机的机器环境,以及极小化最大完工时间、极小化总完工时间、极小化最大延迟、极小化误工工件数、极小化总延误和极小化最大延误的目标函数;然后梳理了由基本问题所衍生出来的具有新特点的16类新型并行分批排序,包括差异尺寸工件、多目标、工件加工时间或顺序存在限制、考虑费用和具有特殊机制等情况;最后展望未来的研究方向。 相似文献
14.
问题Pm|rj,B|∑Cj的多项式时间近似算法 总被引:2,自引:0,他引:2
本文针对同型机分批排序问题Pm|rj,B|∑Cj进行了研究,给出了该问题在批容量B及机器台数m为常数情况下的多项式时间近似算法(以下简称PTAS);在B为常数时设计出了问题1|rj,B|∑WjCj的计算时间更少的PTAS. 相似文献
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. 相似文献
16.
J. BehnamianS.M.T. Fatemi Ghomi F. JolaiO. Amirtaheri 《Applied Mathematical Modelling》2012,36(2):723-735
This paper investigates single-batch and batch-single flow shop scheduling problem taking transportation among machines into account. Both transportation capacity and transportation times are explicitly considered. While the single processing machine processes one job at a time, the batch processing machine processes a batch of jobs simultaneously. The batch processing time is the longest processing times of jobs assigned to that batch.Each problem is formulated as a mixed integer programming model to find optimal makespan. Lower bounds and heuristic algorithms are proposed and computational experiments are carried out to verify their effectiveness. 相似文献
17.
18.
《European Journal of Operational Research》2002,139(2):245-261
Flowshop scheduling deals with processing a set of jobs through a set of machines, where all jobs have to pass among machines in the same order. With the exception of minimizing a makespan on two machines, almost all other flowshop problems in a general setup are known to be computationally intractable. In this paper we study special cases of flowshop defined by additional machine dominance constraints. These constraints impose certain relations among the job processing times on different machines and make the studied problems tractable. 相似文献