共查询到20条相似文献,搜索用时 46 毫秒
1.
Win-Chin Lin Chin-Chia Wu Kejian Yu Yong-Han Zhuang Shang-Chia Liu 《Intelligent Automation and Soft Computing》2018,24(4):671-681
Most research studies on scheduling problems assume that a job visits certain machines only one time.
However, this assumption is invalid in some real-life situations. For example, a job may be processed
by the same machine more than once in semiconductor wafer manufacturing or in a printed circuit
board manufacturing machine. Such a setting is known as the “re-entrant flowshop”. On the other
hand, the importance of learning effect present in many practical situations such as machine shop, in
different branches of industry and for a variety of corporate activities, in shortening life cycles, and in
an increasing diversity of products in the manufacturing environment. Inspired by these observations,
this paper addresses a re-entrant m-machine flowshop scheduling problems with time-dependent
learning effect to minimize the total tardiness. The complexity of the proposed problem is very difficult.
Therefore, in this paper we first present four heuristic algorithms, which are modified from existing
algorithms to solve the problem. Then, we use the solutions as four initials to a genetic algorithm.
Finally, we report experimental performances of all the proposed methods for the small and big
numbers of jobs, respectively 相似文献
2.
《Computers & Operations Research》2002,29(8):995-1007
This paper considers a scheduling problem for a single burn-in oven in the semiconductor manufacturing industry where the oven is a batch processing machine and each batch processing time is represented by the largest processing time among those of all the jobs contained in the batch. Each job belongs to one of the given number of families. Moreover, the release times of the jobs are different from one another. The objective measure of the problem is the maximum completion time (makespan) of all jobs. A dynamic programming algorithm is proposed in the order of polynomial time complexity for a situation where the number of job families is given (fixed). A computational experiment is performed to compare the time complexity of the proposed algorithm with that of another exact algorithm evaluating all possible job sequences based on batching-dynamic programming (BDP). The results of the experiment show that the proposed algorithm is superior to the other.Scope and purposeThis paper considers a scheduling problem on the burn-in operation in a semiconductor manufacturing process. The burn-in operation is a bottleneck process in the final testing process which is one of four major steps including wafer fabrication, wafer probe, assembly, and final testing steps. Thus, its scheduling is very important to improve the productivity of the whole manufacturing line. The objective of this paper is to find a solution technique that will find the optimal schedule that minimizes makespan for problems which are found in the semiconductor manufacturing industry. 相似文献
3.
Algorithms for scheduling incompatible job families on single batching machine with limited capacity
Motivated by applications in food processing and semiconductor manufacturing industries, we consider the scheduling problem of a batching machine with jobs of multiple families. The machine has a limited capacity to accommodate jobs. The jobs are in arbitrary sizes and multiple families. Jobs from different families cannot be processed in a batch. We show the problems of minimizing makespan and total batch completion time are both NP-hard in the strong sense. We present a mixed integer programming model for the problems. Then we propose two polynomial time heuristics based on longest processing time first rule and first fit rule. For the special case where a larger job also has a longer processing time, the heuristic for minimizing makespan is optimal. For the general case, we show the performance guarantee of the methods for the two objectives respectively. 相似文献
4.
5.
《Computers & Industrial Engineering》2007,52(1):41-56
This study considers the job scheduling problem of minimizing the weighted waiting time variance (WWTV) of jobs. It is an extension of WTV minimization problems in which we schedule a batch of n jobs, for servicing on a single resource, in such a way that the variance of their waiting times is minimized. WWTV minimization finds its applications for job scheduling in manufacturing systems with earliness and tardiness (E/T) penalties, in computer and networks systems for the stabilized QoS, and in other fields where it is desirable to minimize WWTV of jobs with different weights for priorities. We formulate a WWTV problem as an integer programming problem, prove the V-shape property for agreeably weighted WWTV problems and the nondelay property for general WWTV problems, and discover the strong V-Shape tendency of the optimal job sequences for this problem. Two job scheduling algorithms, Weighted Verified Spiral (WVS) and Weighted Simplified Spiral (WSS), are developed for the WWTV problems. Numerical testing shows that WVS and WSS significantly outperform existing WWTV algorithms. 相似文献
6.
Multiobjective evolutionary algorithm for manufacturing scheduling problems: state-of-the-art survey
Scheduling is an important tool for a manufacturing system, where it can have a major impact on the productivity of a production process. In order to find an optimal solution to scheduling problems it gives rise to complex combinatorial optimization problems. Unfortunately, most of them fall into the class of NP-hard combinatorial problems. In this paper, we focus on the design of multiobjective evolutionary algorithms (MOEAs) to solve a variety of scheduling problems. Firstly, we introduce fitness assignment mechanism and performance measures for solving multiple objective optimization problems, and introduce evolutionary representations and hybrid evolutionary operations especially for the scheduling problems. Then we apply these EAs to the different types of scheduling problems, included job shop scheduling problem (JSP), flexible JSP, Automatic Guided Vehicle (AGV) dispatching in flexible manufacturing system (FMS), and integrated process planning and scheduling (IPPS). Through a variety of numerical experiments, we demonstrate the effectiveness of these Hybrid EAs (HEAs) in the widely applications of manufacturing scheduling problems. This paper also summarizes a classification of scheduling problems, and illustrates the design way of EAs for the different types of scheduling problems. It is useful to guide how to design an effective EA for the practical manufacturing scheduling problems. As known, these practical scheduling problems are very complex, and almost is a combination of different typical scheduling problems. 相似文献
7.
《Journal of Parallel and Distributed Computing》2005,65(7):843-856
The master–slave scheduling model is a new model recently introduced by Sahni. It has many important applications in parallel computer scheduling and industrial settings such as semiconductor testing, machine scheduling, etc. In this model each job is associated with a preprocessing task, a slave task and a postprocessing task that must be executed in this order. While the preprocessing and postprocessing tasks are scheduled on the master machine, the slave tasks are scheduled on the slave machines. In this paper, we consider scheduling problems on single-master master–slave systems. We first strengthen some previously known complexity results for makespan problems, by showing them to be strongly NP-hard. We then show that the problem of minimizing the mean flowtime is strongly NP-hard even under severe constraints. Finally, we propose some heuristics for the mean flowtime and makespan problems subject to some constraints, and we analyze the worst-case performance of these heuristics. 相似文献
8.
Yasin Gocgun 《Computers & Operations Research》2012,39(10):2323-2336
Diverse applications in manufacturing, logistics, health care, telecommunications, and computing require that renewable resources be dynamically scheduled to handle distinct classes of job service requests arriving randomly over slotted time. These dynamic stochastic resource scheduling problems are analytically and computationally intractable even when the number of job classes is relatively small. In this paper, we formally introduce two types of problems called allocation and advanced scheduling, and formulate their Markov decision process (MDP) models. We establish that these MDPs are “weakly coupled” and exploit this structural property to develop an approximate dynamic programming method that uses Lagrangian relaxation and constraint generation to efficiently make good scheduling decisions. In fact, our method is presented for a general class of large-scale weakly coupled MDPs that we precisely define. Extensive computational experiments on hundreds of randomly generated test problems reveal that Lagrangian decisions outperform myopic decisions with a statistically significant margin. The relative benefit of Lagrangian decisions is much higher for advanced scheduling than for allocation scheduling. 相似文献
9.
Rene DriesselLars Mönch 《Computers & Industrial Engineering》2011,61(2):336-345
In this paper, we discuss a scheduling problem for jobs on identical parallel machines. Ready times of the jobs, precedence constraints, and sequence-dependent setup times are considered. We are interested in minimizing the performance measure total weighted tardiness that is important for achieving good on-time delivery performance. Scheduling problems of this type appear as subproblems in decomposition approaches for large scale job shops with automated transport of the jobs as, for example, in semiconductor manufacturing. We suggest several variants of variable neighborhood search (VNS) schemes for this scheduling problem and compare their performance with the performance of a list based scheduling approach based on the Apparent Tardiness Cost with Setups and Ready Times (ATCSR) dispatching rule. Based on extensive computational experiments with randomly generated test instances we are able to show that the VNS approach clearly outperforms heuristics based on the ATCSR dispatching rule in many situations with respect to solution quality. When using the schedule obtained by ATCSR as an initial solution for VNS, then the entire scheme is also fast and can be used as a subproblem solution procedure for complex job shop decomposition approaches. 相似文献
10.
The use of intelligent techniques in the manufacturing field has been growing the last decades due to the fact that most manufacturing optimization problems are combinatorial and NP hard. This paper examines recent developments in the field of evolutionary computation for manufacturing optimization. Significant papers in various areas are highlighted, and comparisons of results are given wherever data are available. A wide range of problems is covered, from job shop and flow shop scheduling, to process planning and assembly line balancing 相似文献
11.
This paper investigates a difficult scheduling problem on a specialized two-stage hybrid flow shop with multiple processors that appears in semiconductor manufacturing industry, where the first and second stages process serial jobs and parallel batches, respectively. The objective is to seek job-machine, job-batch, and batch-machine assignments such that makespan is minimized, while considering parallel batch, release time, and machine eligibility constraints. We first propose a mixed integer programming (MIP) formulation for this problem, then gives a heuristic approach for solving larger problems. In order to handle real world large-scale scheduling problems, we propose an efficient dispatching rule called BFIFO that assigns jobs or batches to machines based on first-in-first-out principle, and then give several reoptimization techniques using MIP and local search heuristics involving interchange, translocation and transposition among assigned jobs. Computational experiments indicate our proposed re-optimization techniques are efficient. In particular, our approaches can produce good solutions for scheduling up to 160 jobs on 40 machines at both stages within 10?min. 相似文献
12.
13.
In a manufacturing or service system, the actual processing time of a job can be controlled by the amount of an indivisible resource allocated, such as workers or auxiliary facilities. In this paper, we consider unrelated parallel-machine scheduling problems with discrete controllable processing times. The processing time of a job is discretely controllable by the allocation of indivisible resources. The planner must make decisions on whether or how to allocate resources to jobs during the scheduling horizon to optimize the performance measures. The objective is to minimize the total cost including the cost measured by a standard criterion and the total processing cost. We first consider three scheduling criterions: the total completion time, the total machine load, and the total earliness and tardiness penalties. If the number of machines and the number of possible processing times are fixed, we develop polynomial time algorithms for the considered problems. We then consider the minimization problem of the makespan cost plus the total processing cost and present an integer programming method and a heuristic method to solve the studied problem. 相似文献
14.
15.
16.
Rapid developments in computerized manufacturing environments and increasing overlapping in the capability of manufacturing
resources provoked integration of many manufacturing functions including process planning scheduling. Several approaches have
been developed in the literature in order to integrate process planning and scheduling. In this paper a novel approach which
makes use of grammatical representation of generic process plans is used within a multiple objective tabu search framework
in order to integrate process planning and scheduling effectively. Detailed explanations along with an example problem are
presented in the paper. Proposed approach is tested on literature problems and also hypothetically generated flexible job
shop scheduling problems with alternative process plans to analyze its performance and efficiency. 相似文献
17.
云制造技术给制造企业带来机遇的同时,也为其制造执行系统MES的设计与实现带来了新的挑战。为了解决单件小批MES中作业计划与调度优化问题,首先设计了一个从作业计划静态制定,到作业执行情况实时监控与主动感知,再到异常事件智能响应,最后到作业调度动态调节的闭环体系结构。接着针对异常信息实时获取与异常事件发现、异常事件智能化处理以及作业计划与调度优化算法计算能力服务化三个子问题,依次进行了问题分析并给出了技术解决方案。最后,以哈尔滨电机厂为案例对象,综合利用IEC/ISO 62264标准、大数据分析与挖掘方法以及由虚拟化、服务化和SOA等组成的云计算技术实现了单件小批MES作业计划与调度综合优化系统,验证了上述理论与方法的有效性。 相似文献
18.
Manufacturing job shop scheduling is a notoriously difficult problem that lends itself to various approaches - from optimal algorithms to suboptimal heuristics. We combined popular heuristic job shop-scheduling approaches with emerging AI techniques to create a dynamic and responsive scheduler. We fashioned our job shop scheduler's architecture around recent holonic manufacturing systems architectures and implemented our system using multiagent systems. Our scheduling approach is based on evolutionary algorithms but differs from common approaches by evolving the scheduler rather than the schedule. A holonic, multiagent systems approach to manufacturing job shop scheduling evolves the schedule creation rules rather than the schedule itself. The authors test their approach using a benchmark agent-based scheduling problem and compare performance results with other heuristic-scheduling approaches. 相似文献
19.
Ikno Kim Junzo Watada Ichiro Shigaki 《Soft Computing - A Fusion of Foundations, Methodologies and Applications》2008,12(2):121-128
Hydraulic cylinders perform straight-line reciprocating movements, and they have been used widely in various forms in many
different industries. In this paper, we select a sample of the various types of standard hydraulic cylinders. Each cylinder’s
near-optimal processing time and the processing order of the cylinder’s parts are investigated using two different techniques.
First, we study typical procedures, known as ‘Dispatching Rules’, which would be used in a job shop to resolve scheduling
problems. Second, we investigate another kind of technique, called ‘Genetic Algorithms’. The goal of this paper, we show that
efficient scheduling solutions are calculated by using dispatching rules and genetic algorithms for manufacturing standard
hydraulic cylinders, and we propose that a way to use dispatching rules in association with genetic algorithms should be considered
for resolving job shop scheduling problems. 相似文献
20.
Semiconductor manufacturing is one of the most complicated production processes with the challenges of dynamic job arrival, job re-circulation, shifting bottlenecks, and lengthy fabrication process. Owing to the lengthy wafer fabrication process, work in process (WIP) usually affects the cycle time and throughput in the semiconductor fabrication. As the applications of semiconductor have reached the era of consumer electronics, time to market has played an increasingly critical role in maintaining a competitive advantage for a semiconductor company. Many past studies have explored how to reduce the time of scheduling and dispatching in the production cycle. Focusing on real settings, this study aims to develop a manufacturing intelligence approach by integrating Gauss-Newton regression method and back-propagation neural network as basic model to forecast the cycle time of the production line, where WIP, capacity, utilization, average layers, and throughput are rendered as input factors for indentifying effective rules to control the levels of the corresponding factors as well as reduce the cycle time. Additionally, it develops an adaptive model for rapid response to change of production line status. To evaluate the validity of this approach, we conducted an empirical study on the demand change and production dynamics in a semiconductor foundry in Hsinchu Science Park. The approach proved to be successful in improving forecast accuracy and realigning the desired levels of throughput in production lines to reduce the cycle time. 相似文献