Scheduling of a job-shop problem with limited output buffers

ABSTRACT

This article addresses a job-shop problem with limited output buffers (JS-LOB) with the objective of minimizing the process makespan. An integer nonlinear mathematical programming model is proposed to describe this problem. Based on the model, a two-stage algorithm consisting of obtaining feasible solutions and a local search is proposed to solve the JS-LOB problem. The local search has two operators: the first is a neighbourhood structure based on a disjunctive graph model, and the second is similar to crossover in the genetic algorithm to avoid falling into local optima. Computational results are presented for a set of benchmark tests. The results show the effectiveness of the proposed algorithm and indicate whether the processing time of the job conforms to a uniform distribution. When the proportion between the capacity of the buffer and the number of jobs is larger than 20%, the influence of the buffer becomes very small.     

Flow-shop problems with intermediate buffers

In this paper the following extension of the classical flow-shop problem is considered: Between each two consecutive machines a buffer of limited capacity is given. After finishing processing on a machine, a job either directly has to be processed on the following machine or it has to be stored in the buffer between these machines. If the buffer is completely occupied the job may wait on its current machine but blocks this machine for other jobs. The objective is to determine a feasible schedule minimizing the makespan. To model such a problem setting, a variation of the classical disjunctive graph model for shop problems is extended. A tabu search procedure is described where neighborhoods based on an extension of the classical block approach theorem are used. Computational results for extended flow-shop benchmark instances are presented. Corespondence to: Silvia HeitmannThe authors are grateful to Tim Nieberg for implementing the tabu search procedure proposed in this paper.S. Heitmann     

求解Job-shop调度问题的遗传算法

在引入一种新的具有自适应性的杂交概率和变异概率的基础上，提出了一种构造染色体的新方法，进而提出了一种面向工作车间问题的新的遗传算法。同时给出了一个例子来说明算法的收敛性和收敛效率。仿真结果表明了该算法的有效性。     

A two-machine permutation flow shop scheduling problem with buffers

Problems with blocking (limited intermediate storage space) are used frequently for modelling and scheduling just-in-time and flexible manufacturing systems. In this paper, an approximation algorithm is presented for the problem of finding the minimum makespan in a two-machine permutation flow-shop scheduling problem with the mediating buffer of finite capacity. The algorithm is based on the tabu search approach supported by the reduced neighborhood, search accelerator and technique of back jumps on the search trajectory. Due to some special properties, the proposed algorithm provides makespans very close to optimal in a short time. It has been shown that this algorithm outperforms all known approximation algorithms for the problem stated.     

基于MPSO的有限缓冲区多产品厂间歇调度问题的研究

研究了以最小化最大完工时间为目标的有限缓冲区多产品厂间歇调度问题,提出了一种基于多种群粒子群优化(MPSO)的间歇调度算法.该算法采用多种群,增加了种群初始粒子的多样性,在每一代子种群并行进化的过程中引入移民粒子,使子种群之间相互影响和促进,避免算法过早地陷入局部最优,提高了算法的全局搜索能力;每代进化后选出子种群中的优秀粒子作为精华种群,并对其进行变邻域搜索(VNS),进一步提高了算法的收敛精度.通过对不同规模调度问题的仿真,以及与其它算法的对比,证明了该算法解决有限缓冲区多产品厂间歇调度问题的有效性和优越性.     

基于有限生产能力和产出缓存的订单接受策略

研究了MTO(make-to-order)生产环境下,生产商在生产能力和产出缓存有限的情况下的订单接受决策问题.构建了一个整数规划模型将订单选择、交货期和生产计划决策结合起来,对订单进行选择性接受,使得制造商所获得的利润值最大.利用实际考察的企业历史数据对模型进行了算例分析,检验了需求分布和产出缓存对企业总利润的影响.结果表明,采用该模型对订单进行选择性接受,所得到的系统总利润明显高于企业采用旧有生产方式所获得的总利润.分析结果可以帮助MTO企业管理者在进行订单接受决策时提供有益的指导.     

智能车间调度系统中优化算法的研究

本文根据作业车间凋度问题的数学模型和特点，首先改进了经典的TS和SA算法，在此基础上提出了一套基于关键路理论的混合优化算法，实现了关键路理论和混合优化策略的有机结合；应用此算法对该调度问题的一些实例进行了计算验证，实践证明本算法能显著提高优化效果和效率。该套方法对实现自动化、智能化的车间调度系统提供了较好的算法支持。     

On the complexity of two machine job-shop scheduling with regular objective functions

For the nonpreemptive two machine job-shop scheduling problem with a fixed number of jobs and objective functions f _i and maxf _i , wheref _i are nondecreasing functions of the finish times of jobsi, polynomial algorithms are presented. This answers previous open questions about the complexity status of the corresponding problems with objective functionsL _max, w _i U _i , and w _i U. We generalize these results by showing that the problem with any regular criterion can be solved in polynomial time.Supported by the International Association for the promotion of cooperation with scientists from the independent states of the former Soviet Union, Project INTAS-93-257.     

Job-shop scheduling heuristics with local neighbourhood search

This paper investigates the suitability and performance of local-neighbourhood-search-based heuristics for job-shop scheduling problems. A procedure is developed which provides an objective assessment in terms of average and worst-case performance in relation to the computational complexity of the problem and the speed of the tree search. Solution improvements models and stopping rules are suggested.     

Tabu search for the job-shop scheduling problem with multi-purpose machines

In this paper we study the following generalization of the job-shop scheduling problem. Each operation can be performed by one machine out of a set of machines given for this operation. The processing time does not depend on the machine which has been chosen for processing the operation. This problem arises in the area of flexible manufacturing. As a generalization of the jobshop problem it belongs to the hardest problems in combinatorial optimization. We show that an application of tabu search techniques to this problem yields excellent results for benchmark problems.Supported by Deutsche Forschungsgemeinschaft, Project JoP-TAG     

Anticipation and flexibility in dynamic scheduling

Many real-world optimization problems change over time and require frequent re-optimization. We suggest that in such environments, an optimization algorithm should reflect the problem's dynamics and explicitly take into account that changes to the current solution are to be expected. We claim that this can be achieved by having the optimization algorithm search for solutions that are not only good, but also flexible, i.e. easily adjustable if necessary in the case of problem changes. For the example of a job-shop with jobs arriving non-deterministically over time, we demonstrate that avoiding early idle times increases flexibility, and thus that the incorporation of an early idle time penalty as secondary objective into the scheduling algorithm can greatly enhance the overall system performance.     

Integrating a decomposition procedure with problem reduction for factory scheduling with disruptions: a simulation study

Dispatching rules are widely used in industry because schedules obtained from optimization procedures can be difficult to implement in the face of executional uncertainties. Barua et al. (Barua, A., Narasimhan, R., Upasani, A. and Uzsoy, R., Implementing global factory schedules in the face of stochastic disruptions. Int. J. Prod. Res., 2005, 43(4), 793–818) implement global schedules obtained from an optimization-based heuristic using a dispatching rule, and outperform myopic dispatching rules in the face of disruptions. However, the computation of the global schedules is still time-consuming for realistic instances. Upasani et al. (Upasani, A., Uzsoy, R. and Sourirajan, K., A problem reduction approach for scheduling semiconductor wafer fabrication facilities. IEEE Trans. Semicon. Manuf., 2006, 19, 216–225) develop a problem reduction scheme based on load disparity between work centres, and report significant reduction in CPU times with minimal loss of solution quality in deterministic experiments. In this paper we integrate the problem-reduction scheme to obtain global schedules with the dispatching approach of Barua et al. (Barua, A., Narasimhan, R., Upasani, A. and Uzsoy, R., Implementing global factory schedules in the face of stochastic disruptions. Int. J. Prod. Res., 2005, 43(4), 793–818) in a multi-product environment with stochastic machine breakdowns and job arrivals. A simulation model of a scaled-down wafer fabrication facility is used to evaluate the performance of the proposed procedures. Results show that the integrated procedure outperforms the benchmark dispatching rules while significantly reducing computation times.     

Sequencing with limited flexibility

We consider the problem of resequencing a set of prearranged jobs when there is limited resequencing flexibility and sequence-dependent changeover costs. Resequencing flexibility is limited by how far forward or backward a job can shift in the sequence relative to its original position. We show how the problem can be solved using dynamic programming in polynomial time with respect to the number of jobs. We also show how the same solution approach can be extended to problems where sequencing constraints are job specific and to problems where job features, which determine changeover costs, are jointly determined with the job sequence. We provide an integer programming formulation to the resequencing problem whose linear programming relaxation offers a useful lower bound. We also describe a family of decomposition heuristics that are easy to customize to provide desired levels of solution quality and solution time. We document the quality of the lower bound from the linear programming relaxation and the upper bound from the heuristic using numerical results. We also provide numerical results to support managerial insights regarding the value of flexibility. We show that the value of flexibility is of the diminishing kind with most of the benefit realized with relatively limited flexibility. We also show that a balanced allocation of flexibility among forward and backward position shifting is superior to an unbalanced one. More significantly, we show that forward and backward position shifting flexibility are complements with the value of one increasing in the amount of the other. Finally, we apply our solution approach to a real-world case from the automotive industry.     

Flow shop scheduling with a batch processor and limited buffer

This paper addresses flow shop scheduling problem with a batch processor followed by a discrete processor. Incompatible job families and limited buffer size are considered, and the objective is to determine a schedule such that the total completion time is minimised. Flexible buffer service policy is designed, and a greedy heuristic together with the worst-case analysis is developed. We also propose a hybrid method involving a Differential Evolution algorithm. Moreover, two tight lower bounds are provided to measure the performances of the proposed algorithms. Numerical results demonstrate that the proposed algorithms are capable of providing high-quality solutions for large-scale problems within a reasonable computational time.     

Optimisation of flow-shop scheduling with batch processor and limited buffer

This paper deals with a flow-shop scheduling problem with limited intermediate buffer. Jobs are grouped in incompatible job families. Each job has to be processed by a batch processor followed by a discrete processor in the same order. The batch processor can process several jobs simultaneously so that all jobs of the same batch start and complete together. We assume that the capacity of batch processor is bounded. The batch processing time is identical for batches of the same family. A batch which has completed processing on the batch processor may block the processor until there is a free unit in the buffer. The objective is to determine a batching and scheduling for all jobs so as to minimise mean completion time. A lower bound and two heuristics algorithm are developed. Moreover, a two-stage method embedded with a Differential Evolution (DE) algorithm is also developed. DE is one of the latest evolutionary computation algorithms, which implements mutation, crossover, and selection operators to improve the candidate solutions iteratively. Three variants of DE are first compared with a continuous Genetic Algorithm employing the random key representation. Then, one variant of the DE with the best convergence speed is selected. Numerical experiments are conducted to evaluate the performances of the selected two-stage meta-heuristic and two heuristics.     

Job-shop问题基于RBF网络的自学习算法

通过对Job-shop问题分析,在逐步添加约束到有向图模型来获取可行调度方案基础上,提出一种具备自动学习功能智能算法.设计了可互换工序对4种选取函数,并以此作为网络输入构建了基于RBF的神经网络以实现对可互换工序对选取.利用最小均方算法对网络权重进行训练,经过对更新过的样本进行再学习后,网络选取可互换工序对的准确度得以提高,使算法具备自学习能力.数值仿真结果表明所提算法对于大规模Job-shop问题求解存在较好效果,具较好的应用价值.     

A parallel-machine scheduling problem with two competing agents

Scheduling with two competing agents has become popular in recent years. Most of the research has focused on single-machine problems. This article considers a parallel-machine problem, the objective of which is to minimize the total completion time of jobs from the first agent given that the maximum tardiness of jobs from the second agent cannot exceed an upper bound. The NP-hardness of this problem is also examined. A genetic algorithm equipped with local search is proposed to search for the near-optimal solution. Computational experiments are conducted to evaluate the proposed genetic algorithm.     

Iterated greedy algorithms to minimize the total family flow time for job-shop scheduling with job families and sequence-dependent set-ups

This study addresses a variant of job-shop scheduling in which jobs are grouped into job families, but they are processed individually. The problem can be found in various industrial systems, especially in reprocessing shops of remanufacturing systems. If the reprocessing shop is a job-shop type and has the component-matching requirements, it can be regarded as a job shop with job families since the components of a product constitute a job family. In particular, sequence-dependent set-ups in which set-up time depends on the job just completed and the next job to be processed are also considered. The objective is to minimize the total family flow time, i.e. the maximum among the completion times of the jobs within a job family. A mixed-integer programming model is developed and two iterated greedy algorithms with different local search methods are proposed. Computational experiments were conducted on modified benchmark instances and the results are reported.     

Assessing the resource usage in scheduling with incompatibilities

In the field of resource constrained scheduling, the papers in the literature are mainly focused on minimizing the maximum completion time of a set of tasks to be carried out, paying attention to respecting the maximum simultaneous availability of each resource type in the system. This work, instead, considers the issues of balancing the resource usage and minimizing the peak of the resources allocated each time in the schedule, while keeping the makespan low. To this aim we propose a local search algorithm which acts as a multi start greedy heuristic. Extensive experiments on various randomly generated test instances are provided. Furthermore, we present a comparison with lower bounds and known heuristics. Correspondence to: Massimiliano CaramiaWe wish to thank the anonymous referees for their useful comments which have led to this improved version of the paper.