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.     

Scheduling parallel dedicated machines with the speeding‐up resource

We consider a problem of scheduling jobs on m parallel machines. The machines are dedicated, i.e., for each job the processing machine is known in advance. We mainly concentrate on the model in which at any time there is one unit of an additional resource. Any job may be assigned the resource and this reduces its processing time. A job that is given the resource uses it at each time of its processing. No two jobs are allowed to use the resource simultaneously. The objective is to minimize the makespan. We prove that the two‐machine problem is NP‐hard in the ordinary sense, describe a pseudopolynomial dynamic programming algorithm and convert it into an FPTAS. For the problem with an arbitrary number of machines we present an algorithm with a worst‐case ratio close to 3/2, and close to 3, if a job can be given several units of the resource. For the problem with a fixed number of machines we give a PTAS. Virtually all algorithms rely on a certain variant of the linear knapsack problem (maximization, minimization, multiple‐choice, bicriteria). © 2008 Wiley Periodicals, Inc. Naval Research Logistics, 2008     

Scheduling on M parallel machines subject to random breakdowns to minimize expected mean flow time

The problem of scheduling n jobs on m parallel machines is considered when the machines are subject to random breakdowns and job processing times are random variables. An objective function of mean flow time is developed for a general parallel machine system, and an expression of its expected value is derived. The problem is transformed into a deterministic unrelated parallel machine scheduling model with modified processing times when the number of breakdowns is modeled as a generalized Poisson process. © 1994 John Wiley & Sons, Inc.     

Optimal renewal policies for complex systems

Most maintenance and replacement models for industrial equipment have been developed for independent single-component machines. Most equipment, however, consists of multiple components. Also, when the maintenance crew services several machines, the maintenance policy for each machine is not independent of the states of the other machines. In this paper, two dynamic programming replacement models are presented. The first is used to determine the optimal replacement policy for multi-component equipment. The second is used to determine the optimal replacement policy for a multi-machine system which uses one replacement crew to service several machines. In addition, an approach is suggested for developing an efficient replacement policy for a multi-component, multi-machine system.     

The open shop scheduling problem with a given sequence of jobs on one machine

The paper considers the open shop scheduling problem to minimize the make-span, provided that one of the machines has to process the jobs according to a given sequence. We show that in the preemptive case the problem is polynomially solvable for an arbitrary number of machines. If preemption is not allowed, the problem is NP-hard in the strong sense if the number of machines is variable, and is NP-hard in the ordinary sense in the case of two machines. For the latter case we give a heuristic algorithm that runs in linear time and produces a schedule with the makespan that is at most 5/4 times the optimal value. We also show that the two-machine problem in the nonpreemptive case is solvable in pseudopolynomial time by a dynamic programming algorithm, and that the algorithm can be converted into a fully polynomial approximation scheme. © 1998 John Wiley & Sons, Inc. Naval Research Logistics 45: 705–731, 1998     

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     

Dual criteria preemptive open-shop problems with minimum makespan

In this article we present an algorithm for the minimum makespan preemptive open shop, which is superior to existing algorithms in both space and time requirements. We define the more complex generalized open shop and flexible open shop and address the minimum makespan problem on these shops. We show how we can use the algorithm for the minimum makespan open shop to achieve load balancing in simple and generalized open shops without increasing the complexity of the algorithm. Load balancing dictates that the number of busy machines in each period is as even as possible. We also consider preventive maintenance issues in the open shop, and makespan retains its minimum value. In particular we consider the scenario where a machine can be maintained during any period that it happens to be idle. Also we consider the case that a maintenance schedule is prespecified. We show that this problem can be solved via a linear programming formulation that can also take into account release times for the jobs and ready times for the machines. Faster algorithms are presented for open shops with three machines or less. © 1995 John Wiley & Sons, Inc.     

Printed circuit board family grouping and component allocation for a multimachine,open-shop assembly cell

This article considers a particular printed circuit board (PCB) assembly system employing surface mount technology. Multiple, identical automatic placement machines, a variety of board types, and a large number of component types characterize the environment studied. The problem addressed is that of minimizing the makespan for assembling a batch of boards with a secondary objective of reducing the mean flow time. The approach adopted is that of grouping boards into production families, allocating component types to placement machines for each family, dividing of families into board groups with similar processing times, and the scheduling of groups. A complete setup is incurred only when changing over between board families. For the environment studied, precedence constraints on the order of component placement do not exist, and placement times are independent of feeder location. Heuristic solution procedures are proposed to create board subfamilies (groups) for which the component mounting times are nearly identical within a subfamily. Assignment of the same component type to multiple machines is avoided. The procedures use results from the theory of open-shop scheduling and parallel processor scheduling to sequence boards on machines. Note that we do not impose an open-shop environment but rather model the problem in the context of an open shop, because the order of component mountings is immaterial. Three procedures are proposed for allocating components to machines and subsequently scheduling boards on the machines. The first two procedures assign components to machines to balance total work load. For scheduling purposes, the first method groups boards into subfamilies to adhere to the assumptions of the open-shop model, and the second procedure assumes that each board is a subfamily and these are scheduled in order of shortest total processing time. The third procedure starts by forming board subfamilies based on total component similarity and then assigns components to validate the open-shop model. We compare the performance of the three procedures using estimated daily, two-day, and weekly production requirements by averaging quarterly production data for an actual cell consisting of five decoupled machines. © 1994 John Wiley & Sons, Inc.     

Steady-state approximation of a multiechelon multi-indentured repairable-item inventory system with a single repair facility

We model a two-echelon multi-indentured repairable-item inventory system where each “base” has a maximum number of identical online machines, and each machine consists of several module types. Machine failures are due to module failures and occur according to an exponential distribution. When a machine fails, the failed module is replaced by an identical spare module if one is available. Otherwise, the module is backordered. All failed modules go to a single “depot” repair facility which consists of a finite number of identical repairmen who are able to repair any module type in an exponentially distributed time, although the repair rates for different module types may differ. The principal contribution of this article is an approximation algorithm for calculating the steady-state characteristics of the system. In comparison with simulation results, the algorithm is quite accurate and computationally efficient. © 1993 John Wiley & Sons, Inc.     

Analysis of a machine repair problem with an unreliable server and phase type repairs and services

In this paper we study a machine repair problem in which a single unreliable server maintains N identical machines. The breakdown times of the machines are assumed to follow an exponential distribution. The server is subject to failure and the failure times are exponentially distributed. The repair times of the machine and the service times of the repairman are assumed to be of phase type. Using matrix‐analytic methods, we perform steady state analysis of this model. The time spent by a failed machine in service and the total time in the repair facility are shown to be of phase type. Several performance measures are evaluated. An optimization problem to determine the number of machines to be assigned to the server that will maximize the expected total profit per unit time is discussed. An illustrative numerical example is presented. © 2003 Wiley Periodicals, Inc. Naval Research Logistics 50: 462–480, 2003     

Some comparative & design aspects of fixed cycle production systems

A serial production line is defined wherein a unit is produced if, and only if, all machines are functioning. A single buffer stock with finite capacity is to be placed immediately after one of the first N-1 machines in the N machine line. When all machines have equal probability of failure it is shown that the optimal buffer position is exactly in the middle of the line. This result is synthesized with the earlier work of Koenigsberg and Buzacott including an analysis of the covariance between transition states. An alternative model formulation is presented and integrated with previous results. Finally, a sufficient condition and solution procedure is derived for the installation of a buffer where there is a possible trade-off between increasing the reliability of the line versus adding a buffer stock.     

Evaluation of costs of ordering policies in large machine repair problems

This article examines a version of the machine repair problem where failures may be irreparable. Since the number of machines in the system keeps decreasing, we impose a fixed state-dependent ordering policy of the type often encountered in inventory models. Although the system is Markovian, the number of states becomes very large. The emphasis of the article, therefore, is on deriving computationally tractable formulas for the steady-state probabilities, the long-run average cost per unit time, and the vector of expected discounted costs. When the state space is so large that exact computations may be infeasible, we propose approximations which are relatively quick and simple to compute and which yield very accurate results for the test problems examined.     

Approximation algorithms for minimizing total weighted completion time of orders on identical machines in parallel

We consider the problem of scheduling orders on identical machines in parallel. Each order consists of one or more individual jobs. A job that belongs to an order can be processed by any one of the machines. Multiple machines can process the jobs of an order concurrently. No setup is required if a machine switches over from one job to another. Each order is released at time zero and has a positive weight. Preemptions are not allowed. The completion time of an order is the time at which all jobs of that order have been completed. The objective is to minimize the total weighted completion time of the orders. The problem is NP‐hard for any fixed number (≥2) of machines. Because of this, we focus our attention on two classes of heuristics, which we refer to as sequential two‐phase heuristics and dynamic two‐phase heuristics. We perform a worst case analysis as well as an empirical analysis of nine heuristics. Our analyses enable us to rank these heuristics according to their effectiveness, taking solution quality as well as running time into account. © 2006 Wiley Periodicals, Inc. Naval Research Logistics, 2006     

Polynomial‐time approximation scheme for concurrent open shop scheduling with a fixed number of machines to minimize the total weighted completion time

In this article, we consider the concurrent open shop scheduling problem to minimize the total weighted completion time. When the number of machines is arbitrary, the problem has been shown to be inapproximable within a factor of 4/3 ‐ ε for any ε > 0 if the unique games conjecture is true in the literature. We propose a polynomial time approximation scheme for the problem under the restriction that the number of machines is fixed. © 2011 Wiley Periodicals, Inc. Naval Research Logistics, 2011     

基于事件的系统可靠性参数仿真算法

介绍了可以用扩展可靠性框图表示的系统的可靠性参数的仿真算法。首先,对扩展可靠性框图进行了介绍,提出了利用树状结构来描述扩展可靠性框图的结构。其次,对基于扩展可靠性框图的系统行为进行了分析。然后,依据离散事件系统仿真思想,分别给出了计算可修系统可靠性参数的仿真算法与不可修系统可靠性参数的仿真算法。最后,给出了计算实例。该仿真算法不仅可以对状态独立系统进行可靠性参数计算,而且可以对具有冷储备关系以及冷储备嵌套关系的状态相关系统进行可靠性参数计算,具有很强的通用性与实用性。     

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.     

An optimum group maintenance policy

In this article we present an optimum maintenance policy for a group of machines subject to stochastic failures where the repair cost and production loss due to the breakdown of machines are minimized. A nomograph was developed for machines with exponential failure time distributions. The optimal schedule time for repair as well as the total repair cost per cycle can be obtained easily from the nomograph. Conditions for the existence of a unique solution for the optimum schedule and the bounds for the schedule are discussed.     

A stochastic constrained optimal replacement model

In this paper a stochastically constrained replacement model is formulated. This model determines a sequence of replacement dates such that the total “current account” cost of all future costs and capital expenditures over an infinite time horizon for the n initial incumbent machines is minimized subject to the constraints that an expected number of machines are in a chosen utility class at any point in time. We then indicate one possible solution method for the model.     

Optimal arrangement of systems

To location L_i we are to allocate a “generator” and n_i “machines” for i = 1, …,k, where n₁ … n₁ ≧ … ≧ n_k. Although the generators and machines function independently of one another, a machine is operable only if it and the generator at its location are functioning. The problem we consider is that of finding the arrangement or allocation optimizing the number of operable machines. We show that if the objective is to maximize the expected number of operable machines at some future time, then it is best to allocate the best generator and the n₁ best machines to location L₁, the second-best generator and the n₂-next-best machines to location L₂, etc. However, this arrangement is not always stochastically optimal. For the case of two generators we give a necessary and sufficient condition that this arrangement is stochastically best, and illustrate the result with several examples.     

Two novel critical shock models based on Markov renewal processes

In this paper, we investigate systems subject to random shocks that are classified into critical and noncritical categories, and develop two novel critical shock models. Classical extreme shock models and run shock models are special cases of our developed models. The system fails when the total number of critical shocks reaches a predetermined threshold, or when the system stays in an environment that induces critical shocks for a preset threshold time, corresponding to failure mechanisms of the developed two critical shock models respectively. Markov renewal processes are employed to capture the magnitude and interarrival time dependency of environment-induced shocks. Explicit formulas for systems under the two critical shock models are derived, including the reliability function, the mean time to failure and so on. Furthermore, the two critical shock models are extended to the random threshold case and the integrated case where formulas of the reliability indexes of the systems are provided. Finally, a case study of a lithium-ion battery system is conducted to illustrate the proposed models and the obtained results.