Designing safe job rotation schedules using optimization and heuristic search

Job rotation is one method that is sometimes used to reduce exposure to strenuous materials handling; however, developing effective rotation schedules can be complex in even moderate sized facilities. The purpose of this research is to develop methods of incorporating safety criteria into scheduling algorithms to produce job rotation schedules that reduce the potential for injury. Integer programming and a genetic algorithm were used to construct job rotation schedules. Schedules were comprised of lifting tasks whose potential for causing injury was assessed with the Job Severity Index. Each method was used to design four job rotation schedules that met specified safety criteria in a working environment where the object weight, horizontal distance and repetition rate varied over time. Each rotation was assigned to a specific gender/lifting capacity group. Five versions of the integer programming search method were applied to this problem. Each version generated one job rotation schedule. The genetic algorithm model was able to create a population of 437 feasible solutions to the rotation problem. Utilizing cluster analysis, a rule set was derived from the genetic algorithm generated solutions. These rules provided guidelines for designing safe job rotation schedules without the use of a computer. The advantages and limitations of these approaches in developing administrative controls for the prevention of back injury are discussed.     

Total flow time minimization in no-wait job shop using a hybrid discrete group search optimizer

The no-wait job shop scheduling problem is a well-known NP-hard problem and it is typically decomposed into timetabling subproblem and sequencing subproblem. By adopting favorable features of the group search technique, a hybrid discrete group search optimizer is proposed for finding high quality schedules in the no-wait job shops with the total flow time criterion. In order to find more promising sequences, the producer operator is designed as a destruction and construction (DC) procedure and an insertion-based local search, the scrounger operator is implemented by differential evolution scheme, and the ranger operator is designed by hybridizing best insert moves. An efficient initialization scheme based on Nawaz–Enscore–Ham (NEH) heuristic is designed to construct the initial population with both quality and diversity. A speed-up method is developed to accelerate the evaluation of the insertion neighborhood. Computational results based on well-known benchmark instances show that the proposed algorithm clearly outperforms a hybrid differential evolution algorithm and an iterated greedy algorithm. In addition, the proposed algorithm is comparable to a local search method based on optimal job insertion, especially for large-size instances.     

Enhanced exchange heuristic based resource constrained scheduler using ARTMAP

The Exchange Heuristic (EH) has demonstrated superior results compared with other RCS methods in solving Resource Constrained Scheduling (RCS) problems. Selecting the most promising target constitutes the success of EH. The current version of EH highly depends on experts' intuition in selecting a target. Expert systems and Fuzzy rulebase as well as Neural Network (NN) have been considered as alternatives for human experts. Expert systems are brittle in its nature, and Fuzzy rulebase needs membership functions defined for each linguistic variable. However, these membership function can not be justified and can be very subjective. Therefore, Neural Network is employed because of its capability of learning as well as dealing with fuzzy data. Known examples are used to train the NN. Back propagation algorithm is used first, then Adaptive Resonance Theory (ART) network is employed to reduce training time since new rules come up often. Even at the end of the training the NN, we may end up with local optima or the NN which is too general to specific problems. Utilizing Genetic Algorithm (GA) will help to further refine or adapt the weights of the NN which optimizes target selection strategy for a specific problem.     

A comparison of dispatching rules and genetic algorithms for job shop schedules of standard hydraulic cylinders

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.     

Deadlock-free scheduling for flexible manufacturing systems using Petri nets and heuristic search

Deadlock-free control and scheduling are two different problems for flexible manufacturing systems (FMSs). They are significant for improving the behaviors of the systems. Based on the Petri net models of FMSs, this paper embeds deadlock control policies into heuristic search algorithm, and proposes a deadlock-free scheduling algorithm to minimize makespan for FMSs. Scheduling is performed as heuristic search in the reachability graph of the Petri net. The searching process is guided by a heuristic function based on firing count vectors of state equation for the Petri net. By using the one-step look-ahead method in the optimal deadlock control policy, the safety of a state is checked. Experimental results are provided to show effectiveness of the proposed heuristic search approach in deadlock-free scheduling for FMSs.     

A genetic algorithm with tabu search procedure for flexible job shop scheduling with transportation constraints and bounded processing times

In this paper, we propose a model for Flexible Job Shop Scheduling Problem (FJSSP) with transportation constraints and bounded processing times. This is a NP hard problem. Objectives are to minimize the makespan and the storage of solutions. A genetic algorithm with tabu search procedure is proposed to solve both assignment of resources and sequencing problems on each resource. In order to evaluate the proposed algorithm's efficiency, five types of instances are tested. Three of them consider sequencing problems with or without assignment of processing or/and transport resources. The fourth and fifth ones introduce bounded processing times which mainly characterize Surface Treatment Facilities (STFs). Computational results show that our model and method are efficient for solving both assignment and scheduling problems in various kinds of systems.     

Modeling machine loading problem of FMSs and its solution methodology using a hybrid tabu search and simulated annealing-based heuristic approach

In this article, a machine loading problem of a flexible manufacturing system (FMS) is discussed having the bicriterion objectives of minimizing system unbalance and maximizing throughput in the presence of technological constraints such as available machining time and tool slots. A generic 0–1 integer programming formulation with the objective functions and constraints described above has been proposed. A hybrid algorithm based on tabu search and simulated annealing (SA) is employed to solve the problem. The main advantage of this approach is that a short-term memory provided by the tabu list can be used to avoid revisiting the solution while preserving the stochastic nature of the SA method. The proposed methodology has been tested on ten standard problems and the results obtained are compared with those from some of the existing heuristics.     

Mathematical model and genetic optimization for the job shop scheduling problem in a mixed- and multi-product assembly environment: A case study based on the apparel industry

An effective job shop scheduling (JSS) in the manufacturing industry is helpful to meet the production demand and reduce the production cost, and to improve the ability to compete in the ever increasing volatile market demanding multiple products. In this paper, a universal mathematical model of the JSS problem for apparel assembly process is constructed. The objective of this model is to minimize the total penalties of earliness and tardiness by deciding when to start each order’s production and how to assign the operations to machines (operators). A genetic optimization process is then presented to solve this model, in which a new chromosome representation, a heuristic initialization process and modified crossover and mutation operators are proposed. Three experiments using industrial data are illustrated to evaluate the performance of the proposed method. The experimental results demonstrate the effectiveness of the proposed algorithm to solve the JSS problem in a mixed- and multi-product assembly environment.