The cyclic separation scheduling problem

This paper deals with the problem of scheduling items (tasks, employees, equipment, etc.) over a finite time horizon so as to minimize total cost expenditures while maintaining a predefined separation between certain items. The problem is cyclic, because the same schedule will be repeated over several consecutive time periods of equal length. Thus, requirements are present to maintain the separation of items not only within the individual time periods considered, but also between items in adjoining periods. A special purpose branch-and-bound algorithm is developed to solve this scheduling problem by taking advantage of its cyclic nature. Computational results are given.     

Production and transport logistics scheduling with two transport mode choices

This paper considers a new class of scheduling problems arising in logistics systems in which two different transportation modes are available at the stage of product delivery. The mode with the shorter transportation time charges a higher cost. Each job ordered by the customer is first processed in the manufacturing facility and then transported to the customer. There is a due date for each job to arrive to the customer. Our approach integrates the machine scheduling problem in the manufacturing stage with the transportation mode selection problem in the delivery stage to achieve the global maximum benefit. In addition to studying the NP‐hard special case in which no tardy job is allowed, we consider in detail the problem when minimizing the sum of the total transportation cost and the total weighted tardiness cost is the objective. We provide a branch and bound algorithm with two different lower bounds. The effectiveness of the two lower bounds is discussed and compared. We also provide a mathematical model that is solvable by CPLEX. Computational results show that our branch and bound algorithm is more efficient than CPLEX. © 2005 Wiley Periodicals, Inc. Naval Research Logistics, 2005     

Multiple subset sum with inclusive assignment set restrictions

In a traditional multiple subset sum problem (MSSP), there is a given set of items and a given set of bins (or knapsacks) with identical capacities. The objective is to select a subset of the items and pack them into the bins such that the total weight of the selected items is maximized. However, in many applications of the MSSP, the bins have assignment restrictions. In this article, we study the subset sum problem with inclusive assignment set restrictions, in which the assignment set of one item (i.e., the set of bins that the item may be assigned to) must be either a subset or a superset of the assignment set of another item. We develop an efficient 0.6492‐approximation algorithm and test its effectiveness via computational experiments. We also develop a polynomial time approximation scheme for this problem. © 2011 Wiley Periodicals, Inc. Naval Research Logistics, 2011     

Minimizing the sum of absolute lateness in single-machine and multimachine scheduling

Kanet addressed the problem of scheduling n jobs on one machine so as to minimize the sum of absolute lateness under a restrictive assumption on their common due date. This article extends the results to the problem of scheduling n jobs on m parallel identical processors in order to minimize the sum of absolute lateness. Also, a heuristic algorithm for a more general version with no restriction on the common due date, for the problem of n-job single-machine scheduling is presented and its performance is reported.     

Single‐machine scheduling with deadlines to minimize the total weighted late work

We consider scheduling a set of jobs with deadlines to minimize the total weighted late work on a single machine, where the late work of a job is the amount of processing of the job that is scheduled after its due date and before its deadline. This is the first study on scheduling with the late work criterion under the deadline restriction. In this paper, we show that (i) the problem is unary NP‐hard even if all the jobs have a unit weight, (ii) the problem is binary NP‐hard and admits a pseudo‐polynomial‐time algorithm and a fully polynomial‐time approximation scheme if all the jobs have a common due date, and (iii) some special cases of the problem are polynomially solvable.     

The single and multi‐item transshipment problem with fixed transshipment costs

This article deals with supply chain systems in which lateral transshipments are allowed. For a system with two retailers facing stochastic demand, we relax the assumption of negligible fixed transshipment costs, thus, extending existing results for the single‐item case and introducing a new model with multiple items. The goal is to determine optimal transshipment and replenishment policies, such that the total centralized expected profit of both retailers is maximized. For the single‐item problem with fixed transshipment costs, we develop optimality conditions, analyze the expected profit function, and identify the optimal solution. We extend our analysis to multiple items with joint fixed transshipment costs, a problem that has not been investigated previously in the literature, and show how the optimality conditions may be extended for any number of items. Due to the complexity involved in solving these conditions, we suggest a simple heuristic based on the single‐item results. Finally, we conduct a numerical study that provides managerial insights on the solutions obtained in various settings and demonstrates that the suggested heuristic performs very well. © 2014 Wiley Periodicals, Inc. Naval Research Logistics, 61: 637–664, 2014     

Algorithms for the multi‐item multi‐vehicles dynamic lot sizing problem

We consider a two‐stage supply chain, in which multi‐items are shipped from a manufacturing facility or a central warehouse to a downstream retailer that faces deterministic external demand for each of the items over a finite planning horizon. The items are shipped through identical capacitated vehicles, each incurring a fixed cost per trip. In addition, there exist item‐dependent variable shipping costs and inventory holding costs at the retailer for items stored at the end of the period; these costs are constant over time. The sum of all costs must be minimized while satisfying the external demand without backlogging. In this paper we develop a search algorithm to solve the problem optimally. Our search algorithm, although exponential in the worst case, is very efficient empirically due to new properties of the optimal solution that we found, which allow us to restrict the number of solutions examined. Second, we perform a computational study that compares the empirical running time of our search methods to other available exact solution methods to the problem. Finally, we characterize the conditions under which each of the solution methods is likely to be faster than the others and suggest efficient heuristic solutions that we recommend using when the problem is large in all dimensions. © 2005 Wiley Periodicals, Inc. Naval Research Logistics, 2006.     

Open shop scheduling to minimize the number of late jobs

We develop polynomial algorithms for several cases of the NP-hard open shop scheduling problem of minimizing the number of late jobs by utilizing some recent results for the open shop makespan problem. For the two machine common due date problem, we assume that either the machines or the jobs are ordered. For the m machine common due date problem, we assume that one machine is maximal and impose a restriction on its load. © 1998 John Wiley & Sons, Inc. Naval Research Logistics 45: 525–532, 1998     

Single- and multiple-processor models for minimizing completion time variance

This article concerns the scheduling of n jobs around a common due date, so as to minimize the average total earliness plus total lateness of the jobs. Optimality conditions for the problem are developed, based on its equivalence to an easy scheduling problem. It seems that this problem inherently has a huge number of optimal solutions and an algorithm is developed to find many of them. The model is extended to allow for the availability of multiple parallel processors and an efficient algorithm is developed for that problem. In this more general case also, the algorithm permits great flexibility in finding an optimal schedule.     

Joint determination of optimum variable and attribute target means

This article considers the problem of joint control of attribute and variable quality characteristics of a given product. Items are acceptable if they meet the specifications for both types of quality characteristics at the same time. Otherwise, the items are sold as scrap at reduced prices. The objective is to determine simultaneously the target values for each characteristic so as to maximize the expected profit per item. Several item-by-item quality-inspection plans are formulated on the basis of various inspection strategies. These strategies are defined in terms of whether the inspection is to be carried out simultaneously for both characteristics, or sequentially, or whether inspection for one of the characteristics is to be ignored. All these plans are shown to differ in terms of their profitability. However, they all yield equivalent quality standards. A numerical example is provided to illustrate the application of these models.     

Resequencing with parallel queues to minimize the maximum number of items in the overflow area

This article treats an elementary optimization problem, where an inbound stream of successive items is to be resequenced with the help of multiple parallel queues in order to restore an intended target sequence. Whenever early items block the one item to be currently released into the target sequence, they are withdrawn from their queue and intermediately stored in an overflow area until their actual release is reached. We aim to minimize the maximum number of items simultaneously stored in the overflow area during the complete resequencing process. We met this problem in industry practice at a large German automobile producer, who has to resequence containers with car seats prior to the assembly process. We formalize the resulting resequencing problem and provide suited exact and heuristic solution algorithms. In our computational study, we also address managerial aspects such as how to properly avoid the negative effects of sequence alterations. © 2016 Wiley Periodicals, Inc. Naval Research Logistics 63: 401–415, 2016     

Single machine just‐in‐time scheduling problems with two competing agents

In scheduling problems with two competing agents, each one of the agents has his own set of jobs to be processed and his own objective function, and both share a common processor. In the single‐machine problem studied in this article, the goal is to find a joint schedule that minimizes the total deviation of the job completion times of the first agent from a common due‐date, subject to an upper bound on the maximum deviation of job completion times of the second agent. The problem is shown to be NP‐hard even for a nonrestrictive due‐date, and a pseudopolynomial dynamic program is introduced and tested numerically. For the case of a restrictive due‐date (a sufficiently small due‐date that may restrict the number of early jobs), a faster pseudopolynomial dynamic program is presented. We also study the multiagent case, which is proved to be strongly NP‐hard. A simple heuristic for this case is introduced, which is tested numerically against a lower bound, obtained by extending the dynamic programming algorithm. © 2013 Wiley Periodicals, Inc. Naval Research Logistics 61: 1–16, 2014     

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.     

The initial provisioning decision for insurance type items

Initial provisioning decisions (inventory stocking requirements) for low demand items often have to be made without much knowledge of what future demand rates will be. When the nature of an item is such that little demand for it is expected, the problem of whether to stock initially or risk not stocking the item is most critical. This report discusses this problem and presents decision procedures which can be used to handle this aspect of initial provisioning. The procedures relate an item's provisioning desirability to its provisioning characteristics, such as expected cost, expected resupply time, current information on its likely demand rate, and to an overall operating policy or criterion. The criterion function measures the total system degredation as a function of the events of having items out of stock when demand occurs. Several different policy functions are discussed and the provisioning decision rules which apply to each are presented. Demand rate information is handled through a Bayesian type approach. The decision rules presented in this report can be utilized to either determine stocking requirements within a budgetary constraint, or determine the relative stocking desirability on an item-by-item basis.     

Minimizing mean absolute deviation of completion times about a common due date

We consider a single machine scheduling problem in which the objective is to minimize the mean absolute deviation of job completion times about a common due date. We present an algorithm for determining multiple optimal schedules under restrictive assumptions about the due date, and an implicit enumeration procedure when the assumptions do not hold. We also establish the similarity of this problem to the two parallel machines mean flow time problem.     

Group testing procedures with quantitative features and incomplete identification

We present a group testing model for items characterized by marker random variables. An item is defined to be good (defective) if its marker is below (above) a given threshold. The items can be tested in groups; the goal is to obtain a prespecified number of good items by testing them in optimally sized groups. Besides this group size, the controller has to select a threshold value for the group marker sums, and the target number of groups which by the tests are classified to consist only of good items. These decision variables have to be chosen so as to minimize a cost function, which is a linear combination of the expected number of group tests and an expected penalty for missing the desired number of good items, subject to constraints on the probabilities of misclassifications. We treat two models of this kind: the first one is based on an infinite population size, whereas the second one deals with the case of a finite number of available items. All performance measures are derived in closed form; approximations are also given. Furthermore, we prove monotonicity properties of the components of the objective function and of the constraints. In several examples, we study (i) the dependence of the cost function on the decision variables and (ii) the dependence of the optimal values of the decision variables (group size, group marker threshold, and stopping rule for groups classified as clean) and of the target functionals (optimal expected number of tests, optimal expected penalty, and minimal expected cost) on the system parameters.© 2011 Wiley Periodicals, Inc. Naval Research Logistics, 2011     

Multiple common due dates

Common due date problems have been extensively discussed in the scheduling literature. Initially, these problems discussed finding a common due date for a set of jobs on a single machine. These single machine problems were later extended to finding the common due date on a set of parallel machines. This paper further extends the single machine problem to finding multiple common due dates on a single machine. For a basic and important class of penalty functions, we show that this problem is comparable to the parallel machine problem. © 2001 John Wiley & Sons, Inc. Naval Research Logistics 48: 293–298, 2001     

Stochastic scheduling subject to machine breakdowns: The preemptive‐repeat model with discounted reward and other criteria

We consider the problem of scheduling a set of jobs on a single machine subject to random breakdowns. We focus on the preemptive‐repeat model, which addresses the situation where, if a machine breaks down during the processing of a job, the work done on the job prior to the breakdown is lost and the job will have to be started from the beginning again when the machine resumes its work. We allow that (i) the uptimes and downtimes of the machine follow general probability distributions, (ii) the breakdown process of the machine depends upon the job being processed, (iii) the processing times of the jobs are random variables following arbitrary distributions, and (iv) after a breakdown, the processing time of a job may either remain a same but unknown amount, or be resampled according to its probability distribution. We first derive the optimal policy for a class of problems under the criterion to maximize the expected discounted reward earned from completing all jobs. The result is then applied to further obtain the optimal policies for other due date‐related criteria. We also discuss a method to compute the moments and probability distributions of job completion times by using their Laplace transforms, which can convert a general stochastic scheduling problem to its deterministic equivalent. The weighted squared flowtime problem and the maintenance checkup and repair problem are analyzed as applications. © 2004 Wiley Periodicals, Inc. Naval Research Logistics, 2004     

Spares stocking policies for repairable items with dependent repair times

This paper analyzes the problem of determining desirable spares inventory levels for repairable items with dependent repair times. The problem is important for repairable products such as aircraft engines which can have very large investment in spares inventory levels. While existing models can be used to determine optimal inventory spares levels when repair times are independent, the practical considerations of limited repair shop capacity and prioritized shop dispatching rules combine to make repair times not independent of one another. In this research a simulation model of a limited capacity repair facility with prioritized scheduling is used to explore a variety of heuristic approaches to the spares stocking decision. The heuristics are also compared with use of a model requiring independent repair times (even though that assumption is not valid here). The results show that even when repair time dependencies are present, the performance of a model which assumes independent repair times is quite good.     

Server scheduling on parallel dedicated machines with fixed job sequences

We consider server scheduling on parallel dedicated machines to minimize the makespan. Each job has a loading operation and a processing operation. The loading operation requires a server that serves all the jobs. Each machine has a given set of jobs to process, and the processing sequence is known and fixed. We design a polynomial‐time algorithm to solve the two‐machine case of the problem. When the number of machines is arbitrary, the problem becomes strongly NP‐hard even if all the jobs have the same processing length or all the loading operations require a unit time. We design two heuristic algorithms to treat the case where all the loading times are unit and analyze their performance.