Search

17 páginas nly a few studies in the available scientific literature address the problem of having a group of workers that do not share identical levels of productivity during the planning horizon. This study considers a workforce scheduling problem in which the actual processing time is a function of the scheduling sequence to represent the decline in workers’ performance, evaluating two classical performance measures separately: makespan and maximum tardiness. Several mathematical models are compared with each other to highlight the advantages of each approach. The mathematical models are tested with randomly generated instances available from a public e-library.

A scheduling problem commonly observed in the metal working industry has been studied in this research effort. A job shop equipped with one batch processing machine (BPM) and several unit-capacity machines has been considered. Given a set of jobs, their process routes, processing requirements, and size, the objective is to schedule the jobs such that the makespan is minimized. The BPM can process a batch of jobs as long as its capacity is not exceeded. The batch processing time is equal to the longest processing job in the batch. If no batches were to be formed, the scheduling problem under study reduces to the classical job shop problem with makespan objective, which is known to be nondeterministic polynomial time-hard. A network representation of the problem using disjunctive and conjunctive arcs, and a simulated annealing (SA) algorithm are proposed to solve the problem. The solution quality and run time of SA are compared with CPLEX, a commercial solver used to solve the mathematical formulation and with four dispatching rules. Experimental study clearly highlights the advantages, in terms of solution quality and run time, of using SA to solve large-scale problems.

This paper considers the problem of scheduling a set of jobs subject to arbitrary release dates and sequence-dependent setup times on a single machine with the objective of minimizing the maximum completion of all the jobs, or makespan. This problem is often found in manufacturing processes such as painting and metalworking. A new mixed integer linear program (MILP) is firstly proposed. Because the problem is known to be NP-hard, a beam search heuristic is developed. Computational experiments are carried out using a well-known set of instances from the literature. Our results show that the proposed heuristic is effective in finding high quality solutions at low computational cost. A novel mixed integer linear program is proposed for the scheduling problem.Experiments showed that a commercial solver can only solve small instances.A beam search (BS) heuristic is proposed to solve larger instances.Experiments showed that the BS heuristic finds high quality solutions at low cost.

Given a set of jobs and two batch processing machines (BPMs) arranged in a flow shop environment, the objective is to batch the jobs and sequence the batches such that the makespan is minimized. The job sizes, ready times, and processing times on the two BPMs are known. The batch processing machines can process a batch of jobs as long as the total size of all the jobs assigned to a batch does not exceed its capacity. Once the jobs are batched, the processing time of the batch on the first machine is equal to the longest processing job in the batch; processing time of the batch on the second machine is equal to the sum of processing times of all the jobs in the batch. The batches cannot wait between two machines (i.e., no-wait). The problem under study is NP-hard. We propose a mathematical formulation and present a particle swarm optimization (PSO) algorithm. The solution quality and run time of PSO is compared with a commercial solver used to solve the mathematical formulation. Experimental study clearly highlights the advantages, in terms of solution quality and run time, of using PSO to solve large-scale problems.

A simulated annealing (SA) algorithm to minimize the makespan on a group of identical batch processing machines arranged in parallel is presented. We consider the case where each job has an arbitrary processing time, non-identical size, and non-zero ready time. Each machine can process simultaneously several jobs as a batch as long as the machine capacity is not exceeded. 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 all the jobs in the batch. Random instances were used to compare the results of the SA approach against a lower bound, a mathematical model, and two heuristics published in the literature: the Modified Delay (MD) heuristic and a Greedy Randomized Adaptive Search Procedure (GRASP). Computational experiments showed that the SA approach is comparable to GRASP with respect to solution quality, and less computationally costly. Both SA and GRASP comfortably outperformed the MD heuristic.

This research is motivated by our interactions with an electronics manufacturer who assembles and tests printed circuit boards (PCBs) used in consumer products. Environmental stress screening (ESS) chambers are commonly used to test PCBs to detect early failures before they are used in the field. The chambers are capable of testing multiple PCBs simultaneously (i.e., batch processing machines). The minimum testing time of each PCB and their size are known. The objective is to group these PCBs into batches and schedule the batches formed on ESS chambers such that the makespan is minimized. The ESS chambers can process a batch of jobs as long as its capacity is not violated. Each ESS chamber is unique with respect to its capacity. The problem is NP-hard. Consequently, a particle swarm optimization (PSO) algorithm is proposed. The effectiveness of the PSO algorithm is evaluated by comparing its results to a random-key genetic algorithm and a commercial solver used to solve a mixed-integer linear program. A thorough experimental study conducted indicates that the PSO algorithm reports better quality solution in a short time on larger problem instances.

This research aims at minimizing the makespan of a set of identical batch processing machines arranged in parallel. Each job is defined by its processing time, ready time, and size. Each machine can process several jobs simultaneously as long as the machine capacity is not exceeded. The batch processing and ready times depend upon the batch composition. The batch processing time is equal to the longest processing job in the batch, and the batch ready time is equal to the largest ready time among those jobs in the batch. The problem under study is NP-hard. Consequently, a constructive heuristic is proposed and its performance with respect to solution quality and computational cost is compared against other solution approaches found in the literature. The computational experiments on a set of randomly generated instances show that the performance of the proposed heuristic is competitive with respect to solution quality and requires little computational cost.

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.

This paper considers a two-stage flow shop scheduling problem with a batch processing machine (BPM) in each stage. The processing time of the batch on the first machine is equal to the longest processing job in the batch, and the batch processing time on the second machine is equal to the sum of processing times of all the jobs in the batch. The jobs cannot wait between the two stages. The problem under study with the makespan objective is NP-hard. An ant colony optimisation (ACO) algorithm combined with batch forming and local search heuristics is proposed and its solution is compared with: a particle swarm optimisation (PSO) algorithm; a greedy randomised adaptive search procedure (GRASP) algorithm; and a commercial solver used to solve the mixed-integer linear formulation. The experimental study helps to highlight the advantages, in terms of solution quality and run time, of using ACO to solve large-scale problems.

In a flow shop with two batch processing machines (BPMs) one of the key objectives is to minimise the makespan. In this study jobs with different sizes were batched together, without exceeding the machine capacity, and processed in the BPMs. Job ready times were also taken into consideration hence, a batch cannot be started unless all the jobs in the batch are ready and available. Also, the batches cannot wait between two machines (i.e., no-wait). The problem under study is NP-hard. A greedy randomised adaptive search procedure (GRASP) algorithm has been developed for this problem. Experiments were conducted to study up to 200 job instances. The solution quality of the GRASP algorithm was compared with the results of a mathematical model developed using CPLEX and a particle swarm optimisation algorithm. The experimental study highlights the advantages, in terms of solution quality of using GRASP to solve large-scale problems.

This paper aims to minimise the makespan of a set of identical batch processing machines in parallel. The batch processing machine can process a batch of jobs as long as the total size of all the jobs in the batch does not exceed its capacity. The processing time of the job and its size are given. Batch processing time is equal to the longest processing job in the batch. Two interdependent decisions are required, namely grouping jobs into batches, and scheduling the batches on the machines. The problem under study is NP-hard and hence a Genetic Algorithm (GA) approach is proposed. The effectiveness of the GA approach to solve randomly generated problems was compared with a Simulated Annealing (SA) approach, a Random Keys Genetic Algorithm (RKGA), a Hybrid Genetic Heuristic (HGH) and a commercial solver. The proposed GA approach was found to be very effective in finding a good solution in a short time as opposed to SA, RKGA and a commercial solver. Both GA and HGH are marginally better than each other on different problem instances. [Submitted 17 August 2007; Revised 10 October 2007; Revised 30 May 2008; Revised 29 July 2008; Accepted 15 September 2008]