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.     

Scheduling a Single Server in a Two-machine Flow Shop

We study the problem of scheduling a single server that processes n jobs in a two-machine flow shop environment. A machine dependent setup time is needed whenever the server switches from one machine to the other. The problem with a given job sequence is shown to be reducible to a single machine batching problem. This result enables several cases of the server scheduling problem to be solved in O(n log n) by known algorithms, namely, finding a schedule feasible with respect to a given set of deadlines, minimizing the maximum lateness and, if the job processing times are agreeable, minimizing the total completion time. Minimizing the total weighted completion time is shown to be NP-hard in the strong sense. Two pseudopolynomial dynamic programming algorithms are presented for minimizing the weighted number of late jobs. Minimizing the number of late jobs is proved to be NP-hard even if setup times are equal and there are two distinct due dates. This problem is solved in O(n ³) time when all job processing times on the first machine are equal, and it is solved in O(n ⁴) time when all processing times on the second machine are equal. Received November 20, 2001; revised October 18, 2002 Published online: January 16, 2003     

On scheduling a single machine with resource dependent release times

We consider a single machine scheduling problem with resource dependent release times that can be controlled by a non-increasing convex resource consumption function. The objective is to minimize the weighted total resource consumption and sum of job completion times with an initial release time greater than the total processing times. It is known that the problem is polynomially solvable in O(n⁴) with n the number of jobs.     

Approximation algorithms for minimizing the total weighted number of late jobs with late deliveries in two-level supply chains

We study a supply chain scheduling problem in which n jobs have to be scheduled on a single machine and delivered to m customers in batches. Each job has a due date, a processing time and a lateness penalty (weight). To save batch-delivery costs, several jobs for the same customer can be delivered together in a batch, including late jobs. The completion time of each job in the same batch coincides with the batch completion time. A batch setup time has to be added before processing the first job in each batch. The objective is to find a schedule which minimizes the sum of the weighted number of late jobs and the delivery costs. We present a pseudo-polynomial algorithm for a restricted case, where late jobs are delivered separately, and show that it becomes polynomial for the special cases when jobs have equal weights and equal delivery costs or equal processing times and equal setup times. We convert the algorithm into an FPTAS and prove that the solution produced by it is near-optimal for the original general problem by performing a parametric analysis of its performance ratio.     

Batching and scheduling in a multi-machine flow shop

We study the problem of batching and scheduling n jobs in a flow shop comprising m, m≥2, machines. Each job has to be processed on machines 1,…,m in this order. Batches are formed on each machine. A machine dependent setup time precedes the processing of each batch. Jobs of the same batch are processed on each machine 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 of the same batch formed on machine l become available for a downstream operation on machine l+1 at the same time when the processing of the last job of the batch on machine l has been finished. The objective is to minimize maximum job completion time. We establish several properties of an optimal schedule and develop polynomial time algorithms for important special cases. They are improvements over the existing methods with regard to their generality and time efficiency.     

Approximation algorithm for the weighted flow-time minimization on a single machine with a fixed non-availability interval

In this article, we consider the non-resumable case of the single machine scheduling problem with a fixed non-availability interval. We aim to minimize the weighted sum of completion times. No polynomial 2-approximation algorithm for this problem has been previously known. We propose a 2-approximation algorithm with O(n²) time complexity where n is the number of jobs. We show that this bound is tight. The obtained result outperforms all the previous polynomial approximation algorithms for this problem.     

Decomposition heuristics for minimizing earliness–tardiness on parallel burn-in ovens with a common due date

This paper considers a scheduling problem for parallel burn-in ovens in the semiconductor manufacturing industry. An oven is a batch processing machine with restricted capacity. The batch processing time is set by the longest processing time among those of all the jobs contained in the batch. All jobs are assumed to have the same due date. The objective is to minimize the sum of the absolute deviations of completion times from the due date (earliness–tardiness) of all jobs. We suggest three decomposition heuristics. The first heuristic applies the exact algorithm due to Emmons and Hall (for the nonbatching problem) in order to assign the jobs to separate early and tardy job sets for each of the parallel burn-in ovens. Then, we use job sequencing rules and dynamic programming in order to form batches for the early and tardy job sets and sequence them optimally. The second proposed heuristic is based on genetic algorithms. We use a genetic algorithm in order to assign jobs to each single burn-in oven. Then, after forming early and tardy job sets for each oven we apply again sequencing rules and dynamic programming techniques to the early and tardy jobs sets on each single machine in order to form batches. The third heuristic assigns jobs to the m early job sets and m tardy jobs sets in case of m burn-in ovens in parallel via a genetic algorithm and applies again dynamic programming and sequencing rules. We report on computational experiments based on generated test data and compare the results of the heuristics with known exact solution for small size test instances obtained from a branch and bound scheme.     

Completion time variance minimisation on two identical parallel processors

The problem of scheduling jobs to minimise completion time variance (CTV) is a well-known problem in scheduling research. CTV is categorized as a non-regular performance measure and its value may decrease by increasing the job completion times. This objective is relevant in situations where providing uniform service to customers is important, and is in-line with just-in-time philosophy. The problem concerned in this paper is to schedule n jobs on two identical parallel machines to minimise CTV. We consider the unrestricted version of the problem. The problem is said to be restricted when a machine is not allowed to remain idle when jobs are available for processing. It may be necessary to delay the start of job processing on a machine in order to reduce the completion time deviations. This gives rise to the unrestricted version of the problem. We discuss several properties of an optimal schedule to the problem. In this paper, we develop a lower bound on CTV for a known partial schedule and propose a branch and bound algorithm to solve the problem. Optimal solutions are obtained and results are reported.     

极小化加权完工时间和的无界批量机器并行调度问题

考虑无界批量机器并行调度中极小化加权完工时间和问题.设有n个工件和m台批加工同型机.每个工件具有一个正权因子、一个释放时间和一个加工时间.每台机器可以同时加工B≥n个工件.一个批次的加工时间是该批次所包含的所有工件的加工时间的最大者.在同一批次中加工的工件有相同的完工时间,即它们的共同开始时间加上该批次的加工时间.给出了一个多项式时间近似方案(PTAS).     

Minimizing the number of tardy jobs on a proportionate flowshop with general position-dependent processing times

In various real life scheduling systems job processing times vary according to the number of jobs previously processed. The vast majority of studies assume a restrictive functional form to describe job processing times. In this note, we address a scheduling problem with the most general job processing time functions. The machine setting assumed is an m-machine proportionate flowshop, and the objective function is minimum number of tardy jobs. We show that the problem can be formulated as a bottleneck assignment problem with a maximum cardinality constraint. An efficient polynomial time (O(n⁴ log n)) solution is introduced.     

Optimal on-line algorithms for the uniform machine scheduling problem with ordinal data

In this paper, we consider an ordinal on-line scheduling problem. A sequence of n independent jobs has to be assigned non-preemptively to two uniformly related machines. We study two objectives which are maximizing the minimum machine completion time, and minimizing the l_p norm of the completion times. It is assumed that the values of the processing times of jobs are unknown at the time of assignment. However it is known in advance that the processing times of arriving jobs are sorted in a non-increasing order. We are asked to construct an assignment of all jobs to the machines at time zero, by utilizing only ordinal data rather than actual magnitudes of jobs. For the problem of maximizing the minimum completion time we first present a comprehensive lower bound on the competitive ratio, which is a piecewise function of machine speed ratio s. Then, we propose an algorithm which is optimal for any s ⩾ 1. For minimizing the l_p norm, we study the case of identical machines (s = 1) and present tight bounds as a function of p.     

Minimizing the number of late jobs on a single machine under due date uncertainty

We study the problem of minimizing the number of late jobs on a single machine where job processing times are known precisely and due dates are uncertain. The uncertainty is captured through a set of scenarios. In this environment, an appropriate criterion to select a schedule is to find one with the best worst-case performance, which minimizes the maximum number of late jobs over all scenarios. For a variable number of scenarios and two distinct due dates over all scenarios, the problem is proved NP-hard in the strong sense and non-approximable in pseudo-polynomial time with approximation ratio less than 2. It is polynomially solvable if the number s of scenarios and the number v of distinct due dates over all scenarios are given constants. An O(nlog?n) time s-approximation algorithm is suggested for the general case, where n is the number of jobs, and a polynomial 3-approximation algorithm is suggested for the case of unit-time jobs and a constant number of scenarios. Furthermore, an O(n ^s+v?2/(v?1) ^v?2) time dynamic programming algorithm is presented for the case of unit-time jobs. The problem with unit-time jobs and the number of late jobs not exceeding a given constant value is solvable in polynomial time by an enumeration algorithm. The obtained results are related to a min-max assignment problem, an exact assignment problem and a multi-agent scheduling problem.     

The two-stage assembly scheduling problem to minimize total completion time with setup times

We address the two-stage assembly scheduling problem where there are m machines at the first stage and an assembly machine at the second stage. The objective is to schedule the available n jobs so that total completion time of all n jobs is minimized. Setup times are treated as separate from processing times. This problem is NP-hard, and therefore we present a dominance relation and propose three heuristics. The heuristics are evaluated based on randomly generated data. One of the proposed heuristics is known to be the best heuristic for the case of zero setup times while another heuristic is known to perform well for such problems. A new version of the latter heuristic, which utilizes the dominance relation, is proposed and shown to perform much better than the other two heuristics.     

Unbounded parallel-batching scheduling with two competitive agents

We consider the scheduling problems arising when two agents, each with a family of jobs, compete to perform their respective jobs on a common unbounded parallel-batching machine. The batching machine can process any number of jobs simultaneously in a batch. The processing time of a batch is equal to the maximum processing time of the jobs in the batch. Two main categories of batch processing based on the compatibility of job families or agents are distinguished. In the case where job families are incompatible, jobs from different families cannot be placed in the same processing batch while all jobs can be placed in the same processing batch when job families are compatible. The goal is to find a schedule for all jobs of the two agents that minimizes the objective of one agent while keeping the objective of the other agent below or at a fixed value Q. Polynomial-time and pseudo-polynomial-time algorithms are provided to solve various combinations of regular objective functions for the scenario in which job families are either incompatible or compatible.     

Size-reduction heuristics for the unrelated parallel machines scheduling problem

In this paper we study the unrelated parallel machines problem where n independent jobs must be assigned to one out of m parallel machines and the processing time of each job differs from machine to machine. We deal with the objective of the minimisation of the maximum completion time of the jobs, usually referred to as makespan or C_max. This is a type of assignment problem that has been frequently studied in the scientific literature due to its many potential applications. We propose a set of metaheuristics based on a size-reduction of the original assignment problem that produce solutions of very good quality in a short amount of time. The underlying idea is to consider only a few of the best possible machine assignments for the jobs and not all of them. The results are simple, yet powerful methods. We test the proposed algorithms with a large benchmark of instances and compare them with current state-of-the-art methods. In most cases, the proposed size-reduction algorithms produce results that are statistically proven to be better by a significant margin.     

An improved approximation algorithm for single machine scheduling with job delivery

In single machine scheduling with release times and job delivery, jobs are processed on a single machine and then delivered by a capacitated vehicle to a single customer. Only one vehicle is employed to deliver these jobs. The vehicle can deliver at most c jobs in a shipment. The delivery completion time of a job is defined as the time in which the delivery batch containing the job is delivered to the customer and the vehicle returns to the machine. The objective is to minimize the makespan, i.e., the maximum delivery completion time of the jobs. We provide an approximation algorithm for this problem which is better than that given in the literature, improving the performance ratio from 5/3 to 3/2.     

Scheduling problems with two competing agents to minimized weighted earliness–tardiness

We study scheduling problems with two competing agents, sharing the same machines. All the jobs of both agents have identical processing times and a common due date. Each agent needs to process a set of jobs, and has his own objective function. The objective of the first agent is total weighted earliness–tardiness, whereas the objective of the second agent is maximum weighted deviation from the common due date. Our goal is to minimize the objective of the first agent, subject to an upper bound on the objective value of the second agent. We consider a single machine, and parallel (both identical and uniform) machine settings. An optimal solution in all cases is shown to be obtained in polynomial time by solving a number of linear assignment problems. We show that the running times of the single and the parallel identical machine algorithms are O(n^m+3), where n is the number of jobs and m is the number of machines. The algorithm for solving the problem on parallel uniform machine requires O(n^m+3m³) time, and under very reasonable assumptions on the machine speeds, is reduced to O(n^m+3). Since the number of machines is given, these running times are polynomial in the number of jobs.     

Single-machine batch scheduling to minimize the total setup cost in the presence of deadlines

We address the single-machine batch scheduling problem with the objective of minimizing the total setup cost. This problem arises when there are n jobs that are partitioned into F families and when setup operations are required whenever the machine switches from processing a job of one family to processing a job of another family. We assume that setups do not require time but are associated with a fixed cost which is identical for all setup operations. Each job has a processing time and an associated deadline. The objective is to schedule all jobs such that they are on time with respect to their deadlines and the total setup cost is minimized. We show that the decision version of this problem is NP-complete in the strong sense. Furthermore, we present properties of optimal solutions and an \(O(n\log n+nF)\) algorithm that approximates the cost of an optimal schedule by a factor of F. The algorithm is analyzed in computational tests.     

Three scheduling problems with deteriorating jobs to minimize the total completion time

In this paper, three scheduling problems with deteriorating jobs to minimize the total completion time on a single machine are investigated. By a deteriorating job, we mean that the processing time of the job is a function of its execution start time. The three problems correspond to three different decreasing linear functions, whose increasing counterparts have been studied in the literature. Some basic properties of the three problems are proved. Based on these properties, two of the problems are solved in O(nlogn) time, where n is the number of jobs. A pseudopolynomial time algorithm is constructed to solve the third problem using dynamic programming. Finally, a comparison between the problems with job processing times being decreasing and increasing linear functions of their start times is presented, which shows that the decreasing and increasing linear models of job processing times seem to be closely related to each other.     

A polynomial-time algorithm for a flow-shop batching problem with equal-length operations

A flow-shop batching problem with consistent batches is considered in which the processing times of all jobs on each machine are equal to p and all batch set-up times are equal to s. In such a problem, one has to partition the set of jobs into batches and to schedule the batches on each machine. The processing time of a batch B _i is the sum of processing times of operations in B _i and the earliest start of B _i on a machine is the finishing time of B _i on the previous machine plus the set-up time s. Cheng et al. (Naval Research Logistics 47:128–144, 2000) provided an O(n) pseudopolynomial-time algorithm for solving the special case of the problem with two machines. Mosheiov and Oron (European Journal of Operational Research 161:285–291, 2005) developed an algorithm of the same time complexity for the general case with more than two machines. Ng and Kovalyov (Journal of Scheduling 10:353–364, 2007) improved the pseudopolynomial complexity to \(O(\sqrt{n})\). In this paper, we provide a polynomial-time algorithm of time complexity O(log?³ n).