Scheduling a dynamic job shop production system with sequence-dependent setups: An experimental study

This paper presents the salient aspects of a simulation-based experimental study of scheduling rules for scheduling a dynamic job shop in which the setup times are sequence dependent. A discrete event simulation model of the job shop system is developed for the purpose of experimentation. Seven scheduling rules from the literature are incorporated in the simulation model. Five new setup-oriented scheduling rules are proposed and implemented. Simulation experiments have been conducted under various experimental conditions characterized by factors such as shop load, setup time ratios and due date tightness. The results indicate that setup-oriented rules provide better performance than ordinary rules. The difference in performance between these two groups of rules increases with increase in shop load and setup time ratio. One of the proposed rules performs better for mean flow time and mean tardiness measures.     

Customized job shop scheduling application development

This paper discusses development of a customized job shop scheduling application. Effective shop floor control relies heavily on the scheduling of part production through work centers. Production without part schedules and sequences is inefficient for job shops. Standard off-the-shelf scheduling software will typically not do the job. Customized scheduling software was developed to both increase manufacturing control while meeting all the requirements of a job shop's production processes, using the least slack rule for sequencing parts in order to meet final assembly schedules.     

Flow shop scheduling with multiple operations and time lags

A scheduling system is proposed and developed for a special type of flow shop. In this flow shop there is one machine at each stage. A job may require multiple operations at each stage. The first operation of a job on stage j cannot start until the last operation of the job on stage j - 1 has finished. Pre-emption of the operations of a job is not allowed. The flow shop that the authors consider has another feature, namely time lags between the multiple operations of a job. To move from one operation of a job to another requires a finite amount of time. This time lag is independent of the sequence and need not be the same for all operations or jobs. During a time lag of a job, operations of other jobs may be processed. This problem originates from a flexible manufacturing system scheduling problem where, between operations of a job on the same workstation, refixturing of the parts has to take place in a load/unload station, accompanied by (manual) transportation activities. In this paper a scheduling system is proposed in which the inherent structure of this flow shop is used in the formulation of lowerbounds on the makespan. A number of lowerbounds are developed and discussed. The use of these bounds makes it possible to generate a schedule that minimizes makespan or to construct approximate solutions. Finally, some heuristic procedures for this type of flow shop are proposed and compared with some well-known heuristic scheduling rules for job shop/flow shop scheduling.An earlier version of this paper was presented at the First International Conference on Industrial Engineering and Production Management 1993, 2–4 June 1993, Mons, Belgium.     

遗传算法解柔性作业车间调度问题应用综述

柔性作业车间调度问题是典型的NP难问题,对实际生产应用具有指导作用。近年来,随着遗传算法的发展,利用遗传算法来解决柔性作业车间调度问题的思想和方法层出不穷。为了促进遗传算法求解柔性作业车间调度问题的进一步发展,阐述了柔性作业车间调度问题的研究理论,对已有改进方法进行了分类,通过对现存问题的分析,探讨了未来的发展方向。     

相关工件车间调度问题的拓扑算法

针对加工装配型离散制造企业实际生产的特点,提出了一类用于表示工序之间偏序关系的相关工件车间调度问题。为了利用已有的求解表示工序之间的线序关系的传统车间调度算法求解相关工件车间调度问题,设计了一种拓扑算法,该算法能够将工序之间的偏序关系转化为线序关系,将相关工件车间调度问题转化为传统的车间调度问题,通过实证研究,结果表明了拓扑算法是可行和高效的。     

Simulation studies in job shop sheduling—I a survey

The dynamic job shop scheduling problem has been studied extensively during the last two decades. Because of the complexity of the dynamic job shop scheduling problem, numerous simulation studies have been conducted and published in the area. These studies fall into one of the following categories: the studies comparing and/or developing scheduling rules which will give good shop performance under a given set of job and shop parameters, and the studies investigating sensitivity of shop performance to job and shop parameters under a given set of scheduling rules. In the literature, shop performance has been evaluated in terms of (1) criteria based on job completion times, (2) criteria based on due dates, (3) criteria based on costs. This paper discusses approaches taken in major simulation studies of dynamic job shop scheduling problem according to the above classification.     

车间调度中的数据挖掘技术研究

基于Multi-Agent System（MAS）的人机合作技术适合于解决复杂调度问题。为了使人与机能够更好地合作来完成高效、准确的车间调度,引入C4.5算法,建立并实现了基于机器学习和MAS的人机合作车间调度系统仿真模型。在Java环境下,以Weka、JADE为开发平台,以Eclipse为开发工具,Access为后台数据库,完成了系统的开发。通过实例仿真和结果分析,运用机器学习算法动态调度的结果稍优于最佳的静态调度结果,证明了系统的正确性和优越性。     

Group shops scheduling with makespan criterion subject to random release dates and processing times

This paper deals with a stochastic group shop scheduling problem. The group shop scheduling problem is a general formulation that includes the other shop scheduling problems such as the flow shop, the job shop and the open shop scheduling problems. Both the release date of each job and the processing time of each job on each machine are random variables with known distributions. The objective is to find a job schedule which minimizes the expected makespan. First, the problem is formulated in a form of stochastic programming and then a lower bound on the expected makespan is proposed which may be used as a measure for evaluating the performance of a solution without simulating. To solve the stochastic problem efficiently, a simulation optimization approach is developed that is a hybrid of an ant colony optimization algorithm and a heuristic algorithm to generate good solutions and a discrete event simulation model to evaluate the expected makespan. The proposed approach is tested on instances where the random variables are normally, exponentially or uniformly distributed and gives promising results.     

An expert system for the selection of scheduling rules in a job shop

This paper presents a conceptual framework for the application of expert systems for the selection and development of scheduling rules for a job shop. A portion of the framework is illustrated using an expert system developed using MI™.     

A heuristic procedure for makespan minimization in job shops with multiple identical processors

Scheduling has been and continues to be a major issue in production planning. Job shop scheduling is one area where a considerable amount of research has been and continues to be pursued. Usual emphasis is on one machine per work center job shop scheduling. There appears to be very limited literature available on scheduling a job shop problem which requires scheduling of n jobs in m machine centers where each machine center may have k number of identical processors (though the number of identical processors may vary from one machine center to next). We discuss here, the problem of minimize of the makespan for such a job shop arrangement The problem can be represented by the symbol m x n x k.     

A heuristic algorithm for group scheduling

Group technology is a rapidly developing productivity improvement tool that can have a significant impact on the development of totally integrated manufacturing facilities and flexible manufacturing systems. Production scheduling associated with group technology is called “Group Scheduling”. There are many heuristic algorithms developed for general job shop applications based on unrealistic hypothesis, complicated computations etc., which are not addressed to group scheduling. In this paper, from the existing algorithms for group scheduling, a heuristic algorithm has been developed and programmed for computer/microcomputer applications. The developed algorithm has been used to determine the optimal group and the optimal job sequence for a batch type production process with functional layout. The developed algorithm is far simpler and easier to compute, compared to the other similar heuristic algorithms and certainly in comparison to other optimization methods such as branch and bound method.     

基于Petri网的JSP动态分类调度

以带有控制器的 Petri 网为建模工具对柔性生产调度中的离散事件建模,通过构建Petri 网控制器使系统的运行满足期望的目标,同时利用混合遗传算法获得调度结果,用于解决作业车间的加工受到机床、操作工人等资源制约条件下的动态优化调度。为了保证生产的平稳性,最大限度地维持车间的生产能力,提出了针对不同的扰动进行分类处理的新方法,首先基于机床故障修复时间、工人离岗时间及取消订单包含任务的多少进行分类调度,然后根据机床故障修复后以及工人回岗后剩余任务的多少决定是否进行再一次的调度,最后对算法进行了仿真研究。     

一种用于车间作业调度问题的智能枚举算法

车间作业调度问题是优化组合中一个著名的难题,即使规模不大的算例,优化算法的时间也很长。文章提出了一种求解车间作业调度问题的快速智能枚举算法,选取了22个标准算例作为算法的测试试验集,该算法在较短的时间内找到了17个算例的最优解,试验结果表明智能枚举算法确实是一种快速的、有效的求解车间作业调度问题的近似算法。     

Multiple criteria job-shop scheduling

This paper presents a programming model for job shop scheduling which can consider a multiple-performance system of evaluations and incorporate multiple organizational goals. While the discussion is centered on the scheduling model formulated by Pritsker, Watters and Wolfe [8], the approach may be implemented (and the associated advantages realized) with other programming formulations of the job shop scheduling problem.     

An integrated scheduler for manufacturing planning and control (INSCH)

The most basic problem in a manufacturing process is to create valid scheduling system which determines the sequence of jobs to be processed at each of the series of machine centers. An integrated scheduler (INSCH) is developed for small job shop manufacturing systems while considering high machine utilization, low work-in-process, and reduced job lateness.

As an and to understand the interaction of live jobs with the shop, sequence scheduler is developed to complement production scheduler such as Gantt bar chart. INSCH can achieve better performance than simple static models as shown in an example. It is desirable for INSCH to be applied to small job shop manufacturing companies using micro personal computer with relevant modifications discussed.     

基于Agent的分布式动态作业车间调度

Agent技术是分布式工业系统建模的一种重要方法．本文对Agent及多Agent技术进 行了简要总结,综述了Agent技术在制造作业车间调度中的应用研究概况,提出了一种基于 合同网协议投标机制的多Agent分布式动态作业车间调度方案．     

考虑工件移动时间的柔性作业车间调度问题研究

分析生产车间的实际生产状况,建立了考虑工件移动时间的柔性作业车间调度问题模型,该模型考虑了以往柔性作业车间调度问题模型所没有考虑的工件在加工机器间的移动时间,使柔性作业车间调度问题更贴近实际生产,让调度理论更具现实性。通过对已有的改进遗传算法的遗传操作进行重构,设计出有效求解考虑工件移动时间的柔性作业车间调度问题的改进遗传算法。最后对实际案例进行求解,得到调度甘特图和析取图,通过对甘特图和析取图的分析验证了所建考虑工件移动时间的柔性作业车间调度问题模型的可行性和有效性。     

Multi-objective flexible job shop schedule: Design and evaluation by simulation modeling

Flexible job shop schedule is very important in both fields of combinatorial optimization and production management. In this paper, a simulation model is presented to solve the multi-objective flexible job shop scheduling problem. The proposed model has been coded by Matlab which is a special mathematical computation language. After modeling the pending problem, the model is validated by five representative instances based on practical data. The results obtained from the computational study have shown that the proposed approach is a feasible and effective approach for the multi-objective flexible job shop scheduling problem.     

Dynamic scheduling of manufacturing job shops using genetic algorithms

Most job shop scheduling methods reported in the literature usually address the static scheduling problem. These methods do not consider multiple criteria, nor do they accommodate alternate resources to process a job operation. In this paper, a scheduling method based on genetic algorithms is developed and it addresses all the shortcomings mentioned above. The genetic algorithms approach is a schedule permutation approach that systematically permutes an initial pool of randomly generated schedules to return the best schedule found to date.A dynamic scheduling problem was designed to closely reflect a real job shop scheduling environment. Two performance measures, namely mean job tardiness and mean job cost, were used to demonstrate multiple criteria scheduling. To span a varied job shop environment, three factors were identified and varied between two levels each. The results of this extensive simulation study indicate that the genetic algorithms scheduling approach produces better scheduling performance in comparison to several common dispatching rules.     

Mixed binary integer programming formulations for the reentrant job shop scheduling problem

This paper describes the development of mixed binary integer programming (BIP) formulations for the reentrant job shop scheduling problem. Based on an earlier classical job shop model developed by Manne and improved by Liao and You, this paper presents two extended BIP optimization formulations for the problem under consideration. In order to improve the solution speed of the BIP formulations, two layer division procedures are developed and incorporated in the corresponding models. Results of computational experiments, in which an average performance of these formulations is investigated, are also reported.