Approximation schemes for parallel machine scheduling with availability constraints

We investigate the problems of scheduling n weighted jobs to m parallel machines with availability constraints. We consider two different models of availability constraints: the preventive model, in which the unavailability is due to preventive machine maintenance, and the fixed job model, in which the unavailability is due to a priori assignment of some of the n jobs to certain machines at certain times. Both models have applications such as turnaround scheduling or overlay computing. In both models, the objective is to minimize the total weighted completion time. We assume that m is a constant, and that the jobs are non-resumable.For the preventive model, it has been shown that there is no approximation algorithm if all machines have unavailable intervals even if w_i=p_i for all jobs. In this paper, we assume that there is one machine that is permanently available and that the processing time of each job is equal to its weight for all jobs. We develop the first polynomial-time approximation scheme (PTAS) when there is a constant number of unavailable intervals. One main feature of our algorithm is that the classification of large and small jobs is with respect to each individual interval, and thus not fixed. This classification allows us (1) to enumerate the assignments of large jobs efficiently; and (2) to move small jobs around without increasing the objective value too much, and thus derive our PTAS. Next, we show that there is no fully polynomial-time approximation scheme (FPTAS) in this case unless P=NP.For the fixed job model, it has been shown that if job weights are arbitrary then there is no constant approximation for a single machine with 2 fixed jobs or for two machines with one fixed job on each machine, unless P=NP. In this paper, we assume that the weight of a job is the same as its processing time for all jobs. We show that the PTAS for the preventive model can be extended to solve this problem when the number of fixed jobs and the number of machines are both constants.     

Due-window assignment with identical jobs on parallel uniform machines

A scheduling problem with a common due-window, earliness and tardiness costs, and identical processing time jobs is studied. We focus on the setting of both (i) job-dependent earliness/tardiness job weights and (ii) parallel uniform machines. The objective is to find the job allocation to the machines and the job schedule, such that the total weighted earliness and tardiness cost is minimized. We study both cases of a non-restrictive (i.e. sufficiently late), and a restrictive due-window. For a given number of machines, the solutions of the problems studied here are obtained in polynomial time in the number of jobs.     

Two machine preemptive scheduling problem with release dates,equal processing times and precedence constraints

We consider a scheduling problem with two identical parallel machines and n jobs. For each job we are given its release date when job becomes available for processing. All jobs have equal processing times. Preemptions are allowed. There are precedence constraints between jobs which are given by a (di)graph consisting of a set of outtrees and a number of isolated vertices. The objective is to find a schedule minimizing mean flow time. We suggest an O(n²) algorithm to solve this problem.The suggested algorithm also can be used to solve the related two-machine open shop problem with integer release dates, unit processing times and analogous precedence constraints.     

Scheduling jobs with release dates,equal processing times,and inclusive processing set restrictions

We consider the problem of scheduling a given set of n jobs with equal processing times on m parallel machines so as to minimize the makespan. Each job has a given release date and is compatible to only a subset of the machines. The machines are ordered and indexed in such a way that a higher-indexed machine can process all the jobs that a lower-indexed machine can process. We present a solution procedure to solve this problem in O(n²+mnlogn) time. We also extend our results to the tree-hierarchical processing sets case and the uniform machine case.     

A polynomial algorithm for a two-machine no-wait job-shop scheduling problem

This paper considers the no-wait scheduling of n jobs, where each job is a chain of unit processing time operations to be processed alternately on two machines. The objective is to minimize the mean flow time. We propose an O(n⁶)-time algorithm to produce an optimal schedule. It is also shown that if zero processing time operations are allowed, then the problem is NP-hard in the strong sense.     

Multi-family scheduling in a two-machine reentrant flow shop with setups

This paper considers a two-machine multi-family scheduling problem with reentrant production flows. The problem consists of two machines, M₁ and M₂, and each job has the processing route (M₁, M₂, M₁, M₂). There are identical jobs in the same family and the jobs in the same family are processed in succession. Each machine needs a setup time before the first job in a family is processed. The objective is to minimize the maximum completion time. Examples of such a problem occur in the bridge construction, semiconductor industry and job processing on numerical controlled machines, where they usually require that the jobs are reprocessed once and there are identical jobs in the same family. This problem is shown to be NP-hard. A branch-and-bound algorithm is proposed, and computational experiments are provided.     

A graph-oriented approach for the minimization of the number of late jobs for the parallel machines scheduling problem

An O(n²) algorithm is presented for the n jobs m parallel machines problem with identical processing times. Due dates for each job are given and the objective is the minimization of the number of late jobs. Preemption is permitted. The problem can be formulated as a maximum flow network model. The optimality proof as well as other properties and a complete example are given.     

The just-in-time scheduling problem in a flow-shop scheduling system

We study the problem of maximizing the weighted number of just-in-time (JIT) jobs in a flow-shop scheduling system under four different scenarios. The first scenario is where the flow-shop includes only two machines and all the jobs have the same gain for being completed JIT. For this scenario, we provide an O(n³) time optimization algorithm which is faster than the best known algorithm in the literature. The second scenario is where the job processing times are machine-independent. For this scenario, the scheduling system is commonly referred to as a proportionate flow-shop. We show that in this case, the problem of maximizing the weighted number of JIT jobs is NP-hard in the ordinary sense for any arbitrary number of machines. Moreover, we provide a fully polynomial time approximation scheme (FPTAS) for its solution and a polynomial time algorithm to solve the special case for which all the jobs have the same gain for being completed JIT. The third scenario is where a set of identical jobs is to be produced for different customers. For this scenario, we provide an O(n³) time optimization algorithm which is independent of the number of machines. We also show that the time complexity can be reduced to O(n log n) if all the jobs have the same gain for being completed JIT. In the last scenario, we study the JIT scheduling problem on m machines with a no-wait restriction and provide an O(mn²) time optimization algorithm.     

Preemptive scheduling of equal length jobs with release dates on two uniform parallel machines

We consider a problem of scheduling n jobs on two uniform parallel machines. For each job we are given its release date when the job becomes available for processing. All jobs have equal processing requirements. Preemptions are allowed. The objective is to find a schedule minimizing total completion time. We suggest an O(n³) algorithm to solve this problem.     

A note on parallel-machine due-window assignment

We consider a due-window assignment problem on identical parallel machines, where the jobs have equal processing times and job-dependent earliness-tardiness costs. We would like to determine a ‘due window’ during which the jobs can be completed at no cost and to obtain a job schedule in which the jobs are penalized if they finish before or after the due window. The objective is to minimize the total earliness and tardiness job penalty, plus the cost associated with the size of the due window. We present an algorithm that can solve this problem in O(n³) time, which is an improvement of the O(n⁴) solution procedure developed by Mosheiov and Sarig.     

Scheduling with controllable release dates and processing times: Total completion time minimization

The single machine scheduling problem with two types of controllable parameters, job processing times and release dates, is studied. It is assumed that the cost of compressing processing times and release dates from their initial values is a linear function of the compression amounts. The objective is to minimize the sum of the total completion time of the jobs and the total compression cost. For the problem with equal release date compression costs we construct a reduction to the assignment problem. We demonstrate that if in addition the jobs have equal processing time compression costs, then it can be solved in O(n²) time. The solution algorithm can be considered as a generalization of the algorithm that minimizes the makespan and total compression cost. The generalized version of the algorithm is also applicable to the problem with parallel machines and to a range of due-date scheduling problems with controllable processing times.     

Flowshop scheduling problem to minimize total completion time with random and bounded processing times

The flowshop scheduling problems with n jobs processed on two or three machines, and with two jobs processed on k machines are addressed where jobs have random and bounded processing times. The probability distributions of random processing times are unknown, and only the lower and upper bounds of processing times are given before scheduling. In such cases, there may not exist a unique schedule that remains optimal for all feasible realizations of the processing times, and therefore, a set of schedules has to be considered which dominates all other schedules for the given criterion. We obtain sufficient conditions when transposition of two jobs minimizes total completion time for the cases of two and three machines. The geometrical approach is utilized for flowshop problem with two jobs and k machines.     

Asymptotical optimality of WSEPT for stochastic online scheduling on uniform machines

We study the stochastic online scheduling on m uniform machines with the objective to minimize the expected value of total weighted completion times of a set of jobs that arrive over time. For each job, the processing time is a random variable, and the distribution of processing time is unknown in advance. The actual processing time could be known only when the job is completed. For the problem, we propose a policy which is proved to be asymptotically optimal when the processing times and weights are uniformly bounded, i.e. the relative error of the solution achieved by our policy approaches zero as the number of jobs increases to infinity.     

An O(n) algorithm for the variable common due date,minimal tardy jobs bicriteria two-machine flow shop problem with ordered machines

We consider the ordinary NP- hard two-machine flow shop problem with the objective of determining simultaneously a minimal common due date and the minimal number of tardy jobs. We present an O(n²) algorithm for the problem when the machines are ordered, that is, when each job has its smaller processing time on the first (second) machine. We also discuss the applicability of the proposed algorithm to the corresponding single-objective problem in which the common due date is given.     

A note on the flow time and the number of tardy jobs in stochastic open shops

In this note open shops with two machines are considered. The processing time of job j, j = 1, …, n, on machine 1 (2) is a random variable X_j (Y_j), which is exponentially distributed with rate γ (μ). If the completion time of job j is C_j, a waiting cost is incurred of g(C_j), where g is a function that is increasing concave. The preemptive policy that minimizes the total expected waiting cost E(Σg(C_j)) is determined. Two machine open shops with jobs that have random due dates are considered as well. For the case where the due dates D₁,…,D_n are exchangeable, the preemptive policy that minimizes the expected number of tardy jobs is determined.     

A priority rule for minimizing weighted flow time in a class of parallel machine scheduling problems

The problem of scheduling n jobs with known process times on m identical parallel machines with an objective of minimizing weighted flow time is NP-hard. However, when job weights are identical, it is well known that the problem is easily solved using the shortest processing time rule. In this paper, we show that a generalization of the shortest processing time rule minimizes weighted flow time in a class of problems where job weights are not identical.     

Single-machine scheduling with deteriorating jobs and past-sequence-dependent setup times

In many realistic scheduling settings a job processed later consumes more time than the same job processed earlier – this is known as scheduling with deteriorating jobs. Most research on scheduling with deteriorating jobs assumes that the actual processing time of a job is an increasing function of its starting time. Thus a job processed late may incur an excessively long processing time. On the other hand, setup times occur in manufacturing situations where jobs are processed in batches whereby each batch incurs a setup time. This paper considers scheduling with deteriorating jobs in which the actual processing time of a job is a function of the logarithm of the total processing time of the jobs processed before it (to avoid the unrealistic situation where the jobs scheduled late will incur excessively long processing times) and the setup times are proportional to the actual processing times of the already scheduled jobs. Under the proposed model, we provide optimal solutions for some single-machine problems.     

On A Scheduling Problem of Time Deteriorating Jobs

We consider a scheduling problem with a single machine and a set of jobs which have to be processed sequentially. While waiting for processing, jobs may deteriorate, causing the processing requirement of each job to grow after a fixed waiting timet₀. We prove that the problem of minimizing the makespan—completion time for all jobs—is NP-hard. Next we consider the problem for a natural special case where the job requirement grows linearly at a job-specific rate aftert₀. We develop a fully polynomial time approximation scheme for the problem in this case. We also give further NP-hardness results, and a polynomial time algorithm for the case where the job-specific rate is proportional to the initial processing requirement of each job.     

Two meta-heuristics for parallel machine scheduling with job splitting to minimize total tardiness

Parallel machine scheduling is a popular research area due to its wide range of potential application areas. This paper focuses on the problem of scheduling n independent jobs to be processed on m identical parallel machines with the aim of minimizing the total tardiness of the jobs considering a job splitting property. It is assumed that a job can be split into sub-jobs and these sub-jobs can be processed independently on parallel machines. We present a mathematical model for this problem. The problem of total tardiness on identical parallel machines is NP-hard. Obtaining an optimal solution for this type of complex, large-sized problem in reasonable computational time by using an optimization solver is extremely difficult. We propose two meta-heuristics: Tabu search and simulated annealing. Computational results are compared on random generated problems with different sizes.     

A rank-based approach to the sequential selection and assignment problem

In the classical sequential assignment problem, “machines” are to be allocated sequentially to “jobs” so as to maximize the expected total return, where the return from an allocation of job j to machine k is the product of the value x_j of the job and the weight p_k of the machine. The set of m machines and their weights are given ahead of time, but n jobs arrive in sequential order and their values are usually treated as independent, identically distributed random variables from a known univariate probability distribution with known parameter values. In the paper, we consider a rank-based version of the sequential selection and assignment problem that minimizes the sum of weighted ranks of jobs and machines. The so-called “secretary problem” is shown to be a special case of our sequential assignment problem (i.e., m = 1). Due to its distribution-free property, our rank-based assignment strategy can be successfully applied to various managerial decision problems such as machine scheduling, job interview, kidney allocations for transplant, and emergency evacuation plan of patients in a mass-casualty situation.