Algorithms for multiprocessor scheduling with two job lengths and allocation restrictions

A variant of the High Multiplicity Multiprocessor Scheduling Problem with C job lengths is considered, in which jobs can be processed only by machines not greater than a given index. When C=2, polynomial algorithms are proposed, for the feasibility version of the problem and for maximizing the number of scheduled jobs.     

Elucidating multiprocessors flow shop scheduling with dependent setup times using a twin particle swarm optimization

Particle swarm optimization (PSO) is a novel metaheuristic, which has been applied in a wide variety of production scheduling problems. Two basic characteristics of this algorithm are its efficiency and effectiveness in providing high-quality solutions. In order to improve the traditional PSO, this study proposes the incorporation of a local search heuristic into the basic PSO algorithm. The new, hybrid, metaheuristic is called “twin particle swarm optimization (TPSO)”. The proposed metaheuristic scheme is applied to a flow shop with multiprocessors scheduling problem, which can be considered a real world case regarding the production line. This study, as far as the multiprocessors flow shop production system is concerned, utilizes sequence dependent setup times as constraints. Finally, simulated data confirm the effectiveness and robustness of the proposed algorithm. The data test results indicate that TPSO has potential to replace PSO and become a significant heuristic algorithm for similar problems.     

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.     

Preemptive stochastic online scheduling on two uniform machines

This paper addresses a stochastic online scheduling problem in which a set of independent jobs are to be processed by two uniform machines whose speeds are 1 and s(s?1). Each job has a processing time, which is a random variable with an arbitrary distribution, and all the jobs are arriving overtime, which means that no information of the job is known in advance before its arrival. During the processing, jobs are allowed to be preempted and resumed later. The objective is to minimize the sum of expected weighted completion times. In this paper, the optimal policy, named SMPR, is designed for the single-machine preemptive stochastic scheduling problem where jobs have a common arriving time. Based on SMPR, the online approximative policy-UMPR, is devised for the preemptive stochastic online scheduling on two uniform machines. Then, UMPR is proved to have an approximation factor of 2. Furthermore, it is concluded that UMPR could not have a smaller approximation factor than 2, which means 2 is the approximation ratio of UMPR for the two-uniform-machine scheduling problem.     

An improved approximation algorithm for two-machine flow shop scheduling with an availability constraint

We study the problem of scheduling n jobs in a two-machine flow shop where the second machine is not available for processing during a given time interval. A resumable scenario is assumed, i.e., if a job cannot be finished before the down period it is continued after the machine becomes available again. The objective is to minimize the makespan. The best fast approximation algorithm for this problem guarantees a relative worst-case error bound of 4/3. We present an improved algorithm with a relative worst-case error bound of 5/4.     

A new particle swarm optimization for the open shop scheduling problem

This paper presents a new particle swarm optimization (PSO) for the open shop scheduling problem. Compared with the original PSO, we modified the particle position representation using priorities, and the particle movement using an insert operator. We also implemented a modified parameterized active schedule generation algorithm (mP-ASG) to decode a particle position into a schedule. In mP-ASG, we can reduce or increase the search area between non-delay schedules and active schedules by controlling the maximum delay time allowed. Furthermore, we hybridized our PSO with beam search. The computational results show that our PSO found many new best solutions of the unsolved problems.     

A polynomial-time approximation scheme for the two-machine flow shop scheduling problem with an availability constraint

We study the problem of scheduling n preemptable jobs in a two-machine flow shop where the first machine is not available for processing during a given time interval. The objective is to minimize the makespan. We propose a polynomial-time approximation scheme for this problem. The approach is extended to solve the problem in which the second machine is not continuously available.     

Two-stage hybrid flow shop with precedence constraints and parallel machines at second stage

This study deals with the two-stage hybrid flow shop (HFS) problem with precedence constraints. Two versions are examined, the classical HFS where idle time between the operations of the same job is allowed and the no-wait HFS where idle time is not permitted. For solving these problems an adaptive randomized list scheduling heuristic is proposed. Two global bounds are also introduced so as to conservatively estimate the distance to optimality of the proposed heuristic. The evaluation is done on a set of randomly generated instances. The heuristic solutions for the classical HFS in average are provably situated below 2% from the optimal ones, and on the other hand, in the case of the no-wait HFS the average deviation is below 5%.     

Finding multiple solutions in job shop scheduling by niching genetic algorithms

The interest in multimodal optimization methods is increasing in the last years. The objective is to find multiple solutions that allow the expert to choose the solution that better adapts to the actual conditions. Niching methods extend genetic algorithms to domains that require the identification of multiple solutions. There are different niching genetic algorithms: sharing, clearing, crowding and sequential, etc. The aim of this study is to study the applicability and the behavior of several niching genetic algorithms in solving job shop scheduling problems, by establishing a criterion in the use of different methods according to the needs of the expert. We will experiment with different instances of this problem, analyzing the behavior of the algorithms from the efficacy and diversity points of view.     

Preemptive scheduling on two parallel machines with a single server

This paper addresses a preemptive scheduling problem on two parallel machines with a single server. Each job has to be loaded (setup) by the server before being processed on the machines. The preemption is allowed in this paper. The goal is to minimize the makespan. We first show that it is no of use to preempt the job during its setup time. Namely, every optimal preemptive schedule can be converted to another optimal schedule where all the setup times are non-preemptively performed on one machine. We then present an algorithm with a tight bound of 4/3 for the general case. Furthermore, we show that the algorithm can produce optimal schedules for two special cases: equal processing times and equal setup times, which are NP-hard in the non-preemptive version.     

Approximation algorithms for shop scheduling problems with minsum objective: A correction

We present a correction to the paper, “Approximation algorithms for shop scheduling problems with minsum objective” (Journal of Scheduling 2002; 5:287–305) by Queyranne and Sviridenko. This correction provides a correct derivation of its 2eρ approximation result. Wenhua Li and Jinjiang Yuan: Project supported by NNSFC (Grant 10371112) and NSFHN (Grant 0411011200). Maurice Queyranne: Supported by research grants from NSERC, the Natural Sciences and Engineering Research Council of Canada.     

Decision support tool for multi-objective job shop scheduling problems with linguistically quantified decision functions

This paper presents a new tool for multi-objective job shop scheduling problems. The tool encompasses an interactive fuzzy multi-objective genetic algorithm (GA) which considers aspiration levels set by the decision maker (DM) for all the objectives. The GA's decision (fitness) function is defined as a measure of truth of a linguistically quantified statement, imprecisely specified by the DM using linguistic quantifiers such as most, few, etc., that refer to acceptable distances between the achieved objective values and the aspiration levels. The linguistic quantifiers are modelled using fuzzy sets. The developed tool is used to analyse and solve a real-world problem defined in collaboration with a pottery company. The tool provides a valuable support in performing various what-if analyses, for example, how changes of batch sizes, aspiration levels, linguistic quantifiers and the measure of acceptable distances affect the final schedule.     

A hybrid multi-objective immune algorithm for a flow shop scheduling problem with bi-objectives: Weighted mean completion time and weighted mean tardiness

This paper investigates a novel multi-objective model for a no-wait flow shop scheduling problem that minimizes both the weighted mean completion time and weighted mean tardiness . Obtaining an optimal solution for this type of complex, large-sized problem in reasonable computational time by using traditional approaches and optimization tools is extremely difficult. This paper presents a new hybrid multi-objective algorithm based on the features of a biological immune system (IS) and bacterial optimization (BO) to find Pareto optimal solutions for the given problem. To validate the performance of the proposed hybrid multi-objective immune algorithm (HMOIA) in terms of solution quality and diversity level, various test problems are examined. Further, the efficiency of the proposed algorithm, based on various metrics, is compared against five prominent multi-objective evolutionary algorithms: PS-NC GA, NSGA-II, SPEA-II, MOIA, and MISA. Our computational results suggest that our proposed HMOIA outperforms the five foregoing algorithms, especially for large-sized problems.     

Robust flow shop scheduling with random processing times for reduction of peak power consumption

Recently, power shortages have become a major problem all over Japan, due to the Great East Japan Earthquake, which resulted in the shutdown of a nuclear power plant. As a consequence, production scheduling has become a problem for factories, due to considerations of the availability of electric power. For factories, the contract with the electric power company sets the maximum power demand for a unit period, and in order to minimize this, it is necessary to consider the peak power when scheduling production. There are conventional studies on flowshop scheduling with consideration of peak power. However, these studies did not consider fluctuations in the processing time. Because the actual processing time is not constant, there is an increase in the probability of simultaneous operations with multiple machines. If the probability of simultaneous operations is high, the probability of increasing the peak power is high. Thus, we consider inserting idle time (delay in inputting parts) into the schedule in order to reduce the likelihood of simultaneous operations. We consider a robust schedule that limits the peak power, in spite of an unexpected fluctuation in the processing time. However, when we insert idle time, the makespan gets longer, and the production efficiency decreases. Therefore, we performed simulations to investigate the optimal amount of idle time and the best point for inserting it. We propose a more robust production scheduling model that considers random processing times and the peak power consumption. The results of experiments show that the effectiveness of the schedule produced by the proposed method is superior to the initial schedule and to a schedule produced by another method. Thus, the use of random processing times can limit the peak power.     

Flow shop scheduling for separation model of set-up and net process based on Branch-and-Bound method

Lots of research reports on flow shop scheduling problems have been reported. Generally speaking, these models are applicable to a simple model with no separation of set-up processes and net ones. In many production lines, we cannot ignore the set-up times in comparison with the net processing times. We can expect to shorten the total processing time by executing the set-up processes and net ones in parallel. We need a parallel operation model to improve schedule results.We will propose a new scheduling method for multi-stage flow shops. The aim of the method is to shorten the total processing time by operating the set-up processes and the net ones of each job in parallel. We applied the Branch-and-Bound method and developed a new calculation algorithm for the lower bound estimation of the total processing time. Finally, we will evaluate our proposed method by some numerical experiments using actual production line data.     

Improved bounds for hybrid flow shop scheduling with multiprocessor tasks

In this paper, we investigate the problem of minimizing makespan in a multistage hybrid flow-shop scheduling with multiprocessor tasks. To generate high-quality approximate solutions to this challenging NP-hard problem, we propose a discrepancy search heuristic that is based on the new concept of adjacent discrepancies. Moreover, we describe a new lower bound based on the concept of dual feasible functions. The proposed lower and upper bounds are assessed through computational experiments conducted on 300 benchmark instances with up to 100 jobs and 8 stages. For these instances, we provide evidence that the proposed bounds consistently outperform the best existing ones. In particular, the proposed heuristic successfully improved the best known solution of 75 benchmark instances.     

A hybrid genetic and variable neighborhood descent algorithm for flexible job shop scheduling problems

This paper addresses the flexible job shop scheduling problem (fJSP) with three objectives: min makespan, min maximal machine workload and min total workload. We developed a hybrid genetic algorithm (GA) for the problem. The GA uses two vectors to represent solutions. Advanced crossover and mutation operators are used to adapt to the special chromosome structure and the characteristics of the problem. In order to strengthen the search ability, individuals of GA are first improved by a variable neighborhood descent (VND), which involves two local search procedures: local search of moving one operation and local search of moving two operations. Moving an operation is to delete the operation, find an assignable time interval for it, and allocate it in the assignable interval. We developed an efficient method to find assignable time intervals for the deleted operations based on the concept of earliest and latest event time. The local optima of moving one operation are further improved by moving two operations simultaneously. An extensive computational study on 181 benchmark problems shows the performance of our approach.     

Minimizing total completion time for re-entrant flow shop scheduling problems

In this paper, we study re-entrant flow shop scheduling problems with the objective of minimizing total completion time. In a re-entrant scheduling problem, jobs may visit some machines more than once for processing. The problem is NP-hard even for machine number m=2. A heuristic algorithm is presented to solve the problem, in which an effective k-insertion technique is introduced as the improvement strategy in iterations. Computational experiments and analyses are performed to give guidelines of choosing parameters in the algorithm. We also provide a lower bound for the total completion time of the optimal solution when there are only two machines. Objective function values of the heuristic solutions are compared with the lower bounds to evaluate the efficiency of the algorithm. For randomly generated instances, the results show that the given heuristic algorithm generates solutions with total completion times within 1.2 times of the lower bounds in most of the cases.     

Genetic algorithm-based heuristics for an open shop scheduling problem with setup,processing, and removal times separated

This report proposes a solution to the open shop scheduling problem with the objective of minimizing total job tardiness in the system. Some practical processing restrictions, such as independent setup and dependent removal times, are taken into account as well. The addressed problem is first described as a 0–1 integer programming model, and is then solved optimally. Subsequently, some hybrid genetic-based heuristics are proposed to solve the problem in an acceptable computation time. To demonstrate the adaptability of these heuristics, some performance comparisons are made with solutions provided by running either a mathematical programming model or certain classic meta-heuristics such as genetic algorithm, simulated annealing, and tabu search in various manufacturing scenarios. The experimental results show that the hybrid genetic-based heuristics perform well, especially the DGA. However, these heuristics require some more additional computations but are still acceptable.