A special case of the 3 × n flow shop problem

Johnson [2] in 1954 solved the two machine flow shop problem by giving an argument for a sufficient condition of optimality and by stating an efficient algorithm which produces a solution via satisfaction of the sufficient condition. Moreover, Johnson solved two special cases of the corresponding three machine flow shop problem. Since that time, six other special cases have been solved, two contributed by Arthanari and Mukhopadhyay [1], two by Smith, Panwalkar, and Dudek [3], and two of a different nature by Szwarc [5]. This paper contributes an extension to one of the classes described by Szwarc.     

An improved branch and bound procedure for n × m flow shop problems

This paper considers the classical nXm flow shop sequencing problem. An improved branch and bound procedure is proposed. Computational experience shows that the proposed procedure is more efficient compared to the existing optimizing procedures.     

A convex property of an ordered flow shop sequencing problem

A flow shop sequencing problem with ordered processing time matrices is considered. A convex property for the makespan sequences of such problems is discussed. On the basis of this property an efficient optimizing algorithm is presented. Although the proof of optimality has not been developed, several hundred problems were solved optimally with this procedure.     

Minimizing the makespan in open‐shop scheduling problems with a convex resource consumption function

We consider open‐shop scheduling problems where operation‐processing times are a convex decreasing function of a common limited nonrenewable resource. The scheduler's objective is to determine the optimal job sequence on each machine and the optimal resource allocation for each operation in order to minimize the makespan. We prove that this problem is NP‐hard, but for the special case of the two‐machine problem we provide an efficient optimization algorithm. We also provide a fully polynomial approximation scheme for solving the preemptive case. © 2006 Wiley Periodicals, Inc. Naval Research Logistics, 2006     

Time minimizing flows in directed networks

An important class of network flow problems is that class for which the objective is to minimize the cost of the most expensive unit of flow while obtaining a desired total flow through the network. Two special cases of this problem have been solved, namely, the bottleneck assignment problem and time-minimizing transportation problem. This paper addresses the more general case which we shall refer to as the time-minimizing network flow problem. Associated with each arc is an arc capacity (static) and a transferral time. The objective is to find a maximal flow for which the length (in time) of the longest path carrying flow is minimized. The character of the problem is discussed and a solution algorithm is presented.     

Scheduling for parallel dedicated machines with a single server

This paper examines scheduling problems in which the setup phase of each operation needs to be attended by a single server, common for all jobs and different from the processing machines. The objective in each situation is to minimize the makespan. For the processing system consisting of two parallel dedicated machines we prove that the problem of finding an optimal schedule is N P‐hard in the strong sense even if all setup times are equal or if all processing times are equal. For the case of m parallel dedicated machines, a simple greedy algorithm is shown to create a schedule with the makespan that is at most twice the optimum value. For the two machine case, an improved heuristic guarantees a tight worst‐case ratio of 3/2. We also describe several polynomially solvable cases of the later problem. The two‐machine flow shop and the open shop problems with a single server are also shown to be N P‐hard in the strong sense. However, we reduce the two‐machine flow shop no‐wait problem with a single server to the Gilmore—Gomory traveling salesman problem and solve it in polynomial time. © 2000 John Wiley & Sons, Inc. Naval Research Logistics 47: 304–328, 2000     

链约束下加工时间恶化的Flow Shop排序问题

讨论作业具有线性加工时间,作业间具有链约束的两台处理机流水作业排序问题,目标函数为极小化完工时间。在作业加工时间简单线性恶化下,提出作业的非负开始和停止延迟恶化率,构造了满足约束条件的复合作业。在此基础上,给出作业间具有平行链约束的两台处理机流水作业排序问题的最优多项式算法。     

The two-machine permutation flow shop with state-dependent processing times

If the processing time of each job in a flow shop also depends on the time spent prior to processing, then the choice of a sequence influences processing times. This nonstandard scheduling problem is studied here for the minimum makespan schedule in a flow shop with two machines. The problem is NP-hard in the strong sense and already contains the main features of the general case [10]. Restricting to the case of permutation schedules, we first determine the optimal release times of the jobs for a given sequence. Permutation schedules are evaluated for this optimal policy, and the scheduling problem is solved using branch-and-bound techniques. We also show the surprising result that the optimal schedule may not be a permutation schedule. Numerical results on randomly generated data are provided for permutation schedules. Our numerical results confirm our preliminary study [10] that fairly good approximate solutions can efficiently be obtained in the case of limited computing time using the heuristics due to Gilmore and Gomory [7]. © 1993 John Wiley & Sons, Inc.     

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 jobs,with exponentially distributed processing times,on two machines of a flow shop

This paper treats the problem of sequencing n jobs on two machines in a “flow shop.” (That is, each job in the shop is required to flow through the same sequence of the machines.) The processing time of a given job on a given machine is assumed to be distributed exponentially, with a known mean. The objective is to minimize the expected job completion time. This paper proves an optimal ordering rule, previously conjectured by Talwar [10]. A formula is also derived through Markov Chain analysis, which evaluates the expected job completion time for any given sequence of the jobs. In addition, the performance of a heuristic rule is discussed in the light of the optimal solution.     

Scheduling and lot streaming in two‐machine open shops with no‐wait in process

We study the problem of minimizing the makespan in no‐wait two‐machine open shops producing multiple products using lot streaming. In no‐wait open shop scheduling, sublot sizes are necessarily consistent; i.e., they remain the same over all machines. This intractable problem requires finding sublot sizes, a product sequence for each machine, and a machine sequence for each product. We develop a dynamic programming algorithm to generate all the dominant schedule profiles for each product that are required to formulate the open shop problem as a generalized traveling salesman problem. This problem is equivalent to a classical traveling salesman problem with a pseudopolynomial number of cities. We develop and test a computationally efficient heuristic for the open shop problem. Our results indicate that solutions can quickly be found for two machine open shops with up to 50 products. © 2005 Wiley Periodicals, Inc. Naval Research Logistics, 2005     

Counterexamples to optimal permutation schedules for certain flow shop problems

It is well known that a minimal makespan permutation sequence exists for the n × 3 flow shop problem and for the n × m flow shop problem with no inprocess waiting when processing times for both types of problems are positive. It is shown in this paper that when the assumption of positive processing times is relaxed to include nonnegative processing times, optimality of permutation schedules cannot be guaranteed.     

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 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.     

On equivalence between the proportionate flow shop and single‐machine scheduling problems

We derive sufficient conditions which, when satisfied, guarantee that an optimal solution for a single‐machine scheduling problem is also optimal for the corresponding proportionate flow shop scheduling problem. We then utilize these sufficient conditions to show the solvability in polynomial time of numerous proportionate flow shop scheduling problems with fixed job processing times, position‐dependent job processing times, controllable job processing times, and also problems with job rejection. © 2015 Wiley Periodicals, Inc. Naval Research Logistics 62: 595–603, 2015     

Parallel machine scheduling with batch deliveries to minimize total flow time and delivery cost

Motivated by the flow of products in the iron and steel industry, we study an identical and parallel machine scheduling problem with batch deliveries, where jobs finished on the parallel machines are delivered to customers in batches. Each delivery batch has a capacity and incurs a cost. The objective is to find a coordinated production and delivery schedule that minimizes the total flow time of jobs plus the total delivery cost. This problem is an extension of the problem considered by Hall and Potts, Ann Oper Res 135 (2005) 41–64, who studied a two‐machine problem with an unbounded number of transporters and unbounded delivery capacity. We first provide a dynamic programming algorithm to solve a special case with a given job assignment to the machines. A heuristic algorithm is then presented for the general problem, and its worst‐case performance ratio is analyzed. The computational results show that the heuristic algorithm can generate near‐optimal solutions. Finally, we offer a fully polynomial‐time approximation scheme for a fixed number of machines. © 2016 Wiley Periodicals, Inc. Naval Research Logistics 63: 492–502, 2016     

A mofified gub algorithm for solving linear minimax problems

This article is concerned with the minimization of the maximal value of a set of linear functions subject to linear constraints. It is well known that this problem can be transformed into a standard linear programming problem by introducing an additional variable. In case index sets of nonzero coefficients of the variables contained in each function are mutually exclusive, the constraints of the associated LP problem exhibit the almost-GUB structure. We devised a technique which reduces the number of arithmetic operations by exploiting this special structure. Computational results are also presented, which indicates that our method is more efficient than the ordinary revised simplex method.     

A mathematical programming approach for improving the robustness of least sum of absolute deviations regression

This paper discusses a novel application of mathematical programming techniques to a regression problem. While least squares regression techniques have been used for a long time, it is known that their robustness properties are not desirable. Specifically, the estimators are known to be too sensitive to data contamination. In this paper we examine regressions based on Least‐sum of Absolute Deviations (LAD) and show that the robustness of the estimator can be improved significantly through a judicious choice of weights. The problem of finding optimum weights is formulated as a nonlinear mixed integer program, which is too difficult to solve exactly in general. We demonstrate that our problem is equivalent to a mathematical program with a single functional constraint resembling the knapsack problem and then solve it for a special case. We then generalize this solution to general regression designs. Furthermore, we provide an efficient algorithm to solve the general nonlinear, mixed integer programming problem when the number of predictors is small. We show the efficacy of the weighted LAD estimator using numerical examples. © 2006 Wiley Periodicals, Inc. Naval Research Logistics, 2006     

Optimal selection from a random sequence with observation errors

A form of sequential decision problem is introduced in which options are presented in sequence. with no recall of rejected options (as in the secretary problem), but in which the value of each option may only he inferred from experiments. Decisions have thus to be made concerning both the acceptance and rejection of each option and the degree of experimentation. General properties of the optimal policy are derived, and an algorithm is obtained for the solution in a special case. This special case suggests a heuristic rule for more general situations. the performance of which rule has been investigated by a Monte Carlo study.     

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.