Hybrid metaheuristics for scheduling of machines and transport robots in job shop environment

In real manufacturing environments, the control of some elements in systems based on robotic cells, such as transport robots has some difficulties when planning operations dynamically. The Job Shop scheduling Problem with Transportation times and Many Robots (JSPT-MR) is a generalization of the classical Job Shop scheduling Problem (JSP) where a set of jobs additionally have to be transported between machines by several transport robots. Hence, the JSPT-MR is more computationally difficult than the JSP presenting two NP-hard problems simultaneously: the job shop scheduling problem and the robot routing problem. This paper proposes a hybrid metaheuristic approach based on clustered holonic multiagent model for the JSPT-MR. Firstly, a scheduler agent applies a Neighborhood-based Genetic Algorithm (NGA) for a global exploration of the search space. Secondly, a set of cluster agents uses a tabu search technique to guide the research in promising regions. Computational results are presented using two sets of benchmark literature instances. New upper bounds are found, showing the effectiveness of the presented approach.     

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.     

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.     

A genetic algorithm for permutation flow shop scheduling under make to stock production system

The permutation flow shop scheduling is a well-known combinatorial optimization problem that arises in many manufacturing systems. Over the last few decades, permutation flow shop problems have widely been studied and solved as a static problem. However, in many practical systems, permutation flow shop problems are not really static, but rather dynamic, where the challenge is to schedule n different products that must be produced on a permutation shop floor in a cyclical pattern. In this paper, we have considered a make-to-stock production system, where three related issues must be considered: the length of a production cycle, the batch size of each product, and the order of the products in each cycle. To deal with these tasks, we have proposed a genetic algorithm based lot scheduling approach with an objective of minimizing the sum of the setup and holding costs. The proposed algorithm has been tested using scenarios from a real-world sanitaryware production system, and the experimental results illustrates that the proposed algorithm can obtain better results in comparison to traditional reactive approaches.     

Variable neighborhood search approaches for scheduling jobs on parallel machines with sequence-dependent setup times, precedence constraints, and ready times

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.     

Recurrent neural network approach for cyclic job shop scheduling problem

While cyclic scheduling is involved in numerous real-world applications, solving the derived problem is still of exponential complexity. This paper focuses specifically on modelling the manufacturing application as a cyclic job shop problem and we have developed an efficient neural network approach to minimise the cycle time of a schedule. Our approach introduces an interesting model for a manufacturing production, and it is also very efficient, adaptive and flexible enough to work with other techniques. Experimental results validated the approach and confirmed our hypotheses about the system model and the efficiency of neural networks for such a class of problems.     

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.     

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.     

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

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

Development of an expert system for scheduling work content in a job shop environment

Experts estimate that 65% of all manufacturing firms employ fifty or less employees, and many of these small manufacturing firms operate as job shop environments. This paper will focus on a methodology for the development of an expert systems approach to job shop scheduling. Specifically, the concept of prototyping and life cycle development will be discussed. Prototyping combines the steps of knowledge acquisition, knowledge representation, knowledge implementation, and verification and validation into a repetitive cycle, rather than having the steps in a sequential fashion. By using a prototyping cycle, a small expert system is developed first and then gradually enlarged as exception cases are identified, instead of attempting to complete each step entirely before continuing with the next.     

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

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

Real-time holonic scheduling of material handling operations in a dynamic manufacturing environment

In a real-world manufacturing environment, finding the right sequences and associated schedules with resource, precedence, and timing constraints is a difficult task. Moreover, a decision time period of hours or even minutes is simply too long. Good solutions are often needed in real time. One approach to overcome the limitations of classical scheduling is the use of distributed schemes such as agent or holonic-based control architectures. This paper presents a solution for scheduling material handling devices in the cellular manufacturing environment using the holonic control approach. In holonic systems, under real-time constraints, a feasible schedule for the material handling devices emerges from the combination of individual material handling holons’ schedules. Internal evaluation and allocation algorithms and specific cooperation mechanisms between the holons in the architecture are the basis for the resultant emergent schedules. These evaluation algorithms are developed using several scenarios that take into account uncertainties that usually exist in a dynamic manufacturing environment, such as new orders entering into the system. The study results obtained show that the holonic system is capable of accommodating new arriving jobs and delivers good solutions in real time.     

Distributed and centralised material handling scheduling: Comparison and results of a simulation study

Part of a larger research that employs decentralized holonic modelling techniques in manufacturing planning and control, this work proposes a holonic-based material handling system and contrasts the centralized and distributed scheduling approaches for the allocation of material handling operations to the available system resources. To justify the use of the decentralized holonic approach and assess its performance compared to conventional scheduling systems, a series of evaluation tests and a simulation study are carried out. As illustrated by the results obtained from the simulation study, the decentralized holonic approach is capable of delivering competitive feasible solutions in, practically, real-time.     

A genetic algorithm-based approach to flexible flow-line schedulingwith variable lot sizes

Genetic algorithms (GAs) have been used widely for such combinatorial optimization problems as the traveling salesman problem (TSP), the quadratic assignment problem (QAP), and job shop scheduling. In all of these problems there is usually a well defined representation which GA's use to solve the problem. We present a novel approach for solving two related problems-lot sizing and sequencing-concurrently using GAs. The essence of our approach lies in the concept of using a unified representation for the information about both the lot sizes and the sequence and enabling GAs to evolve the chromosome by replacing primitive genes with good building blocks. In addition, a simulated annealing procedure is incorporated to further improve the performance. We evaluate the performance of applying the above approach to flexible flow line scheduling with variable lot sizes for an actual manufacturing facility, comparing it to such alternative approaches as pair wise exchange improvement, tabu search, and simulated annealing procedures. The results show the efficacy of this approach for flexible flow line scheduling.     

Discrepancy search for the flexible job shop scheduling problem

The flexible job shop scheduling problem (FJSP) is a generalization of the classical job shop problem in which each operation must be processed on a given machine chosen among a finite subset of candidate machines. The aim is to find an allocation for each operation and to define the sequence of operations on each machine, so that the resulting schedule has a minimal completion time. We propose a variant of the climbing discrepancy search approach for solving this problem. We also present various neighborhood structures related to assignment and sequencing problems. We report the results of extensive computational experiments carried out on well-known benchmarks for flexible job shop scheduling. The results demonstrate that the proposed approach outperforms the best-known algorithms for the FJSP on some types of benchmarks and remains comparable with them on other ones.     

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.     

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

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

A holonic approach to dynamic manufacturing scheduling

Manufacturing scheduling is a complex combinatorial problem, particularly in distributed and dynamic environments. This paper presents a holonic approach to manufacturing scheduling, where the scheduling functions are distributed by several entities, combining their calculation power and local optimization capability. In this scheduling and control approach, the objective is to achieve fast and dynamic re-scheduling using a scheduling mechanism that evolves dynamically to combine centralized and distributed strategies, improving its responsiveness to emergence, instead of the complex and optimized scheduling algorithms found in traditional approaches.     

A neighborhood for complex job shop scheduling problems with regular objectives

Due to the limited applicability in practice of the classical job shop scheduling problem, many researchers have addressed more complex versions of this problem by including additional process features, such as time lags, setup times, and buffer limitations, and have pursued objectives that are more practically relevant than the makespan, such as total flow time and total weighted tardiness. However, most proposed solution approaches are tailored to the specific scheduling problem studied and are not applicable to more general settings. This article proposes a neighborhood that can be applied for a large class of job shop scheduling problems with regular objectives. Feasible neighbor solutions are generated by extracting a job from a given solution and reinserting it into a neighbor position. This neighbor generation in a sense extends the simple swapping of critical arcs, a mechanism that is widely used in the classical job shop but that is not applicable in more complex job shop problems. The neighborhood is embedded in a tabu search, and its performance is evaluated with an extensive experimental study using three standard job shop scheduling problems: the (classical) job shop, the job shop with sequence-dependent setup times, and the blocking job shop, combined with the following five regular objectives: makespan, total flow time, total squared flow time, total tardiness, and total weighted tardiness. The obtained results support the validity of the approach.     

Dynamic scheduling of a batch of parallel task jobs on heterogeneous clusters

This paper addresses the problem of minimizing the scheduling length (make-span) of a batch of jobs with different arrival times. A job is described by a direct acyclic graph (DAG) of parallel tasks. The paper proposes a dynamic scheduling method that adapts the schedule when new jobs are submitted and that may change the processors assigned to a job during its execution. The scheduling method is divided into a scheduling strategy and a scheduling algorithm. We also propose an adaptation of the Heterogeneous Earliest-Finish-Time (HEFT) algorithm, called here P-HEFT, to handle parallel tasks in heterogeneous clusters with good efficiency without compromising the makespan. The results of a comparison of this algorithm with another DAG scheduler using a simulation of several machine configurations and job types shows that P-HEFT gives a shorter makespan for a single DAG but scores worse for multiple DAGs. Finally, the results of the dynamic scheduling of a batch of jobs using the proposed scheduler method showed significant improvements for more heavily loaded machines when compared to the alternative resource reservation approach.