Multiobjective flow-shop scheduling

Previous research on the scheduling of multimachine systems has generally focused on the optimization of individual performance measures. This article considers the sequencing of jobs through a multimachine flow shop, where the quality of the resulting schedule is evaluated according to the associated levels of two scheduling criteria, schedule makespan (C_max) and maximum job tardiness (T_max). We present constructive procedures that quantify the trade-off between C_max and T_max. The significance of this trade-off is that the optimal solution for any preference function involving only C_max and T_max must be contained among the set of efficient schedules that comprise the trade-off curve. For the special case of two-machine flow shops, we present an algorithm that identifies the exact set of efficient schedules. Heruistic procedures for approximating the efficient set are also provided for problems involving many jobs or larger flow shops. Computational results are reported for the procedures which indicate that both the number of efficient schedules and the error incurred by heuristically approximating the efficient set are quite small.     

Scheduling with earliest start and due date constraints

We consider the scheduling of n tasks on a single resource. Each task becomes available for processing at time a_i, must be completed by time b_i, and requires d_i time units for processing. The aim is to find a schedule that minimizes the elapsed time to complete all jobs. We present solution algorithms for this problem when job splitting is permitted and when job splitting is not permitted. Then we consider several scheduling situations which arise in practice where these models may apply.     

A logistics scheduling model: Inventory cost reduction by batching

Logistics scheduling refers to the problems where the decisions of job scheduling and transportation are integrated in a single framework. In this paper, we discuss a logistics scheduling model where the raw material is delivered to the shop in batches. By making the batching and scheduling decisions simultaneously, the total inventory and batch setup cost can be reduced. We study different models on this issue, present complexity analysis and optimal algorithms, and conduct computational experiments. Some managerial insights are observed. © 2005 Wiley Periodicals, Inc. Naval Research Logistics, 2005.     

An absolute approximation algorithm for scheduling unrelated machines

Non‐preemptive scheduling of n independent jobs on m unrelated machines so as to minimize the maximal job completion time is considered. A polynomial algorithm with the worst‐case absolute error of min{(1 ? 1/m)p_max, p} is presented, where p_max is the largest job processing time and p is the mth element from the non‐increasing list of job processing times. This is better than the earlier known best absolute error of p_max. The algorithm is based on the rounding of acyclic multiprocessor distributions. An O(nm²) algorithm for the construction of an acyclic multiprocessor distribution is also presented. © 2006 Wiley Periodicals, Inc. Naval Research Logistics, 2006     

A note on scheduling parallel machines subject to breakdown and repair

In this paper we consider n jobs and a number of machines in parallel. The machines are identical and subject to breakdown and repair. The number may therefore vary over time and is at time t equal to m(t). Preemptions are allowed. We consider three objectives, namely, the total completion time, ∑ C_j, the makespan C_max, and the maximum lateness L_max. We study the conditions on m(t) under which various rules minimize the objective functions under consideration. We analyze cases when the jobs have deadlines to meet and when the jobs are subject to precedence constraints. © 2003 Wiley Periodicals, Inc. Naval Research Logistics, 2004.     

Algorithms for the minimax transportation problem

In this paper, we consider a variant of the classical transportation problem as well as of the bottleneck transportation problem, which we call the minimax transportation problem. The problem considered is to determine a feasible flow x_ij from a set of origins I to a set of destinations J for which max_(i,j)εIxJ{c_ijx_ij} is minimum. In this paper, we develop a parametric algorithm and a primal-dual algorithm to solve this problem. The parametric algorithm solves a transportation problem with parametric upper bounds and the primal-dual algorithm solves a sequence of related maximum flow problems. The primal-dual algorithm is shown to be polynomially bounded. Numerical investigations with both the algorithms are described in detail. The primal-dual algorithm is found to be computationally superior to the parametric algorithm and it can solve problems up to 1000 origins, 1000 destinations and 10,000 arcs in less than 1 minute on a DEC 10 computer system. The optimum solution of the minimax transportation problem may be noninteger. We also suggest a polynomial algorithm to convert this solution into an integer optimum solution.     

Real-time task scheduling with overheads considered

n periodic tasks are to be processed by a single machine, where each task i has a maximum request rate or periodicity F_i, a processing time E_i, a deadline D_i, relative to each request of task i, a task-request interrupt overhead I_i, and a task-independent scheduling overhead S. Two scheduling strategies are considered for sequencing the execution of an arbitrary arrangement of task requests in time: the preemptive and the nonpreemptive earliest-deadline algorithms. Necessary and sufficient conditions are derived for establishing whether a given set of tasks can be scheduled by each scheduling strategy. The conditions are given in the form of limited simulations of a small number of well-defined task-request arrangements. If all simulations succeed, the schedule is feasible for the given set of tasks. If any simulation fails, the schedule is infeasible. While interrupt handling and scheduling overheads can be handled by such simulations, context switching overhead resulting from preemption cannot. A counterexample illustrates how the simulations fail to uncover unschedulable task sets when context switching overhead is considered.     

On scheduling a single machine to minimize a piecewise linear objective function: A compact MIP formulation

We study the scheduling situation in which a set of jobs subjected to release dates and deadlines are to be performed on a single machine. The objective is to minimize a piecewise linear objective function ∑_jF_j where F_j(C_j) corresponds to the cost of the completion of job j at time C_j. This class of function is very large and thus interesting both from a theoretical and practical point of view: It can be used to model total (weighted) completion time, total (weighted) tardiness, earliness and tardiness, etc. We introduce a new Mixed Integer Program (MIP) based on time interval decomposition. Our MIP is closely related to the well‐known time‐indexed MIP formulation but uses much less variables and constraints. Experiments on academic benchmarks as well as on real‐life industrial problems show that our generic MIP formulation is efficient. © 2009 Wiley Periodicals, Inc. Naval Research Logistics, 2009     

Instant transportation solutions

This paper presents direct noniterative methods for solving such known problems as shoploading and aggregate scheduling. There is given a simple optimal rule for the shop-loading problem which is quite surprising. The crucial point in solving this problem is what not to assign rather than what to assign. The development of those methods was possible since the discussed problems can be converted into a special transportation model where the given cost coefficients c_ij assume a form cij = ui + uj.     

Flowshop/no-idle or no-wait scheduling to minimize the sum of completion times

This paper deals with flowshop/sum of completion times scheduling problems, working under a “no-idle” or a “no-wait” constraint, the former prescribes for the machines to work continuously without idle intervals and the latter for the jobs to be processed continuously without waiting times between consecutive machines. Under either of the constraints the problem is unary NP-Complete for two machines. We prove some properties of the optimal schedule for n/2/F, no-idle/σC_i. For n/m/P, no-idle/σC_i, and n/m/P, no-wait/σC_i, with an increasing or decreasing series of dominating machines, we prove theorems that are the basis for polynomial bounded algorithms. All theorems are demonstrated numerically.     

Scheduling multiple products on parallel machines with setup costs

We consider a class of production scheduling models with m identical machines in parallel and k different product types. It takes a time p_i to produce one unit of product type i on any one of the machines. There is a demand stream for product type i consisting of n_i units with each unit having a given due date. Before a machine starts with the production of a batch of products of type i a setup cost c is incurred. We consider several different objective functions. Each one of the objective functions has three components, namely a total setup cost, a total earliness cost, and a total tardiness cost. In our class of problems we find a relatively large number of problems that can be solved either in polynomial time or in pseudo‐polynomial time. The polynomiality or pseudo‐polynomiality is achieved under certain special conditions that may be of practical interest; for example, a regularity pattern in the string of due dates combined with earliness and tardiness costs that are similar for different types of products. The class of models we consider includes as special cases discrete counterparts of a number of inventory models that have been considered in the literature before, e.g., Wagner and Whitin (Manage Sci 5 (1958), 89–96) and Zangwill (Oper Res 14 (1966), 486–507; Manage Sci 15 (1969), 506–527). © 2008 Wiley Periodicals, Inc. Naval Research Logistics, 2008     

Parallel machine scheduling: A probabilistic analysis

The minimum makespan of the general parallel machine scheduling problem with m machines and n jobs is studied. As for a number of other important combinatorial problems, the theory of empirical processes proves to be a very elegant and powerful tool for the probabilistic analysis of the solution value. It is used in this paper to derive a scheduling constant θ such that, for random processing times, the minimum makespan almost surely grows as θn when n goes to infinity. Moreover, a thorough probabilistic analysis is performed on the difference between the minimum makespan and θn. Explicit expressions for the scheduling constant are given for an arbitrary number of unrelated machines with identically distributed processing times (with an increasing failure rate), and for an arbitrary number of uniform machines and generally distributed processing times. © 1996 John Wiley & Sons, Inc.     

Single-machine scheduling to minimize absolute deviation of completion times from a common due date

The article considers a single-machine n-job scheduling problem to minimize the sum of absolute lateness given a common due date. Two models are defined depending on whether the start time t₀ of schedules is arbitrary or fixed. Conditions are provided when those two models coincide. The developed branch-and-bound procedure is tested on nine known examples from the literature (6 ⩽ n ⩽ 14) and 90 medium-size random problems (15 ⩽ n ⩽ 25) with a fixed t₀.     

Scheduling data transmission under an {si; o} policy

This paper discusses scheduling of data transmission when data can only be transmitted in one direction at a time. A common policy used is the so-called alternating priority policy. In this paper we select a more general class of policies named the {S_i; O} policy. We show how to determine the optimal parameters of the {S_i; O} policy for given system parameters. We also give a simple example to show that {S_i; O} policy is, in fact, better then alternating priority policy.     

Solution of minisum and minimax location–allocation problems with Euclidean distances

A new method for the solution of minimax and minisum location–allocation problems with Euclidean distances is suggested. The method is based on providing differentiable approximations to the objective functions. Thus, if we would like to locate m service facilities with respect to n given demand points, we have to minimize a nonlinear unconstrained function in the 2m variables x₁,y₁, ?,x_m,y_m. This has been done very efficiently using a quasi-Newton method. Since both the original problems and their approximations are neither convex nor concave, the solutions attained may be only local minima. Quite surprisingly, for small problems of locating two or three service points, the global minimum was reached even when the initial position was far from the final result. In both the minisum and minimax cases, large problems of locating 10 service facilities among 100 demand points have been solved. The minima reached in these problems are only local, which is seen by having different solutions for different initial guesses. For practical purposes, one can take different initial positions and choose the final result with best values of the objective function. The likelihood of the best results obtained for these large problems to be close to the global minimum is discussed. We also discuss the possibility of extending the method to cases in which the costs are not necessarily proportional to the Euclidean distances but may be more general functions of the demand and service points coordinates. The method also can be extended easily to similar three-dimensional problems.     

Deterministic and stochastic scheduling with teamwork tasks

We study a class of new scheduling problems which involve types of teamwork tasks. Each teamwork task consists of several components, and requires a team of processors to complete, with each team member to process a particular component of the task. Once the processor completes its work on the task, it will be available immediately to work on the next task regardless of whether the other components of the last task have been completed or not. Thus, the processors in a team neither have to start, nor have to finish, at the same time as they process a task. A task is completed only when all of its components have been processed. The problem is to find an optimal schedule to process all tasks, under a given objective measure. We consider both deterministic and stochastic models. For the deterministic model, we find that the optimal schedule exhibits the pattern that all processors must adopt the same sequence to process the tasks, even under a general objective function GC = F(f₁(C₁), f₂(C₂), … , f_n(C_n)), where f_i(C_i) is a general, nondecreasing function of the completion time C_i of task i. We show that the optimal sequence to minimize the maximum cost MC = max f_i(C_i) can be derived by a simple rule if there exists an order f₁(t) ≤ … ≤ f_n(t) for all t between the functions {f_i(t)}. We further show that the optimal sequence to minimize the total cost TC = ∑ f_i(C_i) can be constructed by a dynamic programming algorithm. For the stochastic model, we study three optimization criteria: (A) almost sure minimization; (B) stochastic ordering; and (C) expected cost minimization. For criterion (A), we show that the results for the corresponding deterministic model can be easily generalized. However, stochastic problems with criteria (B) and (C) become quite difficult. Conditions under which the optimal solutions can be found for these two criteria are derived. © 2004 Wiley Periodicals, Inc. Naval Research Logistics, 2004     

Exploiting self‐canceling demand point aggregation error for some planar rectilinear median location problems

When solving location problems in practice it is quite common to aggregate demand points into centroids. Solving a location problem with aggregated demand data is computationally easier, but the aggregation process introduces error. We develop theory and algorithms for certain types of centroid aggregations for rectilinear 1‐median problems. The objective is to construct an aggregation that minimizes the maximum aggregation error. We focus on row‐column aggregations, and make use of aggregation results for 1‐median problems on the line to do aggregation for 1‐median problems in the plane. The aggregations developed for the 1‐median problem are then used to construct approximate n‐median problems. We test the theory computationally on n‐median problems (n ≥ 1) using both randomly generated, as well as real, data. Every error measure we consider can be well approximated by some power function in the number of aggregate demand points. Each such function exhibits decreasing returns to scale. © 2003 Wiley Periodicals, Inc. Naval Research Logistics 50: 614–637, 2003.     

Heuristics for multimachine minmax scheduling problems with general earliness and tardiness costs

We consider the problem of scheduling N jobs on M parallel machines so as to minimize the maximum earliness or tardiness cost incurred for each of the jobs. Earliness and tardiness costs are given by general (but job-independent) functions of the amount of time a job is completed prior to or after a common due date. We show that in problems with a nonrestrictive due date, the problem decomposes into two parts. Each of the M longest jobs is assigned to a different machine, and all other jobs are assigned to the machines so as to minimize their makespan. With these assignments, the individual scheduling problems for each of the machines are simple to solve. We demonstrate that several simple heuristics of low complexity, based on this characterization, are asymptotically optimal under mild probabilistic conditions. We develop attractive worst-case bounds for them. We also develop a simple closed-form lower bound for the minimum cost value. The bound is asymptotically accurate under the same probabilistic conditions. In the case where the due date is restrictive, the problem is more complex only in the sense that the set of initial jobs on the machines is not easily characterized. However, we extend our heuristics and lower bounds to this general case as well. Numerical studies exhibit that these heuristics perform excellently even for small- or moderate-size problems both in the restrictive and nonrestrictive due-date case. © 1997 John Wiley & Sons, Inc.     

Scheduling with earliest start and due date constraints on multiple machines

We consider the scheduling of n jobs on m identical machines when the jobs become available for processing at ready times a_i, a_i, ? 0, require d_i time units for processing and must be completed by times b_i for i = 1, 2, … n. The objective chosen is that of minimizing the total elapsed time to complete all jobs subject to the ready time and due date constraints, preemption is not allowed. We present a multi-stage solution algorithm for this problem that is based on an implicit enumeration procedure and also uses the labelling type algorithm which solves the problem when preemption is allowed.     

Parallel machine scheduling with eligibility constraints: A composite dispatching rule to minimize total weighted tardiness

We study a parallel machine scheduling problem, where a job j can only be processed on a specific subset of machines M_j, and the M_j subsets of the n jobs are nested. We develop a two‐phase heuristic for minimizing the total weighted tardiness subject to the machine eligibility constraints. In the first phase, we compute the factors and statistics that characterize a problem instance. In the second phase, we propose a new composite dispatching rule, the Apparent Tardiness Cost with Flexibility considerations (ATCF) rule, which is governed by several scaling parameters of which the values are determined by the factors obtained in the first phase. The ATCF rule is a generalization of the well‐known ATC rule which is very widely used in practice. We further discuss how to improve the dispatching rule using some simple but powerful properties without requiring additional computation time, and the improvement is quite satisfactory. We apply the Sequential Uniform Design Method to design our experiments and conduct an extensive computational study, and we perform tests on the performance of the ATCF rule using a real data set from a large hospital in China. We further compare its performance with that of the classical ATC rule. We also compare the schedules improved by the ATCF rule with what we believe are Near Optimal schedules generated by a general search procedure. The computational results show that especially with a low due date tightness, the ATCF rule performs significantly better than the well‐known ATC rule generating much improved schedules that are close to the Near Optimal schedules. © 2017 Wiley Periodicals, Inc. Naval Research Logistics 64: 249–267, 2017