Single machine batch scheduling with sequential job processing

The problem of scheduling n jobs on a single machine in batches to minimize some regular cost functions is studied. Jobs within each batch are processed sequentially so that the processing time of a batch is equal to the sum of the processing times of the jobs contained in it. Jobs in the same batch are completed at the same time when the last job of the batch has finished its processing. A constant set-up time precedes the processing of each batch. The number of jobs in each batch is bounded by some value b. If b < n, then the problem is called bounded. Otherwise, it is unbounded. For both the bounded and unbounded problems, dynamic programming algorithms are presented for minimizing the maximum lateness, the number of late jobs, the total tardiness, the total weighted completion time, and the total weighted tardiness when all due dates are equal, which are polynomial if there is a fixed number of distinct due dates or processing times. More efficient algorithms are derived for some special cases of both the bounded and unbounded problems in which all due dates and/or processing times are equal. Several special cases of the bounded problem are shown to be NP-hard. Thus, a comprehensive classification of the computational complexities of the special cases is provided.     

On bilevel machine scheduling problems

Bilevel scheduling problems constitute a hardly studied area of scheduling theory. In this paper, we summarise the basic concepts of bilevel optimisation, and discuss two problem classes for which we establish various complexity and algorithmic results. The first one is the bilevel total weighted completion time problem in which the leader assigns the jobs to parallel machines and the follower sequences the jobs assigned to each machine. Both the leader and the follower aims to minimise the total weighted completion time objective, but with different job weights. When the leader’s weights are arbitrary, the problem is NP-hard. However, when all the jobs are of unit weight for the leader, we provide a heuristic algorithm based on iterative LP-rounding along with computational results, and provide a sufficient condition when the LP-solution is integral. In addition, if the follower weights induce a monotone (increasing or decreasing) processing time order in any optimal solution, the problem becomes polynomially solvable. As a by-product, we characterise a new polynomially solvable special case of the MAX m-CUT problem, and provide a new linear programming formulation for the P||?_j C_j{P||\sum_j C_j} problem. Finally, we present some results on the bilevel order acceptance problem, where the leader decides on the acceptance of orders and the follower sequences the jobs. Each job has a deadline and if a job is accepted, it cannot be late. The leader’s objective is to maximise the total weight of accepted jobs, whereas the follower aims at minimising the total weighted job completion times. For this problem, we generalise some known single-level machine scheduling algorithms.     

Single machine scheduling problems with generalised due-dates and job-rejection

We study single machine scheduling problems. Generalised due dates are assumed, i.e. job due dates are specified according to the positions of the jobs in the sequence, rather than their identity. Thus, assuming that due dates are numbered in a non-decreasing order, the jth due date refers to the job assigned to the jth position. In addition, we allow the option of job rejection, i.e. not all jobs must be processed. In this case, the scheduler is penalised for each rejected job, and the total rejection cost becomes part of the objective function. Two objective functions are considered: maximum tardiness plus rejection cost, and total tardiness plus rejection cost. Both problems are proved to be NP-hard. Pseudo-polynomial dynamic programmes and efficient heuristics are introduced and tested numerically.     

Single machine group scheduling with family setups to minimize total tardiness

This paper considers the single machine scheduling problem with independent family (group) setup times where jobs in each family are processed together. A sequence-independent setup is required to process a job from a different family. The objective is to minimize total tardiness. A mixed-integer linear programming model capable of solving small-sized problems is described. In view of the NP-hard nature of the problem, two-phase heuristics including simulated annealing algorithms are proposed to find optimal or near-optimal schedules. Empirical results show that the proposed heuristic algorithms are quite effective in minimizing total tardiness for a single machine group scheduling problem with family setup times.     

Sequency on two and three machines with setup,processing and removal times separated

n jobs are to be processed on two or three machines. Each job must be processed in sequence, first on machine I than on machine II, etc. For each job, setup time, processing time, and removal time is known in each machine. Algorithms are developed which determine an optimal sequence that minimizes the total elapsed time. Numerical examples illustrate the algorithms.     

A branch & bound method for the general-shop problem with sequence dependent setup-times

A branch & bound algorithm is presented for a very general scheduling problem withn jobs andm machines. Each job consists of a set of operations. Each operation has to be processed on a dedicated machine. There may be arbitrary precedence relations between the operations. The set of all operations is partitioned into groups. If on a machine an operation belonging to groupG _g is processed immediately after an operation belonging to groupG _f there is a setup ofs _fg time units. We assume thats _fg=0 iff=g and that thes _fg satisfy the triangle inequality. Computational results for this general problem as well as for special cases like the job-shop problem and the open-shop problem are reported.Supported by the Deutsche Forschungsgemeinschaft (Project JoPTAG) and by INTAS (Project 93–257)     

Minimizing the makespan for the two-machine scheduling problem with a single server: Two algorithms for very large instances

This article considers the problem of scheduling a given set of n jobs on two identical parallel machines with a single server. Each job must be processed on one of the machines. Before processing, the server has to set up the relevant machine. The objective is to minimize the makespan. For this unary NP-hard problem, two fast constructive algorithms with a complexity of O(n²) are presented. The performance of these algorithms is evaluated for instances with up to 10,000 jobs. Computational results indicate that the algorithms have an excellent performance for very large instances so that the obtained objective function values are very close to a lower bound, and in many cases even an optimal solution is achieved. Superiority over all existing algorithms is obtained by sequencing the jobs on the two machines so that the machine idle time and the server waiting time are minimized. In doing so, the characteristics of an optimal solution resulting from its relevant lower bound are taken into account.     

Minimizing total tardiness on a batch processing machine with incompatible job families

Motivated by an application in semiconductor manufacturing, we study the problem of minimizing total tardiness on a batch processing machine with incompatibl8e job families, where all jobs of the same family have identical processing times and jobs of different families cannot be processed together. We present a dynamic programming algorithm which has polynomial time complexity when the number of job families and the batch machine capacity are fixed. We also examine various heuristic solution procedures which can provide near optimal solutions in a reasonable amount of computation time.     

Iterative algorithms for batching and scheduling to minimise the total job tardiness in two-stage hybrid flow shops

This study considers the batching and scheduling problem in two-stage hybrid flow shops in which each job with a distinct due-date is processed through two serial production stages, each of which has identical machines in parallel. Under the fundamental trade-off that large batch sizes with less frequent changeovers may reduce setup costs and hence increase machine utilisation, while small batch sizes may reduce job flow times and hence improve scheduling performance, the problem is to determine the number of batches, the batch compositions, the allocation of batches to the parallel machines at each stage, and the sequence of the batches allocated to each machine for the objective of minimising the total job tardiness. A mixed integer programming model is developed for the reduced problem in which the number of batches is given, and then, three iterative algorithms are proposed in which batching and scheduling are done repeatedly until a good solution is obtained. To show the performance of the algorithms, computational experiments were done on a number of test instances, and the results are reported. In particular, we show that the number of batches decreases as the ratio of the batch setup time to the job processing time increases.     

Batching and scheduling to minimize the makespan in the two-machine flowshop

In this paper, we consider a class of batching and scheduling problems in the two-machine flowshop where one of the machines is a discrete processor and the other one is a batch processor. The jobs are processed separately on the discrete processor and processed in batches on the batch processor. The processing time of a batch is equal to the total processing time of the jobs contained in it, and the completion time of a job in a batch is defined as the completion time of the batch containing it. A constant setup time is incurred whenever a batch is formed on the batch processor. The problem is to find the optimal batch compositions and the optimal schedule of the batches so that the makespan is minimized. All problems in this class are shown to be NP-complete in the ordinary sense. We also identify some polynomially solvable cases by introducing their corresponding solution methods.     

An improved approximation algorithm for the two-machine open shop scheduling problem with family setup times

We consider the problem of scheduling families of jobs in a two-machine open shop so as to minimize the makespan. The jobs of each family can be partitioned into batches and a family setup time on each machine is required before the first job is processed, and when a machine switches from processing a job of some family to a job of another family. For this NP-hard problem the literature contains (5/4)-approximation algorithms that cannot be improved on using the class of group technology algorithms in which each family is kept as a single batch. We demonstrate that there is no advantage in splitting a family more than once. We present an algorithm that splits one family at most once on a machine and delivers a worst-case performance ratio of 6/5.     

Integrated production scheduling and batch delivery with fixed departure times and inventory holding costs

In this paper, we address a model for supply chain coordination. There are m manufacturers modelled as single machines, each of which processes a specific set of jobs (products). After processing is completed, jobs are batched, and batches are shipped to a customer by means of vehicles. The problem consists in concurrently finding a production schedule of the jobs, a partition of jobs into delivery batches and an assignment of delivery batches to vehicles, so that jobs are delivered within their deadlines and total costs are minimised. We focus on a scenario characterised by fixed departure times and inventory holding costs. For each departure time there is a given number of vehicles, possibly having limited capacity. Each job incurs a cost proportional to the time from job completion to delivery departure. In this paper, we show that the problem is NP-hard even for a very restricted case, and report various polynomiality results for two scenarios, namely: (i) when the production sequence of each manufacturer is fixed in advance, and (ii) when there is a single manufacturer and processing times are all equal to 1. We also point out several open problems.     

AN ITERATIVE SOLUTION SCHEME FOR SYSTEMS OF WEAKLY CONNECTED BOUNDARY ELEMENT EQUATIONS

In this paper an iterative scheme of first degree is developed for solving linear systems of equations. The systems investigated are those which are derived from boundary integral equations and are of the form ∑^N_j=1H_ijx_j=c_i, i=1, 2,…,N, where H_ij are matrices, x_j and c_i are column vectors. In addition, N denotes the number of domains and for i≠j, H_ij is considered to be small in some sense. These systems, denoted as weakly connected, are solved using first-order iterative techniques initially developed by the authors for solving single-domain problems. The techniques are extended to solve multi-domain problems. Novel solution strategies are investigated and procedures are developed which are computationally efficient. Computation times are determined for the iterative procedures and for elimination techniques indicating the benefits of iterative techniques over direct methods for problems of this nature.     

Jobs and tool sequencing in an automated manufacturing environment

A practical approach is presented for determining the sequence of jobs and tools in the magazine that would be required to process the jobs in an automated manufacturing environment. Each job has to be completed before a given due date. The magazine has a limited capacity necessitating setups which increase the lead times, Processing jobs also requires an appropriate fixture. Setting up a fixture also contributes to the setup times. A heuristic procedure is developed which determines the above sequences while minimizing the total setup and processing times. The performance of the heuristic is checked against optimal solutions for small-size problems while bounds are obtained (based on statistical lower bounding procedures) on the optimal solution for large-size problems. Computational results are provided for 155 test problems.     

Iterated greedy algorithms to minimize the total family flow time for job-shop scheduling with job families and sequence-dependent set-ups

This study addresses a variant of job-shop scheduling in which jobs are grouped into job families, but they are processed individually. The problem can be found in various industrial systems, especially in reprocessing shops of remanufacturing systems. If the reprocessing shop is a job-shop type and has the component-matching requirements, it can be regarded as a job shop with job families since the components of a product constitute a job family. In particular, sequence-dependent set-ups in which set-up time depends on the job just completed and the next job to be processed are also considered. The objective is to minimize the total family flow time, i.e. the maximum among the completion times of the jobs within a job family. A mixed-integer programming model is developed and two iterated greedy algorithms with different local search methods are proposed. Computational experiments were conducted on modified benchmark instances and the results are reported.     

Minimizing makespan subject to minimum total absolute deviation of completion time on identical parallel machines

This study addresses the identical parallel machine scheduling problem with the objective of minimizing makespan subject to minimum total absolute deviation of job completion time (TADC). An optimization algorithm is first proposed to solve TADC on an identical parallel machine and an iterative procedure based on a polynomial binary integer programming model is then proposed to minimize makespan. Computational experiments show that the proposed algorithm is efficient. The worst case performance, which refers to the largest average execution for each scenario of the experiments, is 229.10 seconds for the problem with n=200, m=30 and p _j from a uniform [1, 100].     

Scheduling parallel batch processing machines with arbitrary job sizes and incompatible job families

Motivated by a bottleneck operation in an MLCC (multi-layer ceramic capacitor) production line, we study the scheduling problem of parallel batch processing machines in which a number of jobs can be processed simultaneously in a machine as a batch. Volumes of the jobs are different from each other and each job belongs to the family in which all jobs have the same processing time. In this situation, we analyse three kinds of problems whose performance measures are makespan, total completion time, and total weighted completion time, respectively. Since these problems are known to be NP-hard, we propose a number of heuristics and design genetic algorithms for the problems. Through some computational experiments, we evaluate the performances of the heuristic algorithms proposed, including the genetic algorithms for each of three problems.     

Fabrication and assembly scheduling in a two-machine flowshop

This paper considers a fabrication scheduling problem to minimize the makespan in a two-machine flowshop. Each job has a unique component and a common component to be processed on the first machine. On machine 1, the common components of the jobs are grouped into batches for processing with a setup cost incurred whenever a batch is formed. A job is ready for its assembly operation on the second machine if both its unique and common components are finished on machine 1. The problems with batch availability and item availability are known as NP-hard. In this paper, we give proofs for the strong NP-hardness of the two problems. The results suggest that it is very unlikely to develop polynomial- or pseudo-polynomial-time algorithm for finding exact solutions for the two problems.     

Some dominance properties for single-machine tardiness problems with sequence-dependent setup

Some dominance properties are proposed for the NP-hard problems of scheduling N jobs on a single machine with due dates, and sequence-dependent setup times. The algorithms based on Ragatz's branch and bound scheme with the dominance properties are developed to minimize the maximum tardiness or the total tardiness. Computational experiments demonstrate the effectiveness of the dominance rules.     

Minimising general setup costs in a two-stage production system

This paper addresses a problem arising in the coordination between two consecutive stages of a production system. Production is organised in batches of identical jobs. Each job is characterised by two distinct attributes, and all jobs sharing the same attributes are processed together as a single batch. Due to the structural and organisational characteristics of the production system, the two stages have to process the same batch sequence. When two consecutive batches with different attributes are processed, at least one stage must pay a setup, in order to reconfigure its own devices. Each stage incurs a setup cost that is a general non-decreasing function of the number of its own setups, and the problem consists of finding a batch sequence minimising the total setup costs of the production system. We present an original solution approach for the considered problem that is shown to be very effective using an extensive experimental campaign.