Two machine flow shop scheduling problems with sequence dependent setup times: A dynamic programming approach

This paper considers the two different flow shop scheduling problems that arise when, in a two machine problem, one machine is characterized by sequence dependent setup times. The objective is to determine a schedule that minimizes makespan. After establishing the optimally of permutation schedules for both of these problems, an efficient dynamic programming formulation is developed for each of them. Each of these formulations is shown to be comparable, from a computational standpoint, to the corresponding formulation of the traveling salesman problem. Then, the relative merits of the dynamic programming and branch and bound approaches to these two scheduling problems are discussed.     

Scheduling of depalletizing and truck loading operations in a food distribution system

This paper studies a scheduling problem arising in a beef distribution system where pallets of various types of beef products in the warehouse are first depalletized and then individual cases are loaded via conveyors to the trucks which deliver beef products to various customers. Given each customer's demand for each type of beef, the problem is to find a depalletizing and truck loading schedule that fills all the demands at a minimum total cost. We first show that the general problem where there are multiple trucks and each truck covers multiple customers is strongly NP‐hard. Then we propose polynomial‐time algorithms for the case where there are multiple trucks, each covering only one customer, and the case where there is only one truck covering multiple customers. We also develop an optimal dynamic programming algorithm and a heuristic for solving the general problem. By comparing to the optimal solutions generated by the dynamic programming algorithm, the heuristic is shown to be capable of generating near optimal solutions quickly. © 2003 Wiley Periodicals, Inc. Naval Research Logistics, 2003     

Scheduling target illuminators in naval battle-group anti-air warfare

We schedule a set of illuminators (homing devices) to strike a set of targets using surface-to-air missiles in a naval battle. The task is viewed as a production floor shop scheduling problem of minimizing the total weighted flow time, subject to time-window job availability and machine downtime side constraints. A simple algorithm based on solving assignment problems is developed for the case when all the job processing times are equal and the data are all integer. For the general case of scheduling jobs with unequal processing times, we develop two alternate formulations and analyze their relative strengths by comparing their respective linear programming relaxations. We select the better formulation in this comparison and exploit its special structures to develop several effective heuristic algorithms that provide good-quality solutions in real time; this is an essential element for use by the Navy. © 1995 John Wiley & Sons, Inc.     

Scheduling with centralized and decentralized batching policies in concurrent open shops

This article considers batch scheduling with centralized and decentralized decisions. The context of our study is concurrent open shop scheduling where the jobs are to be processed on a set of independent dedicated machines, which process designated operations of the jobs in batches. The batching policy across the machines can be centralized or decentralized. We study such scheduling problems with the objectives of minimizing the maximum lateness, weighted number of tardy jobs, and total weighted completion time, when the job sequence is determined in advance. We present polynomial time dynamic programming algorithms for some cases of these problems and pseudo‐polynomial time algorithms for some problems that are NP‐hard in the ordinary sense. © 2010 Wiley Periodicals, Inc. Naval Research Logistics 58: 17–27, 2011     

面向多最优解组合优化问题的决策求解算法

针对具有固定物品总和、多最优解特征的组合优化问题,以固定总和实数子集问题和购买鸡翅问题为例,给出了这类多最优解组合优化问题的形式化表示。在分析枚举等经典算法基础上,提出了基于整数状态表示和实数状态表示的0-1决策递归搜索多最优解动态规划算法。针对该算法在最优解数量较大时,时间复杂度趋向O(mⁿ)的问题,提出了基于相同决策路径合并和基于0-x决策的两种改进算法。实验中两种改进算法的计算时间基本符合与O(nb+nm)的正比关系,表明对于这类多最优解组合优化问题具有良好的求解性能。     

Demand shuffle—A method for multilevel proportional lot sizing and scheduling

This contribution acquaints the reader with a model for multilevel single-machine proportional lot sizing and scheduling problems (PLSPs) that appear in the scope of short-term production planning. It is one of the first articles that deals with dynamic capacitated multilevel lot sizing and scheduling, which is of great practical importance. The PLSP model refines well-known mixed-integer programming formulations for dynamic capacitated lot sizing and scheduling as, for instance, the DLSP or the CSLP. A special emphasis is given on a new method called demand shuffle to solve multilevel PLSP instances efficiently but suboptimally. Although the basic idea is very simple, it becomes clear that in the presence of precedence and capacity constraints many nontrivial details are to be concerned. Computational studies show that the presented approach decidedly improves recent results. © 1997 John Wiley & Sons, Inc. Naval Research Logistics 44: 319–340, 1997     

Scheduling semiconductor test operations: Minimizing maximum lateness and number of tardy jobs on a single machine

We examine a class of single-machine scheduling problems with sequence-dependent setup times that arise in the context of semiconductor test operations. We present heuristics for the problems of minimizing maximum lateness with dynamic arrivals and minimizing number of tardy jobs. We exploit special problem structure to derive worst-case error bounds. The special problem structure also enables us to derive dynamic programming procedures for the problems where all jobs are available simultaneously.     

Two‐machine flow shop scheduling with common due window to minimize weighted number of early and tardy jobs

This article studies two due window scheduling problems to minimize the weighted number of early and tardy jobs in a two‐machine flow shop, where the window size is externally determined. These new scheduling models have many practical applications in real life. However, results on these problems have rarely appeared in the literature because of a lack of structural and optimality properties for solving them. In this article, we derive several dominance properties and theorems, including elimination rules and sequencing rules based on Johnsos order, lower bounds on the penalty, and upper bounds on the window location, which help to significantly trim the search space for the problems. We further show that the problems are NP‐hard in the ordinary sense only. We finally develop efficient pseudopolynomial dynamic programming algorithms for solving the problems. © 2009 Wiley Periodicals, Inc. Naval Research Logistics, 2009     

Linear programming and the reliability of multicomponent systems

Several problems in the assignment of parallel redundant components to systems composed of elements subject to failure are considered. In each case the problem is to make an assignment which maximizes the system reliability subject to system constraints. Three distinct problems; are treated. The first is the classical problem of maximizing system reliability under total cost or weight constraints when components are subject to a single type of failure. The second problem deals with components which are subject to two types of failure and minimizes the probability of one mode of system failure subject to a constraint on the probability of the other mode of system failure. The third problem deals with components which may either fail to operate or may operate prematurely. System reliability is maximized subject to a constraint ori system safety. In each case the problem is formulated as an integer linear program. This has an advantage over alternative dynamic programming formulations in that standard algorithms may be employed to obtain numerical results.     

Due-date assignment and early/tardy scheduling on identical parallel machines

This article examines the problem of simultaneously assigning a common due date to a set of independent jobs and scheduling them on identical parallel machines in such a way that the costs associated with the due date and with the earliness or tardiness of the jobs are minimized. We establish that, for certain values of the due-date cost, an optimal schedule for this problem is also optimal for an early/tardy scheduling problem studied by Emmons. We discuss the solution properties for the two problems, and show that both problems are NP-hard even for two machines. We further show that these problems become strongly NP-hard if the number of machines is allowed to be arbitrary. We provide a dynamic programming solution for the problems, the complexity of which indicates that the problems can be solved in pseudopolynomial time as long as the number of machines remains fixed. Finally, we present the results of a limited computational study. © 1994 John Wiley & Sons, Inc.     

Analysis of algorithms for two‐stage flowshops with multi‐processor task flexibility

In this article we introduce a 2‐machine flowshop with processing flexibility. Two processing modes are available for each task: namely, processing by the designated processor, and processing simultaneously by both processors. The objective studied is makespan minimization. This production environment is encountered in repetitive manufacturing shops equipped with processors that have the flexibility to execute orders either individually or in coordination. In the latter case, the product designer exploits processing synergies between two processors so as to execute a particular task much faster than a dedicated processor. This type of flowshop environment is also encountered in labor‐intensive assembly lines where products moving downstream can be processed either in the designated assembly stations or by pulling together the work teams of adjacent stations. This scheduling problem requires determining the mode of operation of each task, and the subsequent scheduling that preserves the flowshop constraints. We show that the problem is ordinary NP‐complete and obtain an optimal solution using a dynamic programming algorithm with considerable computational requirements for medium and large problems. Then, we present a number of dynamic programming relaxations and analyze their worst‐case error performance. Finally, we present a polynomial time heuristic with worst‐case error performance comparable to that of the dynamic programming relaxations. © 2003 Wiley Periodicals, Inc. Naval Research Logistics, 2004.     

An FPTAS for scheduling a two‐machine flowshop with one unavailability interval

We study a deterministic two‐machine flowshop scheduling problem with an assumption that one of the two machines is not available in a specified time period. This period can be due to a breakdown, preventive maintenance, or processing unfinished jobs from a previous planning horizon. The problem is known to be NP‐hard. Pseudopolynomial dynamic programming algorithms and heuristics with worst case error bounds are given in the literature to solve the problem. They are different for the cases when the unavailability interval is for the first or second machine. The existence of a fully polynomial time approximation scheme (FPTAS) was formulated as an open conjecture in the literature. In this paper, we show that the two cases of the problem under study are equivalent to similar partition type problems. Then we derive a generic FPTAS for the latter problems with O(n⁵/ε⁴) time complexity. © 2003 Wiley Periodicals, Inc. Naval Research Logistics, 2004.     

A primal-dual cutting-plane algorithm for all-integer programming

The integer programming literature contains many algorithms for solving all-integer programming problems but, in general, existing algorithms are less than satisfactory even in solving problems of modest size. In this paper we present a new technique for solving the all-integer, integer programming problem. This algorithm is a hybrid (i.e., primal-dual) cutting-plane method which alternates between a primal-feasible stage related to Young's simplified primal algorithm, and a dual-infeasible stage related to Gomory's dual all-integer algorithm. We present the results of computational testing.     

A theoretical and computational comparison of “equivalent” mixed-integer formulations

This paper provides a theoretical and computational comparison of alternative mixed integer programming formulations for optimization problems involving certain types of economy-of-scale functions. Such functions arise in a broad range of applications from such diverse areas as vendor selection and communications network design. A “nonstandard” problem formulation is shown to be superior in several respects to the traditional formulation of problems in this class.     

Approximation schemes for single‐machine scheduling with a fixed maintenance activity to minimize the total amount of late work

We consider the problem of scheduling n independent and simultaneously available jobs without preemption on a single machine, where the machine has a fixed maintenance activity. The objective is to find the optimal job sequence to minimize the total amount of late work, where the late work of a job is the amount of processing of the job that is performed after its due date. We first discuss the approximability of the problem. We then develop two pseudo‐polynomial dynamic programming algorithms and a fully polynomial‐time approximation scheme for the problem. Finally, we conduct extensive numerical studies to evaluate the performance of the proposed algorithms. © 2016 Wiley Periodicals, Inc. Naval Research Logistics 63: 172–183, 2016     

Balancing and optimizing a portfolio of R&D projects

A mathematical formulation of an optimization model designed to select projects for inclusion in an R&D portfolio, subject to a wide variety of constraints (e.g., capital, headcount, strategic intent, etc.), is presented. The model is similar to others that have previously appeared in the literature and is in the form of a mixed integer programming (MIP) problem known as the multidimensional knapsack problem. Exact solution of such problems is generally difficult, but can be accomplished in reasonable time using specialized algorithms. The main contribution of this paper is an examination of two important issues related to formulation of project selection models such as the one presented here. If partial funding and implementation of projects is allowed, the resulting formulation is a linear programming (LP) problem which can be solved quite easily. Several plausible assumptions about how partial funding impacts project value are presented. In general, our examples suggest that the problem might best be formulated as a nonlinear programming (NLP) problem, but that there is a need for further research to determine an appropriate expression for the value of a partially funded project. In light of that gap in the current body of knowledge and for practical reasons, the LP relaxation of this model is preferred. The LP relaxation can be implemented in a spreadsheet (even for relatively large problems) and gives reasonable results when applied to a test problem based on GM's R&D project selection process. There has been much discussion in the literature on the topic of assigning a quantitative measure of value to each project. Although many alternatives are suggested, no one way is universally accepted as the preferred way. There does seem to be general agreement that all of the proposed methods are subject to considerable uncertainty. A systematic way to examine the sensitivity of project selection decisions to variations in the measure of value is developed. It is shown that the solution for the illustrative problem is reasonably robust to rather large variations in the measure of value. We cannot, however, conclude that this would be the case in general. © 2001 John Wiley & Sons, Inc. Naval Research Logistics 48: 18–40, 2001     

分布式约束优化问题及其求解算法

分布式约束优化问题(DCOP)能够对多智能体系统(MAS)中的各种分布式推理任务进行建模,广泛应用于分布式规划、调度、资源分配等问题中。首先从DCOP的概念出发,引入一个典型的DCOP实例,在此基础上对DCOP问题求解的两类主流算法进行了详细介绍和比较分析。针对DCOP对现实问题建模中出现的部分集中式、硬约束、开放式、隐私和anytime等5个方面的问题进行了阐述,并介绍了相应的扩展算法。在动态实时问题,自稳定性与误差容错以及在物理分布式环境下仿真等问题仍需进一步研究。     

Formulations for dynamic lot sizing with service levels

In this article, we study deterministic dynamic lot‐sizing problems with a service‐level constraint on the total number of periods in which backlogs can occur over a finite planning horizon. We give a natural mixed integer programming formulation for the single item problem (LS‐SL‐I) and study the structure of its solution. We show that an optimal solution to this problem can be found in \begin{align*}\mathcal O(n^2\kappa)\end{align*} time, where n is the planning horizon and \begin{align*}\kappa=\mathcal O(n)\end{align*} is the maximum number of periods in which demand can be backlogged. Using the proposed shortest path algorithms, we develop alternative tight extended formulations for LS‐SL‐I and one of its relaxations, which we refer to as uncapacitated lot sizing with setups for stocks and backlogs. {We show that this relaxation also appears as a substructure in a lot‐sizing problem which limits the total amount of a period's demand met from a later period, across all periods.} We report computational results that compare the natural and extended formulations on multi‐item service‐level constrained instances. © 2013 Wiley Periodicals, Inc. Naval Research Logistics, 2013     

Reformulating linear programs with transportation constraints—With applications to workforce scheduling

We study linear programming models that contain transportation constraints in their formulation. Typically, these models have a multistage nature and the transportation constraints together with the associated flow variables are used to achieve consistency between consecutive stages. We describe how to reformulate these models by projecting out the flow variables. The reformulation can be more desirable since it has fewer variables and can be solved faster. We apply these ideas to reformulate two well‐known workforce staffing and scheduling problems: the shift scheduling problem and the tour scheduling problem. We also present computational results. © 2003 Wiley Periodicals, Inc. Naval Research Logistics, 2004.     

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