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.     

A branch and bound algorithm for an identical parallel machine scheduling problem with a job splitting property

We focus on the problem of scheduling n independent jobs on m identical parallel machines with the objective of minimizing total tardiness of the jobs considering a job splitting property. In this problem, it is assumed that a job can be split into sub-jobs and these sub-jobs can be processed independently on parallel machines. We develop several dominance properties and lower bounds for the problem, and suggest a branch and bound algorithm using them. Computational experiments are performed on randomly generated test problems and results show that the suggested algorithm solves problems of moderate sizes in a reasonable amount of computation time.     

Preemptive scheduling on uniformly related machines: minimizing the sum of the largest pair of job completion times

We revisit the classic problem of preemptive scheduling on m uniformly related machines. In this problem, jobs can be arbitrarily split into parts, under the constraint that every job is processed completely, and that the parts of a job are not assigned to run in parallel on different machines. We study a new objective which is motivated by fairness, where the goal is to minimize the sum of the two maximal job completion times. We design a polynomial time algorithm for computing an optimal solution. The algorithm can act on any set of machine speeds and any set of input jobs. The algorithm has several cases, many of which are very different from algorithms for makespan minimization (algorithms that minimize the maximum completion time of any job), and from algorithms that minimize the total completion time of all jobs.     

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.     

A dominant class of schedules for malleable jobs in the problem to minimize the total weighted completion time

This paper is about scheduling parallel jobs, i.e. which can be executed on more than one machine at the same time. Malleable jobs is a special class of parallel jobs. The number of machines a malleable job is executed on may change during its execution.In this work, we consider the NP-hard problem of scheduling malleable jobs to minimize the total weighted completion time (or mean weighted flow time). For this problem, we introduce the class of “ascending” schedules in which, for each job, the number of machines assigned to it cannot decrease over time while this job is being processed.We prove that, under a natural assumption on the processing time functions of jobs, the set of ascending schedules is dominant for the problem. This result can be used to reduce the search space while looking for an optimal solution.     

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.     

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.     

Scheduling on parallel machines with preemption and transportation delays

This paper deals with an identical parallel machines scheduling problem, where independent jobs can be preempted and transported from one machine to another. The transportation of a preempted job requires a time called the transportation delay. The goal is to find a solution that minimizes the total completion time (makespan). We first study the case of equal-size jobs where new complexity results are given. Then, to solve the problem with two identical machines, we present a dynamic programming algorithm and a fully polynomial time approximation scheme (FPTAS). Experimental results show the efficiency of the FPTAS compared to a previously published heuristic.     

Scheduling job classes on uniform machines

We study a scheduling problem with job classes on parallel uniform machines. All the jobs of a given class share a common due-date. General, non-decreasing and class-dependent earliness and tardiness cost functions are assumed. Two objectives are considered: (i) minmax, where the scheduler is required to minimize the maximum earliness/tardiness cost among all the jobs and (ii) minmax-minsum, where the scheduler minimizes the sum of the maximum earliness/tardiness cost in all job classes. The problem is easily shown to be NP-hard, and we focus here on the introduction of simple heuristics. We introduce LPT (Largest Processing Time first)-based heuristics for the allocation of jobs to machines within each class, followed by a solution of an appropriate non-linear program, which produces for this job allocation an optimal schedule of the classes. We also propose a lower bound, based on balancing the load on the machines. Our numerical tests indicate that the heuristics result in very small optimality gaps.     

Scheduling of parallel machines to minimize total completion time subject to s-precedence constraints

This paper considers a deterministic scheduling problem where multiple jobs with s-precedence relations are processed on multiple identical parallel machines. The objective is to minimize the total completion time. The s-precedence relation between two jobs i and j represents the situation where job j is constrained from processing until job i starts processing, which is different from the standard definition of a precedence relation where j cannot start until i completes. The s-precedence relation has wide applicability in the real world such as first-come-first-served processing systems.     

On-line scheduling mesh jobs with dependencies

We study an on-line problem of scheduling parallel jobs on two-dimensional meshes. Parallel jobs arrive dynamically according to the dependencies between them, which are unknown before the jobs appear. Each job may need more than one processor simultaneously and is required to be scheduled on a submesh of the processors which are located on a two-dimensional mesh, i.e., a job must be scheduled on a rectangle of given dimensions. The objective is to minimize the maximum completion time (makespan). We deal with a UET job system, in which all job processing times are equal. We show a lower bound of 3.859 and present a 5.25-competitive algorithm. It significantly improves a previous lower bound of 3.25 and a previous upper bound of 46/7. We consider also the rotated two-dimensional mesh, in which the parallel jobs can be rotated and the rotation of all the jobs is feasible. A lower bound of 3.535 is proven and an on-line algorithm with competitive ratio of at most 4.25 is derived.     

Scheduling parallel jobs to minimize the makespan

We consider the NP-hard problem of scheduling parallel jobs with release dates on identical parallel machines to minimize the makespan. A parallel job requires simultaneously a prespecified, job-dependent number of machines when being processed. We prove that the makespan of any nonpreemptive list-schedule is within a factor of 2 of the optimal preemptive makespan. This gives the best-known approximation algorithms for both the preemptive and the nonpreemptive variant of the problem. We also show that no list-scheduling algorithm can achieve a better performance guarantee than 2 for the nonpreemptive problem, no matter which priority list is chosen. List-scheduling also works in the online setting where jobs arrive over time and the length of a job becomes known only when it completes; it therefore yields a deterministic online algorithm with competitive ratio 2 as well. In addition, we consider a different online model in which jobs arrive one by one and need to be scheduled before the next job becomes known. We show that no list-scheduling algorithm has a constant competitive ratio. Still, we present the first online algorithm for scheduling parallel jobs with a constant competitive ratio in this context. We also prove a new information-theoretic lower bound of 2.25 for the competitive ratio of any deterministic online algorithm for this model. Moreover, we show that 6/5 is a lower bound for the competitive ratio of any deterministic online algorithm of the preemptive version of the model jobs arriving over time.     

On the complexity of interval scheduling with a resource constraint

We consider a scheduling problem where jobs have to be carried out by parallel identical machines. The attributes of a job j are: a fixed start time s_j, a fixed finish time f_j, and a resource requirement r_j. Every machine owns R units of a renewable resource necessary to carry out jobs. A machine can process more than one job at a time, provided the resource consumption does not exceed R. The jobs must be processed in a non-preemptive way. Within this setting, the problem is to decide whether a feasible schedule for all jobs exists or not.We discuss such a decision problem and prove that it is strongly NP-complete even when the number of resources are fixed to any value R≥2. Moreover, we suggest an implicit enumeration algorithm which has O(nlogn) time complexity in the number n of jobs when the number m of machines and the number R of resources per machine are fixed.The role of storage layout and preemption are also discussed.     

Improving responsiveness of soft aperiodic tasks using proportional slack time

In a real-time system with both hard real-time periodic jobs and soft real-time aperiodic jobs, it is important to guarantee that the deadline of each periodic job is met, as well as to provide a fast response time for each aperiodic job. We propose an algorithm, called Proportional Slack Reserve (PSR), that produces an efficient schedule for such an environment. For every execution unit of a periodic job, the PSR algorithm reserves time which can be used for execution of aperiodic jobs. If reserved time is not available, the algorithm assigns a deadline to an aperiodic job for achieving better responsiveness of aperiodic jobs. The proposed algorithm can fully utilize processing power while meeting all deadlines of periodic jobs. It can also easily reclaim the time unused by the periodic job. We analytically show that for each aperiodic job, the response time in a PSR schedule is no longer than that in a TBS schedule, which is known to be efficient for servicing aperiodic jobs. We also present simulation results in which the response time of PSR is significantly improved over that of TBS, and moreover the performance of PSR compares favorably with TB(N) considering scheduling overhead.     

Scheduling nonpreemptive jobs on parallel machines subject to exponential unrecoverable interruptions

In this paper we consider the problem of scheduling n independent jobs on m parallel machines. If, while a machine is processing a job, a failure (unrecoverable interruption) occurs, the current job as well as subsequently scheduled jobs on that machine cannot be performed, and hence do not contribute to the overall revenue or throughput. The objective is to maximize the expected amount of work done before an interruption occurs. In this paper, we investigate the problem when failures are exponentially distributed. We show that the problem is NP-hard, and characterize a polynomially solvable special case. We then propose both an exact algorithm having pseudopolynomial complexity and a heuristic algorithm. A combinatorial upper bound is also proposed for the problem. Experimental results show the effectiveness of the heuristic approach.     

On-line machine covering on two machines with local migration

We study an on-line machine covering problem, in which jobs arrive one by one and their processing times are known upon their arrival, and jobs are allowed to migrate between machines when a new job is added in the system. However, the total processing time of migration induced by an incoming job is bounded by a constant factor β times the processing time of the incoming job. The objective is to maximize the minimum machine load. In this paper, we present an on-line algorithm with competitive ratio 6/5 for the two identical machines case with β=1. Moreover, the presented on-line algorithm is only a local migration, that is, when one job is assigned to machine i, only the jobs on machine i are allowed to migrate. We also show that the provided algorithm is a best possible on-line algorithm in the sense of local migration.     

On single-walk parallelization of the job shop problem solving algorithms

New parallel objective function determination methods for the job shop scheduling problem are proposed in this paper, considering makespan and the sum of jobs execution times criteria, however, the methods proposed can be applied also to another popular objective functions such as jobs tardiness or flow time. Parallel Random Access Machine (PRAM) model is applied for the theoretical analysis of algorithm efficiency. The methods need a fine-grained parallelization, therefore the approach proposed is especially devoted to parallel computing systems with fast shared memory (e.g. GPGPU, General-Purpose computing on Graphics Processing Units).     

Equilibria for two parallel links: the strong price of anarchy versus the price of anarchy

We consider a job scheduling game with two uniformly related parallel machines (or links). Jobs are atomic players, and the delay of a job is the completion time of the machine running it. The private goal of each job is to minimize its own delay and the social goal is to minimize the maximum delay of any job, that is, to minimize the makespan. We consider the well known price of anarchy as well as the strong price of anarchy, and show that for a wide range of speed ratios these two measures are very different whereas for other speed ratios these two measures give the exact same bound. We extend all our results for models of restricted assignment, where a machine may have an initial load resulting from jobs that can only be assigned to this machine, and show tight results for all variants.     

Machine scheduling with job class setup and delivery considerations

We study machine scheduling problems in which the jobs belong to different job classes and they need to be delivered to customers after processing. A setup time is required for a job if it is the first job to be processed on a machine or its processing on a machine follows a job that belongs to another class. Processed jobs are delivered in batches to their respective customers. The batch size is limited by the capacity of the delivery vehicles and each shipment incurs a transport cost and takes a fixed amount of time. The objective is to minimize the weighted sum of the last arrival time of jobs to customers and the delivery (transportation) cost. For the problem of processing jobs on a single machine and delivering them to multiple customers, we develop a dynamic programming algorithm to solve the problem optimally. For the problem of processing jobs on parallel machines and delivering them to a single customer, we propose a heuristic and analyze its performance bound.     

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.