Batch scheduling with controllable setup and processing times to minimize total completion time

We study a problem of scheduling n jobs on a single machine in batches. A batch is a set of jobs processed contiguously and completed together when the processing of all jobs in the batch is finished. Processing of a batch requires a machine setup time dependent on the position of this batch in the batch sequence. Setup times and job processing times are continuously controllable, that is, they are real-valued variables within their lower and upper bounds. A deviation of a setup time or job processing time from its upper bound is called a compression. The problem is to find a job sequence, its partition into batches, and the values for setup times and job processing times such that (a) total job completion time is minimized, subject to an upper bound on total weighted setup time and job processing time compression, or (b) a linear combination of total job completion time, total setup time compression, and total job processing time compression is minimized. Properties of optimal solutions are established. If the lower and upper bounds on job processing times can be similarly ordered or the job sequence is fixed, then O(n³ log n) and O(n⁵) time algorithms are developed to solve cases (a) and (b), respectively. If all job processing times are fixed or all setup times are fixed, then more efficient algorithms can be devised to solve the problems.     

An efficient approach for solving the lot-sizing problem with time-varying storage capacities

We address the dynamic lot size problem assuming time-varying storage capacities. The planning horizon is divided into T periods and stockouts are not allowed. Moreover, for each period, we consider a setup cost, a holding unit cost and a production/ordering unit cost, which can vary through the planning horizon. Although this model can be solved using O(T³) algorithms already introduced in the specialized literature, we show that under this cost structure an optimal solution can be obtained in O(T log T) time. In addition, we show that when production/ordering unit costs are assumed to be constant (i.e., the Wagner–Whitin case), there exists an optimal plan satisfying the Zero Inventory Ordering (ZIO) property.     

Scheduling an unbounded batching machine with family jobs and setup times

We consider the problem of scheduling n jobs on an unbounded batching machine that can process any number of jobs belonging to the same family simultaneously in the same batch. All jobs in the same batch complete at the same time. Jobs belonging to different families cannot be processed in the same batch, and setup times are required to switch between batches that process jobs from different families. For a fixed number of families m, we present a generic forward dynamic programming algorithm that solves the problem of minimizing an arbitrary regular cost function in pseudopolynomial time. We also present a polynomial-time backward dynamic programming algorithm with time complexity O (mn(n/m+1) ^m ) for minimizing any additive regular minsum objective function and any incremental regular minmax objective function. The effectiveness of our dynamic programming algorithm is shown by computational experiments based on the scheduling of the heat-treating process in a steel manufacturing plant.     

Scheduling transmissions in a network

Consider k stations wishing to transmit messages over a network of channels to a common receiver. The capacity of a channel is the maximum amount of data which can be transmitted in a time unit. In addition to the transmission stations, the network contains switching nodes. Given that the jth station has σ_j messages (j = 1,…, k) to transmit, it is desired to find a schedule with minimum completion time T. The amount of data sent over a channel may vary in time. A schedule is stationary if the amount of data sent in a time unit is constant throughout the schedule. It is first shown that for every schedule there exists a stationary schedule with the same completion time. Thus, the search for an optimum schedule is confined to stationary schedules. The problem of finding an optimum stationary schedule is formulated as a multisource single-sink network flow problem, in which the net amount of outgoing flow from each source (transmission station) within one time unit is $\text{σ}{}_{\mathrm{j}}\text{T}$. An O(k|E||V|²) time algorithm to find the minimum T similar to Dinic's flow algorithm is suggested. Using Sleator and Tarjan's techniques an O(k²|E||V|log|V|) algorithm is derived. The running time of both algorithms is independent of the σ_j's and the capacities.     

Multi-item lot-sizing with joint set-up costs

We consider a multi-item lot-sizing problem with joint set-up costs and constant capacities. Apart from the usual per unit production and storage costs for each item, a set-up cost is incurred for each batch of production, where a batch consists of up to C units of any mix of the items. In addition, an upper bound on the number of batches may be imposed. Under widely applicable conditions on the storage costs, namely that the production and storage costs are nonspeculative, and for any two items the one that has a higher storage cost in one period has a higher storage cost in every period, we show that there is a tight linear program with O(mT ²) constraints and variables that solves the joint set-up multi-item lot-sizing problem, where m is the number of items and T is the number of time periods. This establishes that under the above storage cost conditions this problem is polynomially solvable. For the problem with backlogging, a similar linear programming result is described for the uncapacitated case under very restrictive conditions on the storage and backlogging costs. Computational results are presented to test the effectiveness of using these tight linear programs in strengthening the basic mixed integer programming formulations of the joint set-up problem both when the storage cost conditions are satisfied, and also when they are violated.     

Economic design of an adaptive <Emphasis Type="Italic">T</Emphasis><Superscript>2</Superscript> control chart

Varying three parameters of the Hotelling's T² control chart, namely, the sample size, the sampling interval length, and the action limit, results in a great improvement over the traditional T² control chart particularly for the small process shift. This paper presents the economic model for designing the variable parameters T² chart. In the economic design, a cost function is constructed, involving the cost of sampling and testing, the cost of false alarm, the cost to detect and remove the assignable cause, and the cost when the process is operating out-of-control. Also, a heuristic method of finding optimal values of adaptive design parameters for minimizing the cost function is presented. Variable and fixed parameters T² control charts are compared with respect to the expected loss per unit time. Furthermore, the effects of the initial sample number (used for estimating the parameters of F-distribution) upon the operating cost and adaptive design parameters are examined.     

An Efficient Procedure for Dynamic Lot-sizing Model with Demand Time Windows

We consider a dynamic lot-sizing model with demand time windows where n demands need to be scheduled in T production periods. For the case of backlogging allowed, an O(T ³) algorithm exists under the non-speculative cost structure. For the same model with somewhat general cost structure, we propose an efficient algorithm with O(max {T ², nT}) time complexity.     

Modelling gateway placement in wireless networks: Geometric k-centres of unit disc graphs

Motivated by the gateway placement problem in wireless networks, we consider the geometric k-centre problem on unit disc graphs: given a set of points P in the plane, find a set F of k points in the plane that minimizes the maximum graph distance from any vertex in P to the nearest vertex in F in the unit disc graph induced by P∪F. We show that the vertex 1-centre provides a 7-approximation of the geometric 1-centre and that a vertex k-centre provides a 13-approximation of the geometric k-centre, resulting in an O(kn)-time 26-approximation algorithm. We describe O(n²m)-time and O(n³)-time algorithms, respectively, for finding exact and approximate geometric 1-centres, and an O(mn2k)-time algorithm for finding a geometric k-centre for any fixed k. We show that the problem is NP-hard when k is an arbitrary input parameter. Finally, we describe an O(n)-time algorithm for finding a geometric k-centre in one dimension.     

Uniform-cost inverse absolute and vertex center location problems with edge length variations on trees

This article considers the inverse absolute and the inverse vertex 1-center location problems with uniform cost coefficients on a tree network T with n+1 vertices. The aim is to change (increase or reduce) the edge lengths at minimum total cost with respect to given modification bounds such that a prespecified vertex s becomes an absolute (or a vertex) 1-center under the new edge lengths. First an O(nlogn) time method for solving the height balancing problem with uniform costs is described. In this problem the height of two given rooted trees is equalized by decreasing the height of one tree and increasing the height of the second rooted tree at minimum cost. Using this result a combinatorial O(nlogn) time algorithm is designed for the uniform-cost inverse absolute 1-center location problem on tree T. Finally, the uniform-cost inverse vertex 1-center location problem on T is investigated. It is shown that the problem can be solved in O(nlogn) time if all modified edge lengths remain positive. Dropping this condition, the general model can be solved in O(r_vnlogn) time where the parameter r_v is bounded by ⌈n/2⌉. This corrects an earlier result of Yang and Zhang.     

The inverse Fermat–Weber problem

Given n points in the plane with nonnegative weights, the inverse Fermat–Weber problem consists in changing the weights at minimum cost such that a prespecified point in the plane becomes the Euclidean 1-median. The cost is proportional to the increase or decrease of the corresponding weight. In case that the prespecified point does not coincide with one of the given n points, the inverse Fermat–Weber problem can be formulated as linear program. We derive a purely combinatorial algorithm which solves the inverse Fermat–Weber problem with unit cost using O(n) greedy-like iterations where each of them can be done in constant time if the points are sorted according to their slopes. If the prespecified point coincides with one of the given n points, it is shown that the corresponding inverse problem can be written as convex problem and hence is solvable in polynomial time to any fixed precision.     

Uncapacitated two-level lot-sizing

For the uncapacitated two-level production-in-series T period lot-sizing model, a dynamic program with running time O(T²logT) and a compact and tight extended formulation with O(T³) variables and O(T²) equality constraints are presented. Limited computational comparisons of various formulations of two-level production/transportation problems with multiple clients are reported.     

Dynamic admission and service rate control of a queue

This paper investigates a queueing system in which the controller can perform admission and service rate control. In particular, we examine a single-server queueing system with Poisson arrivals and exponentially distributed services with adjustable rates. At each decision epoch the controller may adjust the service rate. Also, the controller can reject incoming customers as they arrive. The objective is to minimize long-run average costs which include: a holding cost, which is a non-decreasing function of the number of jobs in the system; a service rate cost c(x), representing the cost per unit time for servicing jobs at rate x; and a rejection cost κ for rejecting a single job. From basic principles, we derive a simple, efficient algorithm for computing the optimal policy. Our algorithm also provides an easily computable bound on the optimality gap at every step. Finally, we demonstrate that, in the class of stationary policies, deterministic stationary policies are optimal for this problem.     

On a disparity between relative cliquewidth and relative NLC-width

Cliquewidth and NLC-width are two closely related parameters that measure the complexity of graphs. Both clique- and NLC-width are defined to be the minimum number of labels required to create a labelled graph by certain terms of operations. Many hard problems on graphs become solvable in polynomial-time if the inputs are restricted to graphs of bounded clique- or NLC-width. Cliquewidth and NLC-width differ at most by a factor of two.The relative counterparts of these parameters are defined to be the minimum number of labels necessary to create a graph while the tree-structure of the term is fixed. We show that Relative Cliquewidth and Relative NLC-width differ significantly in computational complexity. While the former problem is NP-complete the latter is solvable in polynomial time. The relative NLC-width can be computed in O(n³) time, which also yields an exact algorithm for computing the NLC-width in time O(3ⁿn). Additionally, our technique enables a combinatorial characterisation of NLC-width that avoids the usual operations on labelled graphs.     

Isoperimetric triangular enclosures with a fixed angle

In this paper, we study four variants of the famous isoperimetric problem. Given a set S of n > 2 points in the plane (in general position), we show how to compute in O(n ²) time, a triangle with maximum (or minimum) area enclosing S among all enclosing triangles with fixed perimeter and one fixed angle. We also show how to compute in O(n ²) time, a triangle with maximum (or minimum) perimeter enclosing S among all enclosing triangles with fixed area and one fixed angle. We also provide an Ω (n log n) lower bound for these problems in the algebraic computation tree model.     

Single item lot-sizing problem for a warm/cold process with immediate lost sales

We consider the dynamic lot-sizing problem with finite capacity and possible lost sales for a process that could be kept warm at a unit variable cost for the next period t + 1 only if more than a threshold value Q_t has been produced and would be cold, otherwise. Production with a cold process incurs a fixed positive setup cost, K_t and setup time, S_t, which may be positive. Setup costs and times for a warm process are negligible. We develop a dynamic programming formulation of the problem, establish theoretical results on the structure of the optimal production plan in the presence of zero and positive setup times with Wagner–Whitin-type cost structures. We also show that the solution to the dynamic lot-sizing problem with lost sales are generated from the full commitment production series improved via lost sales decisions in the presence of a warm/cold process.     

Bicriteria scheduling on a series-batching machine to minimize maximum cost and makespan

This paper studies the bicriteria problem of scheduling n jobs on a serial-batching machine to minimize maximum cost and makespan simultaneously. A serial-batching machine is a machine that can handle up to b jobs in a batch and jobs in a batch start and complete respectively at the same time and the processing time of a batch is equal to the sum of the processing times of jobs in the batch. When a new batch starts, a constant setup time s occurs. We confine ourselves to the unbounded model, where b ≥ n. We present a polynomial-time algorithm for finding all Pareto optimal solutions of this bicriteria scheduling problem.     

A deteriorating cold standby repairable system with priority in use

In this paper, a cold standby repairable system consisting of two dissimilar components and one repairman is studied. In this system, it is assumed that the working time distributions and the repair time distributions of the two components are both exponential and component 1 is given priority in use. After repair, component 2 is “as good as new” while component 1 follows a geometric process repair. Under these assumptions, using the geometric process and a supplementary variable technique, some important reliability indices such as the system availability, reliability, mean time to first failure (MTTFF), rate of occurrence of failure (ROCOF) and the idle probability of the repairman are derived. A numerical example for the system reliability R(t) is given. And it is considered that a repair-replacement policy based on the working age T of component 1 under which the system is replaced when the working age of component 1 reaches T. Our problem is to determine an optimal policy T^∗ such that the long-run average cost per unit time of the system is minimized. The explicit expression for the long-run average cost per unit time of the system is evaluated, and the corresponding optimal replacement policy T^∗ can be found analytically or numerically. Another numerical example for replacement model is also given.     

Minimum flow problem on network flows with time-varying bounds

In this paper, we consider the minimum flow problem on network flows in which the lower arc capacities vary with time. We will show that this problem for set {0, 1, … , T} of time points can be solved by at most n minimum flow computations, by combining of preflow-pull algorithm and reoptimization techniques (no matter how many values of T are given). Running time of the presented algorithm is O(n²m).     

Minimum cost open chain reconfiguration

An open chain or n-link is a sequence of n links with fixed lengths that are joined together at their endpoints and can turn about their endpoints, which act as joints. Positions of the joints of a chain define a configuration of the chain in the space. In one-dimensional space, we define a binary configuration as a sequence of direction of links. Open chain reconfiguration is a sequence of predefined transformation operations which can be used to convert a given binary configuration to another given binary configuration. Each transformation operation is assigned a cost. For two given binary configurations, there may be many reconfigurations whose costs are different. We formalize the problem, and we propose a dynamic programming approach to find a reconfiguration whose cost is minimum for the conversion of two given binary configurations of an open chain in the one-dimensional space. Our algorithm takes O(n²) time using O(n) space.     

Modeling and analysis for determining optimal suppliers under stochastic lead times

The policy of simultaneously splitting replenishment orders among several suppliers has received considerable attention in the last few years and continues to attract the attention of researchers. In this paper, we develop a mathematical model which considers multiple-supplier single-item inventory systems. The item acquisition lead times of suppliers are random variables. Backorder is allowed and shortage cost is charged based on not only per unit in shortage but also per time unit. Continuous review (s,Q)$(s\text{,}Q)$ policy has been assumed. When the inventory level depletes to a reorder level, the total order is split among n suppliers. Since the suppliers have different characteristics, the quantity ordered to different suppliers may be different. The problem is to determine the reorder level and quantity ordered to each supplier so that the expected total cost per time unit, including ordering cost, procurement cost, inventory holding cost, and shortage cost, is minimized. We also conduct extensive numerical experiments to show the advantages of our model compared with the models in the literature. According to our extensive experiments, the model developed in this paper is the best model in the literature which considers order splitting for n-supplier inventory systems since it is the nearest model to the real inventory system.