Production sequencing problem with reentrant work flows and sequence dependent setup times

This paper addresses a shop scheduling problem for the side frame press shop in a truck manufacturing company. In the problem, a set of n jobs to be scheduled on two machines. All the jobs require processing by the first machine more than once in their operation sequences with reentrant work flows. An unusual aspect of the problem is that the setup times required for a job in the first machine depend not on the immediately preceding job but on the job which is two steps prior to it. Redefining the job elements, the problem is formulated into a general two machine flow shop problem which has a set of job-element precedence constraints. The problem is solved with a modified dynamic programming with the objective of the minimum makespan. An optimal schedule is found utilizing the sequence dominance condition and a decision-delay scheme. A numerical example is presented for the illustration purpose.     

周期性和事件驱动的JobShop滚动调度策略

为了适应加工的连续性及环境的变化，借用了预测控制中的滚动优化思想提出了周期性和事件驱动的滚动调度策略。调度算法将遗传算法和分派规则相结合，以此来处理与操作序列有关的工件安装时 间和工件到期时间约束的复杂调度问题。     

A genetic algorithm-based scheduler for multiproduct parallel machine sheet metal job shop

This paper presents a genetic algorithm-based job-shop scheduler for a flexible multi-product, parallel machine sheet metal job shop. Most of the existing research has focused only on permutation job shops in which the manufacturing sequence and routings are strictly in a predefined order. This effectively meant that only the jobs shops with little or no flexibility could be modeled using these models. The real life job shops may have flexibility of routing and sequencing. Our paper proposes one such model where variable sequences and multiple routings are possible. Another limitation of the existing literature was found to be negligence of the setup times. In many job shops like sheet metal shops, setup time may be a very sizable portion of the total make-span of the jobs, hence setup times will be considered in this work. One more flexibility type arises as a direct consequence of the routing flexibility. When there are multiple machines (parallel machines) to perform the same operation, the job could be routed to one or more of these machines to reduce the make-span. This is possible in situations where each job consists of a pre-defined quantity of a specified product. In other words, same job is quantity-wise split into two or more parts whenever it reduces the makespan. This effectively assumes that the setup cost is negligible. This model has been implemented on a real-life industry problem using VB.Net programming language. The results from the scheduler are found to be better than those obtained by simple sequencing rules.     

An interactive micro-computer software for general three machines flow shop sequencing problems

The order in which jobs pass through machines or work centres is a sequencing problem. The sequencing problems occur in flow shop as well as job shop production systems. In flow shop production systems, each job follows the same processing route whereas in the job shop production system, jobs flow across machines or work stations on many different routes. For optimizing the sequencing of such jobs, production planners may adopt different criteria such as makespan time, average completion time, due date performance, machine utilization and so forth. In the absence of given criteria, it is usual to accept the makespan time as the criteria and to attempt to minimize this. In a 2-machines flow shop, the jobs can be sequenced optimally for minimum total makespan time by using Johnson's algorithm [1]. Johnson's algorithm can also be used to find the optimal sequence for special three-machines flow shop problems satisfying certain conditions [1]. But for general three-machines sequencing problems, optimal sequence based on makespan time can be obtained by using a branch and bound solution procedure [1].

In this paper, the branch-and-bound procedure have been used to develop an interactive program in BASIC for finding the optimal job sequence for general three-machines flow shop problems. This program which is written for an IBM-PC or IBM-PC compatibles, also provides the time chart and the time chart drawing. Furthermore, it gives the results of the branching steps (i.e the partial sequences) in a tabular form.     

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.     

IS: An intelligent scheduler for batch manufacturing systems

This paper describes the design and development of IS (for Intelligent Scheduler), a true multiple criteria knowledge-based scheduler which can be used for operational level scheduling of batch manufacturing systems, sometimes called job shops. IS incorporates a heuristic algorithm coupled with two knowledge bases, one for job scheduling and the other for selecting a suitable schedule based on the user provided criterion or criteria. With fourteen dispatching rules, it can generate both static and dynamic schedules. IS is a far more realistic and sophisticated model, accounting for many important factors, such as multiple machines, multiple fixtures, multiple tools, alternate processing routes, machine setup time, machine processing time, due date, job arrival time, initial shop loading, hot jobs, and considering either one criterion or multiple criteria simultaneously. In addition, IS coded in C and has all the features of a modern professional quality interactive program. It has moving bar and pull down menus and an on-line help function, a friendly human-computer interface, and an intuitive and easy to understand representation of the schedules.     

Petri net modeling and scheduling for cyclic job shops with blocking

Cyclic scheduling is an effective scheduling method in the repetitive discrete manufacturing environment. We investigate the scheduling problem for general cyclic job shops with blocking where each machine has an input buffer of finite capacity. We develop Petri net models for the shops. We propose a sequential buffer control policy that restricts the jobs to enter the input buffer of the next machine in a specified sequence. We show that the scheduling model of a cyclic shop with finite buffers under such a buffer control policy can be transformed into a scheduling model of a cyclic shop with no buffer that can be modeled as a timed marked graph. In addition, we characterize the structural properties for deadlock detection. Finally, we present a mixed integer programming model to find an optimal deadlock-free schedule that minimizes the cycle time.     

Real-time scheduling for reentrant hybrid flow shops: A decision tree based mechanism and its application to a TFT-LCD line

A reentrant hybrid flow shop, typically found in the electronics industry, is an extended system of the ordinary flow shop in such a way that there exist one or more parallel machines at each serial stage and each job has the reentrant product flow, i.e., a job may visit a stage several times. Among the operational issues in reentrant hybrid flow shops, we focus on the scheduling problem that determines the allocation of jobs to the machines at each stage as well as the sequence of the jobs assigned to each machine. Unlike the theoretical approach on reentrant hybrid flow shop scheduling, we suggest a real-time scheduling mechanism with a decision tree when selecting appropriate dispatching rules. The decision tree, one of the commonly used data mining techniques, is adopted to eliminate the computational burden required to carry out simulation runs to select dispatching rules. To illustrate the mechanism suggested in this study, a case study was performed on a thin film transistor-liquid crystal display (TFT-LCD) manufacturing line and the results are reported for various system performance measures.     

Scheduling for on-time completion in job shops using feasibility function

This article focuses on job shop type manufacturing systems where a high variety of products of different volumes are requested to be produce on a tight due date. The feasibility function (FF) is addressed in this article to schedule jobs in multi-machine random job shop, where the purpose is to minimize unit penalty by achieving a balance between the number of tardy and early jobs, and reducing the difference between the maximum and the minimum lateness of jobs. A job shop simulation model based on multi-agent architecture developed by the authors provides an environment for comparing the FF to commonly used dispatching rules. The results show the benefit of using the FF. Discussions reveal that this concept is more reliable in case of due dates with different tightness level.     

Deadlock prevention and performance oriented supervision in flexible manufacturing cells: A hierarchical approach

In this paper, a hierarchical control system is proposed for automated flexible manufacturing cells (FMCs) that operate in a job shop flow setting. The control system is made up of a higher level scheduler that optimizes the production flow within the cell, and a lower level supervisor that implements the decisions of the scheduler on the shop floor. To obtain the supervisor, a production schedule is transformed into an augmented Marked Graph (MG) model that can interact with the cell devices. Because of the flow complexities inherent in job shop systems, they are usually prone to deadlocks. Accordingly, this paper also proposes a necessary condition for deadlock occurrence in the scheduling phase. The proposed approach is validated by implementation in an experimental manufacturing cell.     

On the Use of Genetic Algorithm for Solving Re-entrant Flowshop Scheduling with Sum-of-processing-times-based Learning Effect to Minimize Total Tardiness

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     

Holonic job shop scheduling using a multiagent system

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.     

A decentralized model for flow shop production with flexible transportation system

The recent advances in technology sectors often clash with traditional organizational paradigms which can limit or make difficult an efficient implementation in the real world. In this paper we show how it is possible to exploit the advantages of innovative technologies in manufacturing when these are supported by new and efficient methods for production management. More in details, we face a flow shop scheduling problem in a shoe manufacturing system in which overtaking of jobs is allowed thanks to an innovative transportation system. Overtaking means that a job can be put in waiting state and another job can surpass it, allowing the change of the scheduling sequence. Preemption is not allowed. The objective function of the problem is the minimization of the maximum lateness. We propose a decentralized model, based on multi-agent system theory, to represent the production cells of the plant and to include the potentiality offered by overtaking of jobs at decisional level. The adoption of a decentralized approach increases the system flexibility since each machine is able to solve its local scheduling problem. Adding or removing machines to the plant will not imply a change in the scheduling algorithms. The outcomes of this work are reached firstly through a formulation of the problem with three flow shop scheduling models, secondly through a comparison of the models with respect to different performance indicators. The results highlight as the decentralized approach is able to reach comparable performances with the centralized one for a relevant number of instances. Moreover sensitivity analysis shows as in the decentralized model the computational time required to solve bigger instances increases less quickly than in the case of centralized ones. Finally, simulations of the decentralized approach clarify as the correlation of the local solution procedure is effected by the number of machines of the flow shop and the coordination mechanism is effected by the number of the jobs to be scheduled.     

Joint optimization of job scheduling and maintenance planning for a two-machine flow shop considering job-dependent operating condition

Two-machine flow shops are widely adopted in manufacturing systems. To minimize the makespan of a sequence of jobs, joint optimization of job scheduling and preventive maintenance (PM) planning has been extensively studied for such systems. In practice, the operating condition (OC) of the two machines usually varies from one job to another because of different processing covariates, which directly affects the machines’ failure rates, PM plans, and expected job completion times. This fact is common in many real systems, but it is often overlooked in the related literature. In this study, we propose a joint decision-making strategy for a two-machine flow shop with resumable jobs. The objective is to minimize the expected makespan by taking into account job-dependent OC. We consider two situations. In the first situation, where the failure rate of a machine under a fixed OC is constant, a hybrid processing time model is proposed to obtain the optimal job sequence based on the Johnson's law. For the second situation, where the failure rate of a machine is time-varying, the job sequence and PM plan are jointly optimized. An enumeration method is adopted to find the optimal job sequence and PM plan for a small-scale problem, and a genetic algorithm-based method is proposed to solve a large-scale problem. Numerical examples are provided to demonstrate the necessity of considering the effect of job-dependent OC and the effectiveness of the proposed method in handing such joint decision-making problems in manufacturing systems.     

A computer simulation model for job shop scheduling problems minimizing makespan

One of the basic and significant problems, that a shop or a factory manager is encountered, is a suitable scheduling and sequencing of jobs on machines. One type of scheduling problem is job shop scheduling. There are different machines in a shop of which a job may require some or all these machines in some specific sequence. For solving this problem, the objective may be to minimize the makespan. After optimizing the makespan, the jobs sequencing must be carried out for each machine. The above problem can be solved by a number of different methods such as branch and bound, cutting plane, heuristic methods, etc. In recent years, researches have used genetic algorithms, simulated annealing, and machine learning methods for solving such problems. In this paper, a simulation model is presented to work out job shop scheduling problems with the objective of minimizing makespan. The model has been coded by Visual SLAM which is a special simulation language. The structure of this language is based on the network modeling. After modeling the scheduling problem, the model is verified and validated. Then the computational results are presented and compared with other results reported in the literature. Finally, the model output is analyzed.     

分布式车间调度优化算法研究综述

在分布式制造环境下, 分布式车间调度着重研究工件在工厂间的合理分配以及各工厂内的合理加工顺序, 以实现调度指标的最优化. 分布式车间调度的研究具有重要的学术意义和应用价值, 已成为生产调度领域的热点. 对 此, 围绕分布式并行机调度、分布式流水线调度、分布式作业车间调度、分布式装配调度和分布式柔性车间调度等问题, 重点综述分布式调度优化算法方面的代表性成果, 介绍分布式调度的若干应用, 最后指出有待于进一步研究的若干方向和内容.

     

Computerised scheduling technique for productivity improvement

The objective of the presented paper is to develop a model for job - shop scheduling that could be applied to manufacturing workshops as a tool for productivity improvement. The model is based on n jobs, m machines and considers the machining times and the machine ordering of each of the jobs on each machine. The model tries to minimise the total make-span of the product as a measure of performance. The model uses the Longest Preceding Path Time (LPPT) scheduling method.

The model was applied to a production workshop that manufactures pontoon sections which are used for constructing the folding pontoon bridges and ferries, besides, some other products. The pontoon section consists of 30 main jobs and uses 7 machines.     

Scheduling in a manufacturing shop with sequence-dependent setups

In this paper, the problem of scheduling multiple jobs in a flexible manufacturing cell with multiple machine stations is addressed. Due to the large capital investments that usually characterize flexible manufacturing systems (FMS), an area of control of great interest to system users is that of maximizing the system performance through the minimization of machine idle and setup times. The magnitude of total time spent on machine setups and idle times is influenced by the availability of jobs, job mix, similarities of jobs and job scheduling procedure used. Similar jobs on the same machine require less setup times. Similarly, the use of an adequate scheduling method also reduces total idle and setup times. Such reduction improves the flow times of jobs. In this paper, a heuristic algoritm for scheduling jobs with sequence dependent setup times in a FMS is presented. The measure of performance for evaluating schedule adequacy is the production makespan.     

基于Petri网的JSP动态优化调度

提出一种在柔性制造系统动态优化调度中处理紧急定单的方法。以带有控制器的 Petri 网为建模工具对柔性生产调度中的离散事件建模,对系统的设备维护、各种优先级等特性进行描述,利用遗传算法和模拟退火算法获得调度结果,用于解决作业车间的加工受到机床、操作工人等双资源制约条件下的动态优化调度。当有紧急定单需要加工时,该方法把剩余任务和紧急任务作为两个独立的任务分别处理,然后进行集成,在紧急任务为最优调度的基础上选取剩余任务的最优调度,找到兼顾整体和局部的最优解。仿真结果说明了算法的有效性和鲁棒性。