共查询到20条相似文献,搜索用时 31 毫秒
1.
Lars Mönch Rene Schabacker Detlef Pabst John W. Fowler 《European Journal of Operational Research》2007
In this paper, we consider a modified shifting bottleneck heuristic for complex job shops. The considered job shop environment contains parallel batching machines, machines with sequence-dependent setup times and reentrant process flows. Semiconductor wafer fabrication facilities (Wafer Fabs) are typical examples for manufacturing systems with these characteristics. Our primary performance measure is total weighted tardiness (TWT). The shifting bottleneck heuristic uses a disjunctive graph to decompose the overall scheduling into scheduling problems for single tool groups. The scheduling algorithms for these scheduling problems are called subproblem solution procedures (SSPs). In previous research, only subproblem solution procedures based on dispatching rules have been considered. In this paper, we are interested in how much we can gain in terms of TWT if we apply more sophisticated subproblem solution procedures like genetic algorithms for parallel machine scheduling. We conduct simulation experiments in a dynamic job shop environment in order to assess the performance of the suggested subproblem solution procedures. It turns out that using near to optimal subproblem solution procedures leads in many situations to improved results compared to dispatching-based subproblem solution procedures. 相似文献
2.
Ji-Bo Wang 《Journal of Applied Mathematics and Computing》2005,18(1-2):383-391
The paper is devoted to some flow shop scheduling problems, where job processing times are defined by functions dependent on their positions in the schedule. An example is constructed to show that the classical Johnson's rule is not the optimal solution for two different models of the two-machine flow shop scheduling to minimize makespan. In order to solve the makespan minimization problem in the two-machine flow shop scheduling, we suggest Johnson's rule as a heuristic algorithm, for which the worst-case bound is calculated. We find polynomial time solutions to some special cases of the considered problems for the following optimization criteria: the weighted sum of completion times and maximum lateness. Some furthermore extensions of the problems are also shown. 相似文献
3.
A Petri Net based algorithm for minimizing total tardiness in flexible manufacturing systems 总被引:1,自引:0,他引:1
Petri Nets have been extensively used for modeling and simulating of the dynamics of flexible manufacturing systems. Petri
Nets can capture features such as parallel machines, alternative routings, batch sizes, multiplicity of resources, to name
but a few. However, Petri Nets have not been very popular for scheduling in manufacturing due to the Petri Net “state explosion”
combined with the NP-hard nature of many of such problems. A promising approach for scheduling consists of generating only
portions of the Petri Net state space with heuristic search methods. Thus far, most of this scheduling work with Petri Nets
has been oriented to minimize makespan. The problem of minimizing total tardiness and other due date-related criteria has
received little attention. In this paper, we extend the Beam A* Search algorithm presented in a previous work with capability to handle the total tardiness criterion. Computational tests
were conducted on Petri Net models of both flexible job shop and flexible manufacturing systems. The results suggest that
the Petri Net approach is also valid to minimize due date related criteria in flexible systems. 相似文献
4.
Folarin B. Oyebolu Jeroen van Lidth de Jeude Cyrus Siganporia Suzanne S. Farid Richard Allmendinger Juergen Branke 《Journal of Heuristics》2017,23(4):231-256
Biopharmaceutical manufacturing requires high investments and long-term production planning. For large biopharmaceutical companies, planning typically involves multiple products and several production facilities. Production is usually done in batches with a substantial set-up cost and time for switching between products. The goal is to satisfy demand while minimising manufacturing, set-up and inventory costs. The resulting production planning problem is thus a variant of the capacitated lot-sizing and scheduling problem, and a complex combinatorial optimisation problem. Inspired by genetic algorithm approaches to job shop scheduling, this paper proposes a tailored construction heuristic that schedules demands of multiple products sequentially across several facilities to build a multi-year production plan (solution). The sequence in which the construction heuristic schedules the different demands is optimised by a genetic algorithm. We demonstrate the effectiveness of the approach on a biopharmaceutical lot sizing problem and compare it with a mathematical programming model from the literature. We show that the genetic algorithm can outperform the mathematical programming model for certain scenarios because the discretisation of time in mathematical programming artificially restricts the solution space. 相似文献
5.
Lin-Hui Sun Kai Cui Ju-Hong Chen Jun Wang Xian-Chen He 《Annals of Operations Research》2013,211(1):481-490
This article considers flow shop scheduling problems with a learning effect. By the learning effect, we mean that the processing time of a job is defined by a function of its position in a processing permutation. The objective is to minimize the total weighted completion time. Some heuristic algorithms by using the optimal permutations for the corresponding single machine scheduling problems are presented, and the worst-case bound of these heuristics are also analyzed. 相似文献
6.
A variable neighbourhood search for hybrid flow-shop scheduling problem with rework and set-up times
Hamidreza Eskandari Amirhamed Hosseinzadeh 《The Journal of the Operational Research Society》2014,65(8):1221-1231
This paper deals with hybrid flow-shop scheduling problem with rework. In this problem, jobs are inspected at the last stage, and poorly processed jobs were returned and processed again. Thus, a job may visit a stage more than once, and we have a hybrid flow-shop with re-entrant flow. This kind of a shop may occur in many industries, such as final inspection system in automotive manufacturing. The criterion is to minimize the makespan of the system. We developed a 0–1 mixed-integer program of the problem. Since the hybrid flow-shop scheduling problem is NP-hard, an algorithm for finding an optimal solution in polynomial time does not exist. So we generalized some heuristic methods based on several basic dispatching rules and proposed a variable neighbourhood search (VNS) for the problem with sequence-dependent set-up times and unrelated parallel machines. The computational experiments show that VNS provides better solutions than heuristic methods. 相似文献
7.
A flow shop with identical machines is called a proportionate flow shop. In this paper, we consider the variant of the n-job, m-machine proportionate flow shop scheduling problem in which only one machine is different and job processing times are inversely proportional to machine speeds. The objective is to minimize maximum completion time. We describe some optimality conditions and show that the problem is NP-complete. We provide two heuristic procedures whose worst-case performance ratio is less than two. Extensive experiments with various sizes are conducted to show the performance of the proposed heuristics. 相似文献
8.
Constraint Propagation and Problem Decomposition: A Preprocessing Procedure for the Job Shop Problem
In recent years, constraint propagation techniques have been shown to be highly effective for solving difficult scheduling problems. In this paper, we present an algorithm which combines constraint propagation with a problem decomposition approach in order to simplify the solution of the job shop scheduling problem. This is mainly guided by the observation that constraint propagation is more effective for small problem instances. Roughly speaking, the algorithm consists of deducing operation sequences that are likely to occur in an optimal solution of the job shop scheduling problem (JSP).The algorithm for which the name edge-guessing procedure has been chosen – since with respect to the job shop scheduling problem (JSP) the deduction of machine sequences is mainly equivalent to orienting edges in a disjunctive graph – can be applied in a preprocessing step, reducing the solution space, thus speeding up the overall solution process. In spite of the heuristic nature of edge-guessing, it still leads to near-optimal solutions. If combined with a heuristic algorithm, we will demonstrate that given the same amount of computation time, the additional application of edge-guessing leads to better solutions. This has been tested on a set of well-known JSP benchmark problem instances. 相似文献
9.
考虑具有机器适用限制的多个不同置换流水车间的调度问题. 机器适用限制指的是每个工件只能分配到其可加工工厂集合. 所有置换流水车间拥有的机器数相同但是具有不同的加工能力. 首先, 针对该问题建立了基于位置的混合整数线性规划模型; 进而, 对一般情况和三种特殊情况给出了具有较小近似比的多项式时间算法. 其次, 基于NEH方法提出了启发式算法NEHg, 并给出了以NEHg为上界的分支定界算法. 最后, 通过例子说明了NEHg启发式算法和分支定界算法的计算过程, 并进行大量的实验将NEHg与NEH算法结果进行比较, 从而验证了NEHg算法的有效性. 相似文献
10.
In many practical situations, batching of similar jobs to avoid setups is performed while constructing a schedule. This paper addresses the problem of non-preemptively scheduling independent jobs in a two-machine flow shop with the objective of minimizing the makespan. Jobs are grouped into batches. A sequence independent batch setup time on each machine is required before the first job is processed, and when a machine switches from processing a job in some batch to a job of another batch. Besides its practical interest, this problem is a direct generalization of the classical two-machine flow shop problem with no grouping of jobs, which can be solved optimally by Johnson's well-known algorithm. The problem under investigation is known to be NP-hard. We propose two O(n logn) time heuristic algorithms. The first heuristic, which creates a schedule with minimum total setup time by forcing all jobs in the same batch to be sequenced in adjacent positions, has a worst-case performance ratio of 3/2. By allowing each batch to be split into at most two sub-batches, a second heuristic is developed which has an improved worst-case performance ratio of 4/3. © 1998 The Mathematical Programming Society, Inc. Published by Elsevier Science B.V. 相似文献
11.
Inna G. Drobouchevitch H. Neil Geismar Chelliah Sriskandarajah 《European Journal of Operational Research》2010
We consider the problem of scheduling operations in a robotic cell processing a single part type. Each machine in the cell has a one-unit input buffer and a one-unit output buffer. The machines and buffers are served by one single gripper robot. The domain considered is free-pickup cells with additive inter-machine travel time. The processing constraints specify the cell to be a flow shop. The objective is to find a cyclic sequence of robot moves that minimizes the long-run average time to produce a part or, equivalently, maximizes throughput. Bufferless robotic cells have been studied extensively in the literature. However, the few studies of robotic cells with output buffers at each machine have shown that the throughput can be improved by such a configuration. We show that there is no throughput advantage in providing machine input buffers in addition to output buffers. The equivalence in throughput between the two models has significant practical implications, since the cost of providing additional buffers at each machine is substantial. 相似文献
12.
基于遗传算法的多目标柔性工作车间调度问题求解 总被引:1,自引:0,他引:1
本文针对柔性工作车间调度问题给出了一个有意义的综合目标尽可能缩短制造周期的同时尽可能的减少机器负荷。由于传统遗传算法在多目标柔性工作车间调度问题上的局限性,我们提出了一种改进遗传算法:首先,我们给出了针对综合目标的工序调度算法获得初始集合;接着,针对柔性工作车间调度问题的特点,我们在常用的基于工序顺序的编码方法上融入了基于机器分配的编码方法,并据此设计了相应的交叉变异操作;最后借鉴了物种进化现象中的环境迁移思想设计了解决多目标优化问题的迁移操作。实验结果表明,改进的遗传算法在多目标柔性工作车间调度问题的解决上要优于传统遗传算法。 相似文献
13.
14.
A real industrial production phenomenon, referred to as learning effects, has drawn increasing attention. However, most research on this issue considers only single machine problems. Motivated by this limitation, this paper considers flow shop scheduling problems with an exponential learning effect. By the exponential learning effect, we mean that the processing time of a job is defined by an exponent function of its position in a processing permutation. The objective is to minimize one of the four regular performance criteria, namely, the total completion time, the total weighted completion time, the discounted total weighted completion time, and the sum of the quadratic job completion times. We present heuristic algorithms by using the optimal permutations for the corresponding single-machine scheduling problems. We also analyse the worst-case bound of our heuristic algorithms. 相似文献
15.
Dispatching rules are simple scheduling heuristics that are widely applied in industrial practice. Their popularity can be attributed to their ability to flexibly react to shop floor disruptions that are prevalent in many real-world manufacturing environments. However, it is a challenging and time-consuming task to design local, decentralised dispatching rules that result in a good global performance of a complex shop.An evolutionary algorithm is developed to generate job shop problem instances for which an examined dispatching rule fails to achieve a good solution due to a single suboptimal decision. These instances can be easily analysed to reveal limitations of that rule which helps with the design of better rules. The method is applied to a job shop problem from the literature, resulting in new best dispatching rules for the mean flow time measure. 相似文献
16.
F. Guerriero 《Journal of Optimization Theory and Applications》2008,139(2):419-438
In this paper, we focus on heuristic approaches for solving the deterministic job shop scheduling problem. More specifically,
a new priority dispatch rule and hybrid rollout algorithms are developed for approaching the problem under consideration.
The proposed solution algorithms are tested on a set of instances taken from the literature and compared with other methods.
The computational results validate the effectiveness of the developed solution approaches and show that the proposed rollout
algorithms are competitive with respect to several state-of-art heuristics for solving the job shop scheduling problem.
The author thanks Dr. Marco Mancini and Dr. Alessandro Tarasio for valuable suggestions about computational issues. 相似文献
17.
This paper presents a tabu-search heuristic for the flexible-resource flow shop scheduling (FRFS) problem [7]. The FRFS problem generalizes the classic flow shop scheduling problem by allowing job-operation processing times to depend on the amount of resource assigned to an operation; the objective is to determine simultaneously the job sequence, resource-allocation policy, and operation start times that optimize system performance. The tabu-search heuristic (TSH) employs a nested-search strategy based on a decomposition of the FRFS problem into these three components. We discuss computational experience with the THS procedure on more than 1600 test problems. The results show that TSH is effective in obtaining near-optimal solutions to the FRFS test problems. In particular, TSH generates optimal solutions for more than 70% of the test problems for which optimal solutions are known; overall, these solutions are within 0.3% of optimality on the average, and within 2.5% of optimality in the worst case.This research was supported in part by National Science Foundation grant SES90-22940. 相似文献
18.
《European Journal of Operational Research》1988,34(2):208-220
The paper deals with a two-machine flow shop scheduling problem in which both the sequence of jobs and their processing times are decision variables. It is assumed that the cost of performing a job is a linear function of its processing time, and the schedule cost to be minimized is the total processing cost plus maximum completion time cost. In is shown that the decision form of this problem is NP-complete, even when the processing times on one machine only are controllable and all the processing cost units are identical. Two heuristic methods for solving the problem are proposed and their worst-case analysis is presented. 相似文献
19.
A real industrial production phenomenon, referred to as learning effects, has drawn increasing attention. However, most research
on this issue considers only single machine problems. Motivated by this limitation, this paper considers flow shop scheduling
problems with a general position-dependent learning effects. By the general position-dependent learning effects, we mean that
the actual processing time of a job is defined by a general non-increasing function of its scheduled position. The objective
is to minimize one of the five regular performance criteria, namely, the total completion time, the makespan, the total weighted
completion time, the total weighted discounted completion time, and the sum of the quadratic job completion times. We present
heuristic algorithms by using the optimal permutations for the corresponding single machine scheduling problems. We also analyze
the worst-case bound of our heuristic algorithms. 相似文献