Scheduling independent jobs for torus connected networks with/without link contention

In this paper, we investigate the problem of how to schedule n independent jobs on an m × m torus based network. We develop a model to to quantify the effect of contention for communication links on the dilation of job execution time when multiple jobs share communication links; we then design an efficient algorithm to schedule a set of n independent jobs with different torus size requirements on a given torus with an objective to minimize the total schedule length. We also develop a feasibility algorithm for pre-emptively scheduling a given set of jobs on a torus of given size with a given deadline. We provide analysis for both the algorithms.     

Complexity of the job insertion problem in multi-stage scheduling

The job insertion problem in multi-stage scheduling is: given a schedule for n jobs and an additional job, find a feasible insertion of the additional job into the schedule that minimizes the resulting makespan. We prove that finding the optimal job insertion is NP-hard for flow shops and open shops.     

Scheduling jobs with release dates and tails on identical machines to minimize the makespan

This paper considers the problem of scheduling independent jobs with release dates and tails on m identical machines to minimize the makespan. This m-machines problem is NP-hard in the strong sense. Jackson's schedule is defined as the list schedule built by giving priority to the available job with the largest tail. It is proved that the deviation of Jackson's schedule from the optimum is smaller than twice the largest processing time.Next, a new branching scheme is proposed by associating with each job an interval of time during which it has to be processed. To branch, the interval for a particular job is divided into two smaller ones. This is a general scheme which can be applied to many scheduling problems.Finally, a branch and bound algorithm is explained in detail and computational results are given.     

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.     

A Bayesian approach to the triage problem with imperfect classification

A collection of jobs (or customers, or patients) wait impatiently for service. Each has a random lifetime during which it is available for service. Should this lifetime expire before its service starts then it leaves unserved. Limited resources mean that it is only possible to serve one job at a time. We wish to schedule the jobs for service to maximise the total number served. In support of this objective all jobs are subject to an initial triage, namely an assessment of both their urgency and of their service requirement. This assessment is subject to error. We take a Bayesian approach to the uncertainty generated by error prone triage and discuss the design of heuristic policies for scheduling jobs for service to maximise the Bayes’ return (mean number of jobs served). We identify problem features for which a high price is paid in number of services lost for poor initial triage and for which improvements in initial job assessment yield significant improvements in service outcomes. An analytical upper bound for the cost of imperfect classification is developed for exponentially distributed lifetime cases.     

Flow shop scheduling algorithms for minimizing the completion time variance and the sum of squares of completion time deviations from a common due date

We consider two problems of m-machine flow shop scheduling in this paper: one, with the objective of minimizing the variance of completion times of jobs, and the other with the objective of minimizing the sum of squares of deviations of job completion times from a common due date. Lower bounds on the sum of squares of deviations of job completion times from the mean completion time of jobs for a given partial sequence are first presented. Using these lower bounds, a branch and bound algorithm based on breadth-first search procedure for scheduling n jobs on m-machines with the objective of minimizing completion time variance (CTV) is developed to obtain the best permutation sequence. We also present two lower bounds and thereafter, a branch and bound algorithm with the objective of minimizing the sum of squares of deviations of job completion times from a given common due date (called the MSD problem). The computational experience with the working of the two proposed branch and bound algorithms is also reported. Two heuristics, one for each of the two problems, are developed. The computational experience on the evaluation of the heuristics is discussed.     

Soft due window assignment and scheduling of unit-time jobs on parallel machines

We study problems of scheduling n unit-time jobs on m identical parallel machines, in which a common due window has to be assigned to all jobs. If a job is completed within the due window, then no scheduling cost incurs. Otherwise, a job-dependent earliness or tardiness cost incurs. The job completion times, the due window location and the size are integer valued decision variables. The objective is to find a job schedule as well as the location and the size of the due window such that a weighted sum or maximum of costs associated with job earliness, job tardiness and due window location and size is minimized. We establish properties of optimal solutions of these min-sum and min-max problems and reduce them to min-sum (traditional) or min-max (bottleneck) assignment problems solvable in O(n ⁵/m ²) and O(n ^4.5log^0.5 n/m ²) time, respectively. More efficient solution procedures are given for the case in which the due window size cost does not exceed the due window start time cost, the single machine case, the case of proportional earliness and tardiness costs and the case of equal earliness and tardiness costs.     

Preemptive scheduling of two uniform parallel machines to minimize total tardiness

We consider the problem of preemptive scheduling n jobs on two uniform parallel machines. All jobs have equal processing requirements. For each job we are given its due date. The objective is to find a schedule minimizing total tardiness ∑T_i. We suggest an O(n log n) algorithm to solve this problem.     

A branch and bound algorithm for the two-stage assembly scheduling problem

This paper develops a branch and bound algorithm for the two-stage assembly scheduling problem. In this problem, there are m machines at the first stage, each of which produces a component of a job. When all m components are available, a single assembly machine at the second stage completes the job. The objective is to schedule the jobs on the machines so that the maximum completion time, or makespan, is minimized. A lower bound based on solving an artificial two-machine flow shop problem is derived. Also, several dominance theorems are established and incorporated into the branch and bound algorithm. Computational experience with the algorithm is reported for problems with up to 8000 jobs and 10 first-stage machines.     

Parallel machine scheduling with machine availability and eligibility constraints

In this paper we consider the problem of scheduling n independent jobs on m identical machines incorporating machine availability and eligibility constraints while minimizing the makespan. Each machine is not continuously available at all times and each job can only be processed on specified machines. A network flow approach is used to formulate this scheduling problem into a series of maximum flow problems. We propose a polynomial time binary search algorithm to either verify the infeasibility of the problem or solve it optimally if a feasible schedule exists.     

Simultaneous Job Scheduling and Resource Allocation on Parallel Machines

Most deterministic production scheduling models assume that the processing time of a job on a machine is fixed externally and known in advance of scheduling. However, in most realistic situations, apart from the machines, it requires additional resources to process jobs, and the processing time of a job is determined internally by the amount of the resources allocated. In these situations, both the cost associated with the job schedule and the cost of the resources allocated should be taken into account. Therefore, job scheduling and resource allocation should be carefully coordinated and optimized jointly in order to achieve an overall cost-effective schedule. In this paper, we study a parallel-machine scheduling model involving both job processing and resource allocation. The processing time of a job is non-increasing with the cost of the allocated resources. The objective is to minimize the total cost including the cost measured by a scheduling criterion and the cost of all allocated resources. We consider two particular problems of this model, one with the scheduling criterion being the total weighted completion time, and the other with that being the weighted number of tardy jobs. We develop a column generation based branch and bound method for finding optimal solutions for these NP-hard problems. The method first formulates the problems as set partitioning type formulations, and then solves the resulting formulations exactly by branch and bound. In the branch and bound, linear relaxations of the set partitioning type formulations are decomposed into master problems and single-machine subproblems and solved by a column generation approach. The algorithms developed based on this method are capable of solving the two problems with a medium size to optimality within a reasonable computational time.     

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.     

Maximization Problems in Single Machine Scheduling

Problems of scheduling n jobs on a single machine to maximize regular objective functions are studied. Precedence constraints may be given on the set of jobs and the jobs may have different release times. Schedules of interest are only those for which the jobs cannot be shifted to start earlier without changing job sequence or violating release times or precedence constraints. Solutions to the maximization problems provide an information about how poorly such schedules can perform. The most general problem of maximizing maximum cost is shown to be reducible to n similar problems of scheduling n?1 jobs available at the same time. It is solved in O(mn+n ²) time, where m is the number of arcs in the precedence graph. When all release times are equal to zero, the problem of maximizing the total weighted completion time or the weighted number of late jobs is equivalent to its minimization counterpart with precedence constraints reversed with respect to the original ones. If there are no precedence constraints, the problem of maximizing arbitrary regular function reduces to n similar problems of scheduling n?1 jobs available at the same time.     

Scheduling for fabrication and assembly in a two-machine flowshop with a fixed job sequence

This paper studies a problem of scheduling fabrication and assembly operations in a two-machine flowshop, subject to the same predetermined job sequence on each machine. In the manufacturing setting, there are n products, each of which consists of two components: a common component and a unique component which are fabricated on machine 1 and then assembled on machine 2. Common components of all products are processed in batches preceded by a constant setup time. The manufacturing process related to each single product is called a job. We address four regular performance measures: the total job completion time, the maximum job lateness, the total job tardiness, and the number of tardy jobs. Several optimality properties are presented. Based upon the concept of critical path and block schedule, a generic dynamic programming algorithm is developed to find an optimal schedule in O(n ⁷) time.     

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.     

Approximability of single machine scheduling with fixed jobs to minimize total completion time

We consider the single machine scheduling problem to minimize total completion time with fixed jobs, precedence constraints and release dates. There are some jobs that are already fixed in the schedule. The remaining jobs are free to be assigned to any free-time intervals on the machine in such a way that they do not overlap with the fixed jobs. Each free job has a release date, and the order of processing the free jobs is restricted by the given precedence constraints. The objective is to minimize the total completion time. This problem is strongly NP-hard. Approximability of this problem is studied in this paper. When the jobs are processed without preemption, we show that the problem has a linear-time n-approximation algorithm, but no pseudopolynomial-time (1 − δ)n-approximation algorithm exists even if all the release dates are zero, for any constant δ > 0, if P ≠ NP, where n is the number of jobs; for the case that the jobs have no precedence constraints and no release dates, we show that the problem has no pseudopolynomial-time (2 − δ)-approximation algorithm, for any constant δ > 0, if P ≠ NP, and for the weighted version, we show that the problem has no polynomial-time 2^q(n)-approximation algorithm and no pseudopolynomial-time q(n)-approximation algorithm, where q(n) is any given polynomial of n. When preemption is allowed, we show that the problem with independent jobs can be solved in O(n log n) time with distinct release dates, but the weighted version is strongly NP-hard even with no release dates; the problems with weighted independent jobs or with jobs under precedence constraints are shown having polynomial-time n-approximation algorithms. We also establish the relationship of the approximability between the fixed job scheduling problem and the bin-packing problem.     

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.     

Single machine group scheduling with resource dependent setup and processing times

A single machine scheduling problem is studied. There is a partition of the set of n jobs into g groups on the basis of group technology. Jobs of the same group are processed contiguously. A sequence independent setup time precedes the processing of each group. Two external renewable resources can be used to linearly compress setup and job processing times. The setup times are jointly compressible by one resource, the job processing times are jointly compressible by another resource and the level of the resource is the same for all setups and all jobs. Polynomial time algorithms are presented to find an optimal job sequence and resource values such that the total weighted resource consumption is minimum, subject to meeting job deadlines. The algorithms are based on solving linear programming problems with two variables by geometric techniques.     

Improved Bounds for Acyclic Job Shop Scheduling

In acyclic job shop scheduling problems there are n jobs and m machines. Each job is composed of a sequence of operations to be performed on different machines. A legal schedule is one in which within each job, operations are carried out in order, and each machine performs at most one operation in any unit of time. If D denotes the length of the longest job, and C denotes the number of time units requested by all jobs on the most loaded machine, then clearly lb = max[C,D] is a lower bound on the length of the shortest legal schedule. A celebrated result of Leighton, Maggs, and Rao shows that if all operations are of unit length, then there always is a legal schedule of length O(lb), independent of n and m. For the case that operations may have different lengths, Shmoys, Stein and Wein showed that there always is a legal schedule of length , where the notation is used to suppress terms. We improve the upper bound to . We also show that our new upper bound is essentially best possible, by proving the existence of instances of acyclic job shop scheduling for which the shortest legal schedule is of length . This resolves (negatively) a known open problem of whether the linear upper bound of Leighton, Maggs, and Rao applies to arbitrary job shop scheduling instances (without the restriction to acyclicity and unit length operations). Received June 30, 1998 RID="*" ID="*" Incumbent of the Joseph and Celia Reskin Career Development Chair RID="†" ID="†" Research was done while staying at the Weizmann Institute, supported by a scholarship from the Minerva foundation.