Cyclic job shop scheduling problems with blocking

A tabu search algorithm for a cyclic job shop problem with blocking is presented. Operations are blocking if they must stay on a machine after finishing when the next machine is occupied by another job. During this stay the machine is blocked for other jobs. For this problem traditional tabu search moves often lead to infeasible solutions. Recovering procedures are developed which construct nearby feasible solutions. Computational results are presented for the approach.     

Simultaneously scheduling multiple turns for steel color-coating production

This paper investigates a large-scale scheduling problem in the iron and steel industry, called color-coating production scheduling (CCPS). The problem is to generate multiple production turns for the galvanized coils that dynamically arrive from upstream lines within a given scheduling horizon, and at the same time determine the sequence of these turns so that the productivity and product quality are maximized while the production cost and the number of generated turns are minimized. We formulate this problem as a mixed integer nonlinear program and propose a tabu search heuristic to obtain satisfactory solutions. Results on real production instances show that the presented model and heuristic are more effective and efficient with comparison to manual scheduling. A practical scheduling system for CCPS combining the model and heuristic has been developed and successfully implemented in a major iron and steel enterprise in China.     

A problem expanding parametric programming method for solving the job shop scheduling problem

A new zero-one integer programming model for the job shop scheduling problem with minimum makespan criterion is presented. The algorithm consists of two parts: (a) a branch and bound parametric linear programming code for solving the job shop problem with fixed completion time; (b) a problem expanding algorithm for finding the optimal completion time. Computational experience for problems having up to thirty-six operations is presented. The largest problem solved was limited by memory space, not computation time. Efforts are under way to improve the efficiency of the algorithm and to reduce its memory requirements.This report was prepared as part of the activities of the Management Sciences Research Group, Carnegie-Mellon University, under Contract No. N00014-82-K-0329 NR 047-048 with the U.S. Office of Naval Research. Reproduction in whole or in part is permitted for any purpose of the U.S. Government.     

A hybrid single and dual population search procedure for the job shop scheduling problem

This paper presents a genetic algorithm and a scatter search procedure to solve the well-known job shop scheduling problem. In contrast to the single population search performed by the genetic algorithm, the scatter search algorithm splits the population of solutions in a diverse and high-quality set to exchange information between individuals in a controlled way. The extension from a single to a dual population, by taking problem specific characteristics into account, can be seen as a stimulator to add diversity in the search process. This has a positive influence on the important balance between intensification and diversification. Computational experiments verify the benefit of this diversity on the effectiveness of the meta-heuristic search process. Various algorithmic parameters from literature are embedded in both procedures and a detailed comparison is made. A set of standard instances is used to compare the different approaches and the best obtained results are benchmarked against heuristic solutions found in literature.     

A comparative study of a new heuristic based on adaptive memory programming and simulated annealing: The case of job shop scheduling

In this study, a general framework is proposed that combines the distinctive features of three well-known approaches: the adaptive memory programming, the simulated annealing, and the tabu search methods. Four variants of a heuristic based on this framework are developed and presented. The performance of the proposed methods is evaluated and compared with a conventional simulated annealing approach using benchmark problems for job shop scheduling. The unique feature of the proposed framework is the use of two short-term memories. The first memory temporarily prevents further changes in the configuration of a provisional solution by maintaining the presence of good elements of such solutions. The purpose of the second memory is to keep track of good solutions found during an iteration, so that the best of these can be used as the starting point in a subsequent iteration. Our computational results for the job shop scheduling problem clearly indicate that the proposed methods significantly outperform the conventional simulated annealing.     

A new neighborhood and tabu search for the Blocking Job Shop

The Blocking Job Shop is a version of the job shop scheduling problem with no intermediate buffers, where a job has to wait on a machine until being processed on the next machine. We study a generalization of this problem which takes into account transfer operations between machines and sequence-dependent setup times. After formulating the problem in a generalized disjunctive graph, we develop a neighborhood for local search. In contrast to the classical job shop, there is no easy mechanism for generating feasible neighbor solutions. We establish two structural properties of the underlying disjunctive graph, the concept of closures and a key result on short cycles, which enable us to construct feasible neighbors by exchanging critical arcs together with some other arcs. Based on this neighborhood, we devise a tabu search algorithm and report on extensive computational experience, showing that our solutions improve most of the benchmark results found in the literature.     

A tabu search algorithm for the single machine total weighted tardiness problem

In this study, a tabu search (TS) approach to the single machine total weighted tardiness problem (SMTWT) is presented. The problem consists of a set of independent jobs with distinct processing times, weights and due dates to be scheduled on a single machine to minimize total weighted tardiness. The theoretical foundation of single machine scheduling with due date related objectives reveal that the problem is NP-hard, rendering it a challenging area for meta-heuristic approaches. This paper presents a totally deterministic TS algorithm with a hybrid neighborhood and dynamic tenure structure, and investigates the strength of several candidate list strategies based on problem specific characteristics in increasing the efficiency of the search. The proposed TS approach yields very high quality results for a set of benchmark problems obtained from the literature.     

Parallel variable neighbourhood search algorithms for job shop scheduling problems

^** Email: msevkli{at}fatih.edu.tr^*** Corresponding author. Email: mehmetaydin{at}acm.org, mehmet.aydin{at}beds.ac.uk Variable neighbourhood search (VNS) is one of the most recentmetaheuristics used for solving combinatorial optimization problemsin which a systematic change of neighbourhood with a local searchis carried out. However, as happens with other metaheuristics,it takes a long time to reach some useful solutions while solvingsome sort of hard combinatorial problems such as job shop scheduling(JSS). Parallelization is one of the most considerable policiesto overcome this matter. In this paper, firstly, a number ofVNS algorithms are examined for JSS problems and then four differentparallelization policies are taken into account to determineefficient parallelization for VNS algorithms. The experimentationreveals the performance of various VNS algorithms and the efficiencyof policies to follow in parallelization. In the end, the unilateral-ringtopology, a noncentral parallelization method, is found as themost efficient policy.     

A disjunctive graph model and framework for constructing new train schedules

Train scheduling is a complex and time consuming task of vital importance in many countries. To create completely new train schedules that are more accurate and efficient than permitted by current techniques, a novel “hybrid” job shop approach is proposed and implemented in this paper. Unique characteristics of train scheduling are firstly incorporated into a disjunctive graph representation of the solution. Dedicated “stand-alone” constructive algorithms that utilise this representation are then developed. The modelling approach and the constructive algorithms are essential as they provide the basis for which meta-heuristics and other iterative refinement algorithms can be applied. A numerical investigation and case study is provided and demonstrates the viability of the modelling approach. Furthermore it is demonstrated that good quality solutions are provided with reasonable computational effort.     

A tabu search and a genetic algorithm for solving a bicriteria general job shop scheduling problem

This paper deals with a general job shop scheduling problem with multiple constraints, coming from printing and boarding industry. The objective is the minimization of two criteria, the makespan and the maximum lateness, and we are interested in finding an approximation of the Pareto frontier. We propose a fast and elitist genetic algorithm based on NSGA-II for solving the problem. The initial population of this algorithm is either randomly generated or partially generated by using a tabu search algorithm, that minimizes a linear combination of the two criteria. Both the genetic and the tabu search algorithms are tested on benchmark instances from flexible job shop literature and computational results show the interest of both methods to obtain an efficient and effective resolution method.     

A survey of scheduling problems with setup times or costs

The first comprehensive survey paper on scheduling problems with separate setup times or costs was conducted by [Allahverdi, A., Gupta, J.N.D., Aldowaisan, T., 1999. A review of scheduling research involving setup considerations. OMEGA The International Journal of Management Sciences 27, 219–239], who reviewed the literature since the mid-1960s. Since the appearance of that survey paper, there has been an increasing interest in scheduling problems with setup times (costs) with an average of more than 40 papers per year being added to the literature. The objective of this paper is to provide an extensive review of the scheduling literature on models with setup times (costs) from then to date covering more than 300 papers. Given that so many papers have appeared in a short time, there are cases where different researchers addressed the same problem independently, and sometimes by using even the same technique, e.g., genetic algorithm. Throughout the paper we identify such areas where independently developed techniques need to be compared. The paper classifies scheduling problems into those with batching and non-batching considerations, and with sequence-independent and sequence-dependent setup times. It further categorizes the literature according to shop environments, including single-machine, parallel machines, flow shop, no-wait flow shop, flexible flow shop, job shop, open shop, and others.     

A mixed integer programming model for advanced planning and scheduling (APS)

This paper presents a mixed integer programming (MIP) model which succeeds in a system integration of the production planning and shop floor scheduling problems. The proposed advanced planning and scheduling (APS) model explicitly considers capacity constraints, operation sequences, lead times and due dates in a multi-order environment. The objective of the model is to seek the minimum cost of both production idle time and tardiness or earliness penalty of an order. The output of the model is operation schedules with order starting time and finish time. Numerical result shows that the suggested APS model can favorably produce optimal schedules.     

A novel parallel quantum genetic algorithm for stochastic job shop scheduling

In this paper, a Novel Parallel Quantum Genetic Algorithm (NPQGA) is proposed for the stochastic Job Shop Scheduling Problem with the objective of minimizing the expected value of makespan, where the processing times are subjected to independent normal distributions. Based on the parallel evolutionary idea and some concepts of quantum theory, we simulate a model of parallel quantum computation. In this frame, there are some demes (sub-populations) and some universes (groups of populations), which are structured in super star-shaped topologies. A new migration scheme based on penetration theory is developed to control migration rate and direction adaptively between demes, and a novel quantum crossover strategy is devised among universes. The quantum evolution is executed in every deme by applying some improvement operators (the coding mechanism aiming at job shop, the new quantum rotation angle and the catastrophe operator). Experiment results show NPQGA's effectiveness and applicability.     

A tabu search algorithm for solving economic lot scheduling problem

The economic lot scheduling problem has driven considerable amount of research. The problem is NP-hard and recent research is focused on finding heuristic solutions rather than searching for optimal solutions. This paper introduces a heuristic method using a tabu search algorithm to solve the economic lot scheduling problem. Diversification and intensification schemes are employed to improve the efficiency of the proposed Tabu search algorithm. Experimental design is conducted to determine the best operating parameters for the Tabu search. Results show that the tabu search algorithm proposed in this paper outperforms two well known benchmark algorithms.     

Exact and heuristic methodologies for scheduling in hospitals: problems, formulations and algorithms

This text summarizes the PhD thesis defended by the author in January 2006 under the supervision of Professor Erik Demeulemeester at the Katholieke Universiteit Leuven. The thesis is written in English and is available from the author’s website (http://www.econ.kuleuven.be/jeroen.belien). In this research we propose a number of exact and heuristic algorithms for various scheduling problems encountered in hospitals. The emphasis lies on the design of new methodologies as well as on the applicability of the algorithms in real-life environments. The main contributions include a new decomposition approach for a particular class of staff scheduling problems, an extensive study of master surgery scheduling algorithms that aim at leveling the resultant bed occupancy and an innovative method for integrating nurse and surgery scheduling.      

A polynomial algorithm for 2-cyclic robotic scheduling: A non-Euclidean case

In this paper we consider the problem of no-wait cyclic scheduling of identical parts in an m-machine production line in which a robot is responsible for moving each part from a machine to another. The aim is to find the minimum cycle time for the so-called 2-cyclic schedules, in which exactly two parts enter and two parts leave the production line during each cycle. The earlier known polynomial-time algorithms for this problem are applicable only under the additional assumption that the robot travel times satisfy the triangle inequalities. We lift this assumption on robot travel times and present a polynomial-time algorithm with the same time complexity as in the metric case, O(m⁵logm).     

A note on “A mixed integer programming model for advanced planning and scheduling (APS)”

In a recent paper, Chen and Ji [Chen, K., Ji, P., 2007. A mixed integer programming model for advanced planning and scheduling (APS). European Journal of Operational Research 181, 515–522] develop a mixed integer programming model for advanced planning and scheduling problem that considers capacity constraints and precedence relations between the operations. The orders require processing of several operations on eligible machines. The model presented in the above paper works for the case where each operation can be processed on only one machine. However, machine eligibility means that only a subset of machines are capable of processing a job and this subset may include more than one machine. We provide a general model for advanced planning and scheduling problems with machine eligibility. Our model can be used for problems where there are alternative machines that an operation can be assigned to.     

Multi-objective genetic algorithm for single machine scheduling problem under fuzziness

This paper presents a new multi-objective approach to a single machine scheduling problem in the presence of uncertainty. The uncertain parameters under consideration are due dates of jobs. They are modelled by fuzzy sets where membership degrees represent decision maker’s satisfaction grade with respect to the jobs’ completion times. The two objectives defined are to minimise the maximum and the average tardiness of the jobs. Due to fuzziness in the due dates, the two objectives become fuzzy too. In order to find a job schedule that maximises the aggregated satisfaction grade of the objectives, a hybrid algorithm that combines a multi-objective genetic algorithm with local search is developed. The algorithm is applied to solve a real-life problem of a manufacturing pottery company.     

A polynomial algorithm for no-wait cyclic hoist scheduling in an extended electroplating line

This paper addresses cyclic hoist scheduling in a no-wait electroplating line where a part visits some processing tanks more than once and multiple duplicate tanks are used at some production stages. We prove that such an extended problem can be solved in polynomial time.