首页 | 本学科首页   官方微博 | 高级检索  
相似文献
 共查询到20条相似文献,搜索用时 15 毫秒
1.
This paper is concerned with optimization of production run time that takes stochastic breakdown and the reworking of defective items into consideration. In a real‐life manufacturing process, production of imperfect quality items as well as random breakdowns of production equipment is inevitable. All defective items produced are assumed to be repairable through a rework process right after the regular production stops in each cycle. This research starts with derivations of the cost functions for production systems with breakdown (no‐resumption policy is considered) and without breakdown taking place, respectively. Then cost functions of both cases are integrated. Theorems on conditional convexity of the overall cost function and bounds for optimal production run time are proposed and proved. This study concludes that although the optimal run time cannot be expressed in a closed form, it falls within the range of bounds. Hence, it can be pinpointed by the use of the bisection method based on the intermediate value theorem. A numerical example is provided to demonstrate its practical usages. Copyright © 2007 John Wiley & Sons, Ltd.  相似文献   

2.
In this paper, a multi-period assignment problem is studied that arises as part of a weekly planning problem at mail processing and distribution centers. These facilities contain a wide variety of automation equipment that is used to cancel, sort, and sequence the mail. The input to the problem is an equipment schedule that indicates the number of machines required for each job or operation during the day. This result is then post-processed by solving a multi-period assignment problem to determine the sequence of operations for each machine. Two criteria are used for this purpose. The first is to minimize the number of startups, and the second is to minimize the number of machines used per operation.The problem is modeled as a 0–1 integer program that can be solved in polynomial time when only the first criterion is considered. To find solutions in general, a two-stage heuristic is developed that always obtains the minimum number of startups, but not necessarily the minimum number of machines per operation. In a comparative study, high quality solutions were routinely provided by the heuristic in negligible time when compared to a commercial branch-and-bound code (Xpress). For most hard instances, the branch-and-bound code was not able to even find continuous solutions within acceptable time limits.  相似文献   

3.
When a machine breakdown forces a modified flow shop (MFS) out of the prescribed state, the proposed strategy reschedules part of the initial schedule to match up with the preschedule at some point. The objective is to create a new schedule that is consistent with the other production planning decisions like material flow, tooling and purchasing by utilizing the time critical decision making concept. We propose a new rescheduling strategy and a match-up point determination procedure through a feedback mechanism to increase both the schedule quality and stability. The proposed approach is compared with alternative reactive scheduling methods under different experimental settings.  相似文献   

4.
This paper surveys the research published on the machine interference problem, also called the machine repairman problem, in which machines interfere with each other’s service. Our emphasis is on work that has appeared since the 1985 review by Stecke and Aronson. After describing the basic model and the scope of our study, we discuss the literature along several dimensions. We describe some of the more interesting papers, and offer some suggestions for topics holding particular promise for future studies. We conclude with comments about how the research has evolved over the past two decades.  相似文献   

5.
Flexible manufacturing is characterized by versatile work stations with minimum change over times and a versatile material handling system. The loading problem in flexible manufacturing is to assign tools, material, operations and jobs to work stations in order to minimize the total number of job-to-work station assignments. In this paper, we describe a special case of the general loading problem applied to flexible assembly and develop a discrete optimization model. We then discuss approaches for obtaining good heuristic solutions and present results for a large scale study.  相似文献   

6.
A wide class of machine scheduling problems can be formulated as ILP problems and solved by branch and bound using the out-of-kilter algorithm for the solution of the subproblems.  相似文献   

7.
Leung等(Preemptive multiprocessor order scheduling to minimize total weighted flowtime [J]. European Journal of Operational Research, 2008, 190: 40-51)研究了如下问题: 有 n 个订单, 其中每个订单 i 含有 n_i 个不同的工件. 所有的订单在零时刻已经到达, 并且工件的加工是可中断的. 每个订单 i有一个权重 \omega_i, 定义订单 i 的完工时间 C_i 为订单 i 最后一个完工工件的完工时间. 目标是找到一个可行排序使得加权总完工时间\sum\limits_{i=1}^n \omega_iC_i 最小. Leung等证明了这个问题是NP-难的, 给出了一个近似算法, 并且分析了该算法的最坏情况界. 但是定理2的证明存在一些错误. 证明了尽管定理2的证明过程存在错误, 但是其结论仍然正确. 另外, 对上述模型的一种特殊情形给出了更好的近似算法.  相似文献   

8.
The paper presents a generalized economic manufacturing quantity model for an unreliable production system in which the production facility may shift from an ‘in-control’ state to an ‘out-of-control’ state at any random time (when it starts producing defective items) and may ultimately break down afterwards. If a machine breakdown occurs during a production run, then corrective repair is done; otherwise, preventive repair is performed at the end of the production run to enhance the system reliability. The proposed model is formulated assuming that the time to machine breakdown, corrective and preventive repair times follow arbitrary probability distributions. However, the criteria for the existence and uniqueness of the optimal production time are derived under general breakdown and uniform repair time (corrective and preventive) distributions. The optimal production run time is determined numerically and the joint effect of process deterioration, machine breakdowns and repairs (corrective and preventive) on the optimal decisions is investigated for a numerical example.  相似文献   

9.
10.
The problem of sequencing jobs on a single machine to minimize total tardiness is considered. An algorithm, which decomposes the problem into subproblems which are then solved by dynamic programming when they are sufficiently small, is presented and is tested on problems with up to 100 jobs.  相似文献   

11.
Under study is the classical NP-hard problem with three machines: N tasks must be fulfilled at three machines in minimum time. The processing time is given of each task at each machine. The processing sequences of all tasks are identical. It is impossible to process two tasks at one machine at the same time. We address the properties of this problem, find a new polynomially solvable case, and discuss a corresponding algorithm.  相似文献   

12.
We address a single-machine batch scheduling problem to minimize total flow time. Processing times are assumed to be identical for all jobs. Setup times are assumed to be identical for all batches. As in many practical situations, batch sizes may be bounded. In the first setting studied in this paper, all batch sizes cannot exceed a common upper bound. In the second setting, all batch sizes share a common lower bound. An optimal solution consists of the number of batches and their (integer) size. We introduce an efficient solution for both problems.  相似文献   

13.
In this paper we research the single machine stochastic JIT scheduling problem subject to the machine breakdowns for preemptive-resume and preemptive-repeat.The objective function of the problem is the sum of squared deviations of the job-expected completion times from the due date.For preemptive-resume,we show that the optimal sequence of the SSDE problem is V-shaped with respect to expected processing times.And a dynamic programming algorithm with the pseudopolynomial time complexity is given.We discuss the difference between the SSDE problem and the ESSD problem and show that the optimal solution of the SSDE problem is a good approximate optimal solution of the ESSD problem,and the optimal solution of the SSDE problem is an optimal solution of the ESSD problem under some conditions.For preemptive-repeat,the stochastic JIT scheduling problem has not been solved since the variances of the completion times cannot be computed.We replace the ESSD problem by the SSDE problem.We show that the optimal sequence of the SSDE problem is V-shaped with respect to the expected occupying times.And a dynamic programming algorithm with the pseudopolynomial time complexity is given.A new thought is advanced for the research of the preemptive-repeat stochastic JIT scheduling problem.  相似文献   

14.
In this paper, a tabu search approach is proposed for solving the single machine mean tardiness scheduling problem. Simulation experiment results obtained from the tabu search approach and three other heuristics are compared. Although computation time is increased, the results indicate that the proposed approach provides a much better solution than the other three approaches.  相似文献   

15.
This paper gives an O(nnlog3n) time algorithm for the chance-constrained sequencing problem on a single machine, where n is the number of jobs and the objective is to minimize the number of jobs which are early with probability not smaller than α (a given constant) against the common due time d.  相似文献   

16.
In this paper, a new memetic algorithm (MA) for the total tardiness single machine scheduling (SMS) problem with due dates and sequence-dependent setup times is proposed. The main contributions with respect to the implementation of the hybrid population approach are a hierarchically structured population conceived as a ternary tree and the evaluation of three recombination operators. Concerning the local improvement procedure, several neighborhood reduction schemes are developed and proved to be effective when compared to the complete neighborhood. Results of computational experiments are reported for a set of randomly generated test problems. The memetic approach and a pure genetic algorithm (GA) version are compared with a multiple start algorithm that employs the all-pairs neighborhood as well as two constructive heuristics.  相似文献   

17.
In this study, a tabu search (TS) approach to the single machine total weighted tardiness problem (SMTWT) is presented. The problem consists of a set of independent jobs with distinct processing times, weights and due dates to be scheduled on a single machine to minimize total weighted tardiness. The theoretical foundation of single machine scheduling with due date related objectives reveal that the problem is NP-hard, rendering it a challenging area for meta-heuristic approaches. This paper presents a totally deterministic TS algorithm with a hybrid neighborhood and dynamic tenure structure, and investigates the strength of several candidate list strategies based on problem specific characteristics in increasing the efficiency of the search. The proposed TS approach yields very high quality results for a set of benchmark problems obtained from the literature.  相似文献   

18.
We study a single machine scheduling problem with availability constraints and sequence-dependent setup costs, with the aim of minimizing the makespan. To the authors’ knowledge, this problem has not been treated as such in the operations research literature. We derive in this paper a mixed integer programming model to deal with such scheduling problem. Computational tests showed that commercial solvers are capable of solving only small instances of the problem. Therefore, we propose two ways for reducing the execution time, namely a valid inequality that strengthen the linear relaxation and an efficient heuristic procedure that provides a starting feasible solution to the solver. A substantial gain is achieved both in terms of the linear programming relaxation bound and in terms of the time to obtain an integer optimum when we use the enhanced model in conjunction with providing to the solver the solution obtained by the proposed heuristic.  相似文献   

19.
20.
本文研究了带运输机的单机在线调度问题。问题假设工件实时在线到达,系统中有一台运输机,该运输机每次最多运输$k$个工件,每个工件需要先在单机上完成加工,然后再被运输机运往目的地,问题的优化目标为最小化完工时间,即所有工件被加工完并且运往目的地的时间最短。针对该问题,作者研究了工件满足一致性条件的模型,并且基于贪心思想给出了竞争比为$\frac{\sqrt{5}+1}{2}$的在线算法,并且证明该算法是最优在线算法。  相似文献   

设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号