Scheduling unrelated parallel batch processing machines with non-identical job sizes and unequal ready times

This research analyzes the problem of scheduling a set of n jobs with arbitrary job sizes and non-zero ready times on a set of m unrelated parallel batch processing machines so as to minimize the makespan. Unrelated parallel machine is a generalization of the identical parallel processing machines and is closer to real-world production systems. Each machine can accommodate and process several jobs simultaneously as a batch as long as the machine capacity is not exceeded. The batch processing time and the batch ready time are respectively equal to the largest processing time and the largest ready time among all the jobs in the batch. Motivated by the computational complexity and the practical relevance of the problem, we present several heuristics based on first-fit and best-fit earliest job ready time rules. We also present a mixed integer programming model for the problem and a lower bound to evaluate the quality of the heuristics. The small computational effort of deterministic heuristics, which is valuable in some practical applications, is also one of the reasons that motivates this study. The results show that the heuristic proposed in this paper has a superior performance compared to the heuristics based on ideas proposed in the literature.     

Parallel machine scheduling problems using memetic algorithms

In this paper, we investigate how to apply the hybrid genetic algorithms (the memetic algorithms) to solve the parallel machine scheduling problem. There are two essential issues to be dealt with for all kinds of parallel machine scheduling problems: job partition among machines and job sequence within each machine. The basic idea of the proposed method is that (a) use the genetic algorithms to evolve the job partition and then (b) apply a local optimizer to adjust the job permutation to push each chromosome climb to his local optima. Preliminary computational experiments demonstrate that the hybrid genetic algorithm outperforms the genetic algorithms and the conventional heuristics.     

Scheduling unrelated parallel batch processing machines with non-identical job sizes

Scheduling unrelated parallel batch processing machines to minimize makespan is studied in this paper. Jobs with non-identical sizes are scheduled on batch processing machines that can process several jobs as a batch as long as the machine capacity is not violated. Several heuristics based on best fit longest processing time (BFLPT) in two groups are proposed to solve the problem. A lower bound is also proved to evaluate the quality of the heuristics. Computational experiments were undertaken. These showed that J_SC-BFLPT, considering both load balance of machines and job processing times, was robust and outperformed other heuristics for most of the problem categories.     

Some properties of four-dimensional parallel Turing machines

Informally, the parallel Turing machine (PTM) proposed by Wiedermann is a set of identical usual sequential Turing machines (STMs) cooperating on two common tapes: a storage tape and an input tape. Moreover, STMs which represent the individual processors of a parallel computer can multiply themselves in the course of computation. On the other hand, during the past 7 years or so, automata on a four-dimensional tape have been proposed as computational models of four-dimensional pattern processing, and several properties of such automata have been obtained. We proposed a four-dimensional parallel Turing machine (4-PTM), and dealt with a hardware-bounded 4-PTM in which each side-length of each input tape is equivalent. We believe that this machine is useful in measuring the parallel computational complexity of three-dimensional images. In this work, we continued the study of the 3-PTM, in which each side-length of each input tape is equivalent, and investigated some of its accepting powers.     

Unrelated parallel machine scheduling with setup times and a total weighted tardiness objective

This paper presents several search heuristics and their performance in batch scheduling of parallel, unrelated machines. Identical or similar jobs are typically processed in batches in order to decrease setup times and/or processing times. The problem accounts for allotting batched work parts into unrelated parallel machines, where each batch consists of a fixed number of jobs. Some batches may contain different jobs but all jobs within each batch should have an identical processing time and a common due date. Processing time of each job of a batch is determined according to the machine group as well as the batch group to which the job belongs. Major or minor setup times are required between two subsequent batches depending on batch sequence but are independent of machines. The objective of our study is to minimize the total weighted tardiness for the unrelated parallel machine scheduling. Four search heuristics are proposed to address the problem, namely (1) the earliest weighted due date, (2) the shortest weighted processing time, (3) the two-level batch scheduling heuristic, and (4) the simulated annealing method. These proposed local search heuristics are tested through computational experiments with data from dicing operations of a compound semiconductor manufacturing facility.     

New architectures: Performance highlights and new algorithms

Parallel computers are having a profound impact on computational science. Recently highly parallel machines have taken the lead as the fastest supercomputers, a trend that is likely to accelerate in the future. We describe some of these new computers, and issues involved in using them. We present elliptic PDE solutions currently running at 3.8 gigaflops, and an atmospheric dynamics model running at 1.7 gigaflops, on a 65 536-processor computer.

One intrinsic disadvantage of a parallel machine is the need to perform inter-processor communication. It is important to ensure that such communication time is maintained at a small fraction of computation time. We analyze standard multigrid algorithms in two and three dimensions from this point of view, indicating that performance efficiencies in excess of 95% are attainable under suitable conditions on moderately parallel machines. We also demonstrate that such performance is not attainable for multigrid on massively parallel computers, as indicated by an example of poor multigrid efficiency on 65 536 processors. The fundamental difficulty is the inability to keep 65 536 processors busy when operating on very coarse grids.

Most algorithms used for implementing applications on parallel machines have been derived directly from algorithms designed for serial machines. The previously mentioned multigrid example indicates that such ‘parallelized’ algorithms may not always be optimal. Parallel machines open the possibility of finding totally new approaches to solving standard tasks—intrinsically parallel algorithms. In particular, we present a class of superconvergent multiple scale methods that were motivated directly by massevely parallel machines. These methods differ from standard multigrid methods in an intrinsic way, and allow all processors to be used at all times, even when processing on the coarsest grid levels. Their serial versions are not sensible algorithms. The idea that parallel hardware—the Connection Machine in this case—can lead to discovery of new mathematical algorithms was surprising for us.     

A GRASP approach for makespan minimization on parallel batch processing machines

In this paper we consider the problem of scheduling a set of identical batch processing machines arranged in parallel. A Greedy Randomized Adaptive Search Procedure (GRASP) approach is proposed to minimize the makespan under the assumption of non-zero job ready times, arbitrary job sizes and arbitrary processing times. Each machine can process simultaneously several jobs as a batch as long as the machine capacity is not violated. The batch processing time is equal to the largest processing time among those jobs in the batch. Similarly, the batch ready time is equal to the largest ready time among those jobs in the batch. The performance of the proposed GRASP approach was evaluated by comparing its results to a lower bound and heuristics published in the literature. Experimental study suggests that the solution obtained from the GRASP approach is superior compared to other heuristics.     

Three-dimensional parallel Turing machines

Informally, the parallel Turing machine (PTM) proposed by Wiedermann is a set of identical usual sequential Turing machines (STMs) cooperating on two common tapes: storage tape and input tape. Moreover, STMs which represent the individual processors of a parallel computer can multiply themselves in the course of computation. On the other hand, during the past 25 years or so, automata on a three-dimensional tape have been proposed as computational models of three-dimensional pattern processing, and several properties of such automata have been obtained. We proposed a three-dimensional parallel Turing machine (3-PTM), and dealt with a hardware-bounded 3-PTM whose inputs are restricted to cubic ones. We believe that this machine is useful in measuring the parallel computational complexity of three-dimensional images. In this article, we continue the study of 3-PTM, whose inputs are restricted to cubic ones, and investigate some of its accepting powers. This work was presented in part at the 12th International Symposium on Artificial Life and Robotics, Oita, Japan, January 25–27, 2007     

Parallel machine scheduling problems in green manufacturing industry

Manufacturing companies are now more conscious about the environment. As such, there are more concerns in reducing the consumption of energy and the production of pollutants. Reduced consumption of energy will save cost, while reduction of pollutants will decrease the cost of cleaning up the environment. This paper considers scheduling problems that arise in green manufacturing companies. Suppose the manufacturing company has a set of parallel machines. Each machine has a cost per unit time that differs from machine to machine. The cost here is the sum of the energy cost and the clean up cost. A set of jobs is to be processed by these machines. Our goal is to find a schedule that minimizes the makespan (schedule length) or the total completion time, subject to the constraint that the total cost is not more than a given threshold value. We propose efficient heuristics and show, by computational experiments, that they perform very well in practice.     

Some accepting powers of three-dimensional parallel Turing machines

Informally, the parallel Turing machine (PTM) proposed by Wiedermann is a set of identical usual sequential Turing machines (STMs) cooperating on two common tapes: storage tape and input tape. Moreover, STMs which represent the individual processors of a parallel computer can multiply themselves in the course of computation. On the other hand, during the past 25 years or so, automata on a three-dimensional tape have been proposed as computational models of three-dimensional pattern processing, and several properties of such automata have been obtained. We proposed a three-dimensional parallel Turing machine (3-PTM),¹ and dealt with a hardware-bounded 3-PTM whose inputs are restricted to cubic ones. We believe that this machine is useful in measuring the parallel computational complexity of three-dimensional images. Here, we continue the study of 3-PTM, whose inputs are restricted to cubic ones, and investigate some of its accepting powers. This work was presented in part at the First European Workshop on Artificial Life and Robotics, Vienna, Austria, July 12–13, 2007     

Scheduling algorithms for heterogeneous batch processors with incompatible job-families

We consider the problem of scheduling heterogeneous batch processors (i.e., batch processors with different capacity) with incompatible job-families and non-identical job sizes to maximize the utilization of the batch processors. We analyzed the computational complexity of this problem and showed that it is NP-hard and proposed eight variants of a fast greedy heuristic. A series of computational experiments were carried out to compare the performance of the heuristics and showed that the heuristics are capable of consistently obtaining near (estimated) optimal solutions with very low-computational burden for large-scale problems. We also carried out a study to find the effect of family processing time changes on the performance of the heuristics. This sensitivity analysis indicated that the processing time set of job-families influences the performance of the heuristic algorithms.     

Minimizing the normalized sum of square for workload deviations on m parallel processors

In many organizations, it is desirable to distribute workload as equally as possible among a group of employees or machines. This paper proposes a performance measure, that we call the Normalized Sum of Square for Workload Deviations (NSSWD), and studies the problem of how to schedule a set of n jobs on m parallel identical processors in order to minimize the NSSWD. The NSSWD criterion is relevant where uniformity of wear to machines or of workload to employees is desirable. An algorithm, called Workload Balancing (WB), is proposed for solving this problem. Moreover, we perform a simulation experiment to evaluate WB against several well-known heuristics in the literature. Lastly, we discuss the computational results obtained from the simulation experiment.     

Tight bounds for the identical parallel machine scheduling problem

We address the problem of minimizing makespan on identical parallel machines. We propose new lower bounding strategies and heuristics for this fundamental scheduling problem. The lower bounds are based on the so‐called lifting procedure. In addition, two optimization‐based heuristics are proposed. These heuristics require iteratively solving a subset‐sum problem. We present the results of computational experiments that provide strong evidence that the new proposed lower and upper bounds consistently outperform the best bounds from the literature.     

Scheduling two-stage hybrid flow shops with parallel batch, release time, and machine eligibility constraints

This paper investigates a difficult scheduling problem on a specialized two-stage hybrid flow shop with multiple processors that appears in semiconductor manufacturing industry, where the first and second stages process serial jobs and parallel batches, respectively. The objective is to seek job-machine, job-batch, and batch-machine assignments such that makespan is minimized, while considering parallel batch, release time, and machine eligibility constraints. We first propose a mixed integer programming (MIP) formulation for this problem, then gives a heuristic approach for solving larger problems. In order to handle real world large-scale scheduling problems, we propose an efficient dispatching rule called BFIFO that assigns jobs or batches to machines based on first-in-first-out principle, and then give several reoptimization techniques using MIP and local search heuristics involving interchange, translocation and transposition among assigned jobs. Computational experiments indicate our proposed re-optimization techniques are efficient. In particular, our approaches can produce good solutions for scheduling up to 160 jobs on 40 machines at both stages within 10?min.     

Scheduling Parallel Machines for the Customer Order Problem

This paper considers scheduling problems where jobs are dispatched in batches. The objective is to minimize the sum of the completion times of the batches. While a machine can process only one job at a time, multiple machines can simultaneously process jobs in a batch. This simple environment has a variety of real world applications such as part kitting and customer order scheduling.A heuristic is presented for the parallel machine version of the problem. Also, a tight worst case bound on the relative error is found. For the case of two parallel machines, we examine two heuristics, which are based on simple scheduling rules. We find tight worst case bounds of 6/5 and 9/7 on the relative error and show that neither procedure is superior for all instances. Finally, we empirically evaluate these two heuristics. For large problems, the methods find solutions that are close to optimal.     

Hybrid genetic algorithms with dispatching rules for unrelated parallel machine scheduling with setup time and production availability

This article considers the unrelated parallel machine scheduling problem with sequence- and machine-dependent setup times and machine-dependent processing times. Furthermore, the machine has a production availability constraint to each job. The objective of this problem is to determine the allocation policy of jobs and the scheduling policy of machines to minimize the total completion time. To solve the problem, a mathematical model for the optimal solution is derived, and hybrid genetic algorithms with three dispatching rules are proposed for large-sized problems. To assess the performance of the algorithms, computational experiments are conducted and evaluated using several randomly generated examples.     

Completion time variance minimization in single machine and multi-machine systems

In this paper we consider the problem of minimizing the completion time variance of n jobs on a single machine with deterministic processing times. We propose a new heuristic and compare the results with existing popular heuristics for the problem. We also propose a method based on genetic algorithms to solve the problem. We present the worst case performance analysis of the proposed heuristic. We also consider the problem of minimizing the completion time variance of n jobs on m identical parallel machines in both restricted and unrestricted versions. A heuristic method and a method based on genetic algorithms are presented for both the cases and results of computational testing are provided. It is concluded that the proposed methods provide better results compared to existing methods for the single machine case as well as for the multi-machine case.     

Dispatching heuristics for the single machine early/tardy scheduling problem with job-independent penalties

In this paper, we consider the single machine earliness/tardiness scheduling problem with job-independent penalties, and no machine idle time. Several dispatching heuristics are proposed, and their performance is analysed on a wide range of instances. The heuristics include simple scheduling rules, as well as a procedure that takes advantage of the strengths of each of those rules. We also consider early/tardy dispatching procedures, and a heuristic method based on existing adjacent precedence conditions. An improvement procedure that can be used to improve the schedules generated by the heuristics is also proposed.

The computational tests show that the best results are given by the early/tardy dispatching rules. These heuristics are also quite fast, and are capable of quickly solving even very large instances. The use of the improvement procedure is recommended, since it improves the solution quality, with little additional computational effort.     

Scheduling injection molding operations with multiple resource constraints and sequence dependent setup times and costs

This paper addresses a production scheduling problem in an injection molding facility. It appears to be the first attempt to schedule parallel machines for multiple items in presence of multiple capacitated resource constraints with sequence-dependent setup costs and times. The objective is to meet customer demands while minimizing the total inventory holding costs, backlogging costs and setup costs. We present a mathematical formulation of the problem. The computational complexity associated with the formulation makes it difficult for standard solvers address industrial-dimensioned problems in reasonable solution time. To overcome this, a two-phase workcenter-based decomposition scheme has been developed in this paper. The computational results for different problem sizes demonstrate that this scheme is able to solve industrial-dimensioned problems within reasonable time and accuracy.     

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.