Minimizing makespan in three-machine flow shops with deteriorating jobs

In this paper, a three-machine permutation flow shop scheduling problem with time-dependent processing times is considered. By the time-dependent processing times we mean that the job's processing time is an increasing function of its starting time. The objective is to find a sequence that minimizes the makespan. This problem is well known to be NP-hard. Several dominance properties and a lower bound are derived to speed up the elimination process of a branch-and-bound algorithm. Moreover, two heuristic algorithms are proposed to overcome the inefficiency of the branch-and-bound algorithm. Computational experiments on randomly generated problems are conducted to evaluate the branch-and-bound algorithm and heuristic algorithm. Computational results show that the proposed heuristic algorithm M-NEH perform effectively and efficiently.     

Bicriterion scheduling with equal processing times on a batch processing machine

In this paper we consider the problem of scheduling jobs with equal processing times on a single batch processing machine so as to minimize a primary and a secondary criteria. We provide optimal polynomial time algorithms for various combinations of the primary and secondary criteria.     

Minimizing the makespan in a single machine scheduling problem with a time-based learning effect

Both the building cost and the multiple-source routing cost are important considerations in construction of a network system. A spanning tree with minimum building cost among all spanning trees is called a minimum spanning tree (MST), and a spanning tree with minimum k-source routing cost among all spanning trees is called a k-source minimum routing cost spanning tree (k-MRCT). This paper proposes an algorithm to construct a spanning tree T for a metric graph G with a source vertex set S such that the building cost of T is at most 1+2/(α−1) times of that of an MST of G, and the k-source routing cost of T is at most α(1+2(k−1)(n−2)/k(n+k−2)) times of that of a k-MRCT of G with respect to S, where α>1, k=|S| and n is the number of vertices of G.     

A branch-and-bound algorithm for the three-machine flowshop scheduling problem with bicriteria of makespan andtotal flowtime

This paper addresses the three‐machine flowshop scheduling problem with a bicriteria of minimizing a weighted sum of makespan and total flowtime. Three lower bounds, an upper bound, and several dominance relations are developed. The upper bound is developed using a two‐phase hybrid heuristic method. A branch‐and‐bound algorithm, incorporating the developed bounds and dominance relations, is presented. An extensive computational analysis on randomly generated problems is conducted. The analysis indicates that the proposed bounds, dominance relations, and branch‐and‐bound algorithm are efficient.     

A genetic algorithm for minimizing maximum lateness on parallel identical batch processing machines with dynamic job arrivals and incompatible job families

We consider the problem of minimizing maximum lateness on parallel identical batch processing machines with dynamic job arrivals. We propose a family of iterative improvement heuristics based on previous work by Potts [Analysis of a heuristic for one machine sequencing with release dates and delivery times. Operations Research 1980;28:1436–41] and Uzsoy [Scheduling batch processing machines with incompatible job families. International Journal for Production Research 1995;33(10):2685–708] and combine them with a genetic algorithm (GA) based on the random keys encoding of Bean [Genetic algorithms and random keys for sequencing and optimization. ORSA Journal on Computing 1994;6(2):154–60]. Extensive computational experiments show that one of the proposed GAs runs significantly faster than the other, providing a good tradeoff between solution time and quality. The combination of iterative heuristics with GAs consistently outperforms the iterative heuristics on their own.     

Minimizing the number of tardy jobs in a single-machine scheduling problem with periodic maintenance

This research focuses on the problem of scheduling jobs on a single machine that requires periodic maintenance with the objective of minimizing the number of tardy jobs. We present a two-phase heuristic algorithm in which an initial solution is obtained first with a method modified from Moore's algorithm for the problem without maintenance and then the solution is improved in the second phase. Performance of the proposed heuristic algorithm is evaluated through computational experiments on randomly generated problem instances and results show that the heuristic gives solutions close to those obtained from a commercial integer programming solver in much shorter time and works better than an existing heuristic algorithm in terms of the solution quality.     

A genetic algorithm for solving economic lot size scheduling problem

The purpose of this research is to determine an optimal batch size for a product and purchasing policy of associated raw materials. Like most other practical situation, this manufacturing firm has a limited storage space and transportation fleet of known capacity. The mathematical formulation of the problem indicates that the model is a constrained nonlinear integer program. Considering the complexity of solving such model, we investigate the use of genetic algorithms (GAs) for solving this model. We develop GA code with three different penalty functions usually used for constraint optimizations. The model is also solved using an existing commercial optimization package to compare the solution. The detailed computational results are presented.     

A two-machine flowshop makespan scheduling problem with deteriorating jobs

In traditional scheduling problems, the job processing times are assumed to be known and fixed from the first job to be processed to the last job to be completed. However, in many realistic situations, a job will consume more time than it would have consumed if it had begun earlier. This phenomenon is known as deteriorating jobs. In the science literature, the deteriorating job scheduling problems are relatively unexplored in the flowshop settings. In this paper, we study a two-machine flowshop makespan scheduling problem in which job processing times vary as time passes, i.e. they are assumed as increasing functions of their starting times. First, an exact algorithm is established to solve most of the problems of up to 32 jobs in a reasonable amount of time. Then, three heuristic algorithms are provided to derive the near-optimal solutions. A simulation study is conducted to evaluate the performances of the proposed algorithms. In addition, the impact of the deterioration rate is also investigated.     

A two-machine flowshop scheduling problem with a separated maintenance constraint

This paper considers a two-machine flowshop scheduling problem with a separated maintenance constraint. This means that the machine may not always be available during the scheduling period. It needs a constant time to maintain the machine after completing a fixed number of jobs at most. The objective is to find the optimal job combinations and the optimal job schedule such that the makespan is minimized. The proposed problem has some practical applications, for example, in electroplating process, the electrolytic cell needs to be cleaned and made up a deficiency of medicine. In this paper, we propose a heuristic algorithm to solve this problem. Some polynomially solvable cases and computational experiments are also provided.     

A hybrid genetic heuristic for scheduling parallel batch processing machines with arbitrary job sizes

This paper investigates the scheduling problem of parallel identical batch processing machines in which each machine can process a group of jobs simultaneously as a batch. Each job is characterized by its size and processing time. The processing time of a batch is given by the longest processing time among all jobs in the batch. Based on developing heuristic approaches, we proposed a hybrid genetic heuristic (HGH) to minimize makespan objective. To verify the performance of our algorithm, comparisons are made through using a simulated annealing (SA) approach addressed in the literature as a comparator algorithm. Computational experiments reveal that affording the knowledge of problem through using heuristic procedures, gives HGH the ability of finding optimal or near optimal solutions in a reasonable time.     

A branch-and-bound algorithm for single-machine scheduling with batch delivery and job release times

This paper addresses scheduling a set of jobs with specified release times on a single machine for delivery in batches to customers or to other machines for further processing. This problem is a natural extension of minimizing the sum of flow times in the presence of release time by considering the possibility of delivering jobs in batches and introducing batch delivery costs. The scheduling objective adopted is that of minimizing the sum of flow times and delivery costs. The extended problem arises in the context of coordination between machine scheduling and a distribution system in a supply chain network. Structural properties of the problem are investigated and used to devise a branch-and-bound solution scheme. Computational experiments show significant improvement over an existing dynamic programming algorithm.     

A multi-objective electromagnetism algorithm for a bi-objective flowshop scheduling problem

This paper deals with a bi-objective flowshop scheduling problem minimizing the makespan and total weighted tardiness, in which all jobs may not be processed by all machines. Furthermore, we consider transportation times between machines. 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 multi-objective electromagnetism algorithm (MOEM). The motivation behind this algorithm has risen from the attraction–repulsion mechanism of electromagnetic theories. Along with MOEA, we apply simulated annealing to solve the given problem. A set of experimental instances are carried out to evaluate the algorithm by advanced multi-objective performance measures. The related results show that a variant of our proposed MOEM provides sound performance comparing with other algorithms.     

Two-stage hybrid batching flowshop scheduling with blocking and machine availability constraints using genetic algorithm

This research investigates a two-stage hybrid flowshop scheduling problem in a metal-working company. The first stage consists of multiple parallel machines and the second stage has only one machine. Four characteristics of the company have substantiated the complexity of the problem. First, all machines in stage one are able to process multiple jobs simultaneously but the jobs must be sequentially set up one after another. Second, the setup time of each job is separated from its processing time and depends upon its preceding job. Third, a blocking environment exists between two stages with no intermediate buffer storage. Finally, machines are not continuously available due to the preventive maintenance and machine breakdown. Two types of machine unavailability, namely, deterministic case and stochastic case, are identified in this problem. The former occurs on stage-two machine with the start time and the end time known in advance. The latter occurs on one of the parallel machine in stage one and a real-time rescheduling will be triggered. Minimizing the makespan is considered as the objective to develop the optimal scheduling algorithm. A genetic algorithm is used to obtain a near-optimal solution. The computational results with actual data are favorable and superior over the results from existing manual schedules.     

Permutation flowshop problems with bi-criterion makespan and total completion time objective and position-weighted learning effects

In this paper, we study the problem of minimizing the weighted sum of makespan and total completion time in a permutation flowshop where the processing times are supposed to vary according to learning effects. The processing time of a job is a function of the sum of the logarithms of the processing times of the jobs already processed and its position in the sequence. We present heuristic algorithms, which are modified from the optimal schedules for the corresponding single machine scheduling problem and analyze their worst-case error bound. We also adopt an existing algorithm as well as a branch-and-bound algorithm for the general m-machine permutation flowshop problem. For evaluation of the performance of the algorithms, computational experiments are performed on randomly generated test problems.     

Minimizing makespan for multi-spindle head machines with a mobile table

This paper presents a novel application of operational research techniques in Manufacturing. This concerns scheduling of multi-spindle head machines with a mobile table to minimize the makespan. We show that this problem can be formulated as scheduling for a single max-batch processing machine with inclusion, exclusion and precedence constraints between jobs. What makes this study unique from others in literature is that the batch processing time can exceed that of the longest job in the batch. The job compatibility and the batch time depend on the batch content, i.e. which jobs constitute the batch. This problem is transformed into finding the constrained shortest path in a specially constructed digraph. Dominance properties are developed to decrease the digraph's size. An industrial example is presented to illustrate the effectiveness of the proposed techniques.     

Efficient non-population-based algorithms for the permutation flowshop scheduling problem with makespan minimisation subject to a maximum tardiness

This paper focuses on the problem of scheduling jobs in a permutation flowshop with the objective of makespan minimisation subject to a maximum allowed tardiness for the jobs, a problem that combines two desirable manufacturing objectives related to machine utilisation and to customer satisfaction. Although several approximate algorithms have been proposed for this NP-hard problem, none of them can use the excellent speed-up method by Taillard (1990) [22] for makespan minimisation due to the special structure of the problem under consideration. In this paper, several properties of the problem are defined in order to be able to partly apply Taillard׳s acceleration. This mechanism, together with a novel feasible tabu local search method, allows us to further exploit the structure of solutions of the problem, and are incorporated in two proposed algorithms: a bounded-insertion-based constructive heuristic and an advanced non-population-based algorithm. These algorithms are compared with state-of-the-art algorithms under the same computer conditions. The results show that both algorithms improve existing ones and therefore, constitute the new state-of-art approximate solution procedures for the problem.     

Enhanced grouping league championship and optics inspired optimization algorithms for scheduling a batch processing machine with job conflicts and non-identical job sizes

This research aims to address scheduling of a single batch processing machine, where jobs are in different sizes and have a conflicting nature with each other, in the sense that two conflicting jobs cannot share the same batch and hence, cannot be processed simultaneously by the machine. The problem is referred to as SBMC. After formulating the problem, a strong lower bound procedure is developed by transforming a relaxed version of the scheduling problem to the multiple bottleneck transportation problem (MTP) with conflicts. An efficient Lagrangian relaxation procedure is proposed, which takes advantage of decomposable nature of the relaxed problem, to attain a lower bound for MTP which in essence is a lower bound for SBMC. To solve the problem, two metaheuristic algorithms, namely the League Championship Algorithm (LCA) and Optic Inspired Optimization (OIO), are adapted and fundamentally modified to match the problem unique structure (i.e., the grouping structure) and accordingly the grouping version of these algorithms is developed. The effectiveness of the lower bound procedure, as well as algorithms, are evaluated through extensive computational experiments. To show they perform efficiently in running times and effective in finding near-optimal bounds for most of the problem instances, we generate 20 different classes of problems according to variability in job sizes, number of jobs and density of incompatibility matrix. Then, we make comparison with two of extensively used algorithms from literature, SA and GA. Our proposed algorithms obtain solutions with objective values less than 6% gap from the lower bound and outperform SA and GA algorithms, especially for large instances. Moreover, values of the lower bound procedure lie within less than 4% of objective values provided by CPLEX.     

Extended artificial chromosomes genetic algorithm for permutation flowshop scheduling problems

In our previous researches, we proposed the artificial chromosomes with genetic algorithm (ACGA) which combines the concept of the Estimation of Distribution Algorithms (EDAs) with genetic algorithms (GAs). The probabilistic model used in the ACGA is the univariate probabilistic model. We showed that ACGA is effective in solving the scheduling problems. In this paper, a new probabilistic model is proposed to capture the variable linkages together with the univariate probabilistic model where most EDAs could use only one statistic information. This proposed algorithm is named extended artificial chromosomes with genetic algorithm (eACGA). We investigate the usefulness of the probabilistic models and to compare eACGA with several famous permutation-oriented EDAs on the benchmark instances of the permutation flowshop scheduling problems (PFSPs). eACGA yields better solution quality for makespan criterion when we use the average error ratio metric as their performance measures. In addition, eACGA is further integrated with well-known heuristic algorithms, such as NEH and variable neighborhood search (VNS) and it is denoted as eACGA_hybrid to solve the considered problems. No matter the solution quality and the computation efficiency, the experimental results indicate that eACGA_hybrid outperforms other known algorithms in literature. As a result, the proposed algorithms are very competitive in solving the PFSPs.     

A grasp algorithm for m-machine flowshop scheduling problem with bicriteria of makespan and maximum tardiness

In this paper we address the problem of minimizing the weighted sum of makespan and maximum tardiness in an m-machine flow shop environment. This is a NP-hard problem in the strong sense. An attempt has been made to solve this problem using a metaheuristic called Greedy Randomized Adaptive Search Procedure (GRASP). GRASP is a competitive algorithm and is a meta-heuristic for solving combinatorial optimization problems. We have customized the basic concepts of GRASP algorithm to solve a bicriteria flow shop problem and a new algorithm named B-GRASP (Bicriteria GRASP algorithm) is proposed. The new proposed algorithm is evaluated using benchmark problems taken from Taillard and compared with the existing simulated annealing based heuristic developed by Chakravarthy and Rajendran. Computational experiments indicate that the proposed algorithm is much better than the existing one in all cases.     

Spanning tree-based genetic algorithm for bicriteria transportation problem

In this paper, we present a new approach which is spanning tree-based genetic algorithm for bicriteria transportation problem. The transportation problem have the special data structure in solution characterized as a spanning tree. In encoding transportation problem, we introduce one of node encoding which is adopted as it is capable of equally and uniquely representing all possible basic solutions. The crossover and mutation was designed based on this encoding. And we designed the criterion that chromosome always feasibility converted to a transportation tree. In the evolutionary process, the mixed strategy and roulette wheel selection is used. Numerical experiments will be shown the effectiveness and efficiency of the proposed algorithm.