共查询到19条相似文献,搜索用时 421 毫秒
1.
2.
本文研究两机器自由作业问题,每工件恰有两个操作,除本身两台机器用于加工外,制造商可以将部分工件转包给承包商加工.该承包商有一台机器,可以加工全部操作。一旦承担转包任务,制造商需要支付转包费用给承包商,该费用与承包商机器单位时间价格有关.制造商需要确定转包工件集及未转包工件的排序时间表,使得转包费用与时间表的加工总长最小.本文证明该问题是NP困难的,设计动态规划算法,并讨论承包商机器时间的定价方案. 相似文献
3.
研究制造商加工环境为两机自由作业和流水作业柔性排序问题,即工件既可以在制造商两台机器上加工,又可以转包给承包商机器加工.承包商有足够多机器,使得每台机器至多加工一个工件.工件在制造商及承包商机器上所需加工时间及费用均不同.本文需要确定被转包的工件集及未转包工件的加工顺序,在加工及转包总费用不超过给定值的情况下,分别极小... 相似文献
4.
5.
6.
研究了一类工件排序与转包关联的模型,即工件既可以在制造商的同类机上加工,也可以较高费用转包给某个承包商加工.需要确定被转包的工件集,以及未转包工件的加工顺序,使得工件加工与转包费用在工件最大完工时间满足限制条件下达到极小.证明了该问题的NP困难性,用数学规划方法构造多项式时间近似算法,并分析算法性能比. 相似文献
7.
8.
研究工件可以转包加工的单台机排序问题: 有n个工件, 在零时刻已经到达一个单台机处, 每个工件可以由加工者自有的单台机器加工或者转包给其他机器加工. 如果工件被转包加工, 那么其完工时间等于在自有机器上的加工时间, 而产生的加工费用与在自有机器上加工的费用不同. 假设被转包加工的工件的完工时间和加工费用与转包加工机器的总负载没有关系.目标函数是最小化工件最大完工时间与总加工费用的加权和. 该问题已经被证明是NP-难的. 最后给出该问题的伪多项式时间最优算法, 并且提出一个完全多项式时间近似方案(FPTAS). 相似文献
9.
10.
考虑了工件具有退化效应的两台机器流水作业可拒绝排序问题,其中工件的加工时间是其开工时间的简单线性增加函数.每个工件或者被接收,依次在两台流水作业机器上被加工,或者被拒绝但需要支付一个确定的费用.考虑的目标是被接收工件的最大完工时间加上被拒绝工件的总拒绝费用之和.证明了问题是NP-难的,并提出了一个动态规划算法.最后对一种特殊情况设计了多项式时间最优算法. 相似文献
11.
《数学季刊》2015,(4)
Scheduling with outsourcing is studied in this paper. It is assumed that both manufacturer and subcontractor have a single machine to process n jobs. The manufacturer needs to determine simultaneously a set of outsourced jobs and the schedule of the jobs in-house such that two criterias, i.e., outsourcing cost and production cost, are minimized.The production cost is measured by the number of tardy jobs or the total tardiness of jobs in-house, and the outsourcing cost is proportional to the total processing time of jobs outsourced. Two kinds of problems with different criterias are considered. We analyze the computational complexity and provide pseudo-polynomial time optimization algorithms for the NP-hard version of the problems. 相似文献
12.
We consider a two-machine flow shop problem in which each job is processed through an in-house system or outsourced to a subcontractor. A schedule is established for the in-house jobs, and performance is measured by the makespan. Jobs processed by subcontractors require paying an outsourcing cost. The objective is to minimize the sum of the makespan and total outsourcing costs. We show that the problem is NP-hard in the ordinary sense. We consider a special case in which each job has a processing requirement, and each machine a characteristic value. In this case, the time a job occupies a machine is equal to the job’s processing requirement plus a setup time equal to the characteristic value of that machine. We introduce some optimality conditions and present a polynomial-time algorithm to solve the special case. 相似文献
13.
14.
We consider an order acceptance and scheduling model with machine availability constraints. The manufacturer (machine) is assumed to be available to process orders only within a number of discontinuous time intervals. To capture the real-life behavior of a typical manufacturer who has restrictions of time availability to process orders, our model allows the manufacturer to reject or outsource some of the orders. When an order is rejected or outsourced, an order-dependent cost of penalty will occur. The objective is to minimize the makespan of all accepted orders plus the total penalty of all rejected/outsourced orders. We study the approximability of the model and some of its important special cases. 相似文献
15.
《数学季刊》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. 相似文献
16.
This paper considers a two-machine ordered flow shop problem, where each job is processed through the in-house system or outsourced to a subcontractor. For in-house jobs, a schedule is constructed and its performance is measured by the makespan. Jobs processed by subcontractors require paying an outsourcing cost. The objective is to minimize the sum of the makespan and the total outsourcing cost. Since this problem is NP-hard, we present an approximation algorithm. Furthermore, we consider three special cases in which job j has a processing time requirement pj, and machine i a characteristic qi. The first case assumes the time job j occupies machine i is equal to the processing requirement divided by a characteristic value of machine i, that is, pj/qi. The second (third) case assumes that the time job j occupies machine i is equal to the maximum (minimum) of its processing requirement and a characteristic value of the machine, that is, max{pj, qi} (min{pj, qi}). We show that the first and the second cases are NP-hard and the third case is polynomially solvable. 相似文献
17.
Kangbok Lee 《European Journal of Operational Research》2011,213(3):489-497
This paper considers a two-stage production scheduling problem in which each activity requires two operations to be processed in stages 1 and 2, respectively. There are two options for processing each operation: the first is to produce it by utilizing in-house resources, while the second is to outsource it to a subcontractor. For in-house operations, a schedule is constructed and its performance is measured by the makespan, that is, the latest completion time of operations processed in-house. Operations by subcontractors are instantaneous but require outsourcing cost. The objective is to minimize the weighted sum of the makespan and the total outsourcing cost. This paper analyzes how the model’s computational complexity changes according to unit outsourcing costs in both stages and describes the boundary between NP-hard and polynomially solvable cases. Finally, this paper presents an approximation algorithm for one NP-hard case. 相似文献
18.
This paper considers two single-machine scheduling problems with outsourcing allowed where each job can be either processed on an in-house single-machine or outsourced. They include the problem of minimizing maximum lateness and outsourcing costs, and that of minimizing total tardiness and outsourcing costs. Outsourcing is commonly required as a way to improve productivity in various companies including electronics industries and motor industries. The objective is to minimize the weighted sum of the outsourcing cost and the scheduling measure represented by either one of maximum lateness and total tardiness, subject to outsourcing budget. It is proved that the problem is NP-hard. Some solution properties are characterized to derive heuristic algorithms, and also a branch-and-bound algorithm. Numerical experiments are conducted to evaluate performance of the derived algorithms. 相似文献
19.
In this paper, we investigate how opportunities to invest in demand enhancing services for a product line affect the interactions between a manufacturer and her dealer. Many demand enhancing services, e.g. after sales support, warranty repair etc. can be provided either by the manufacturer or they can be delegated to the dealer. We first show that when a manufacturer retains control of such services, the dealer will have an incentive to choose a decentralized organizational structure as a means of committing to non-product line pricing since this will encourage the manufacturer to invest more in demand enhancing services. We then consider a game that is played between the manufacturer and the dealer in which the dealer chooses between centralized (product line pricing) or decentralized (non-product line pricing) operations, and the manufacturer chooses between insourcing the services, i.e. providing them herself, or outsourcing them to the dealer. We find that the equilibrium depends on which, if any, channel partner has the ability to act as a Stackelberg leader. If the dealer can move first, then the equilibrium will always be outsourced services and centralized dealer operations. However, if either the manufacturer moves first or if neither partner can move first, then the equilibrium can be either insourced services and decentralized dealer operations or outsourced service and centralized dealer operations. 相似文献