Export Citations
A note on the single machine serial batching scheduling problem to minimize maximum lateness with precedence constraints
We consider the single machine, serial batching, maximum lateness scheduling problem with precedence constraints in this paper. The complexity of this problem is reported as open in the literature. We give an O(n^2) polynomial-time algorithm for this ...
On the relationships among queue lengths at arrival, departure, and random epochs in the discrete-time queue with D-BMAP arrivals
We consider finite- and infinite-capacity queues with discrete-time batch Markovian arrival processes (D-BMAP) under the assumption of the Late Arrival System with Delayed Access as well as the Early Arrival System. Using simple arguments such as the ...
Compact vs. exponential-size LP relaxations
In this paper, we illustrate by means of examples a technique for formulating compact (i.e. polynomial-size) linear programming relaxations in place of exponential-size models requiring separation algorithms. In the same vein as a celebrated theorem by ...
Optimal allocation of buffers and customers in a two-node cyclic network with multiple servers
Suppose there are a fixed number of waiting positions which need to be allocated between two nodes in a closed, two-node, cyclic, queueing network with multiple servers in order to maximize throughput. We determine the optimal allocation under quite ...
A note on the discretization of Little's result
By considering discrete-time queueing systems as special cases of continuous-time queueing systems, we derive a discrete-time equivalent of Little's result. Our result is general in the sense that no assumptions are made regarding the exact details of ...
An efficient algorithm for a class of constraint satisfaction problems
We define the class of the so-called monotone constraint satisfaction problems (MON-CSP). MON-CSP forms a subclass of the class of min-closed (respectively, max-closed) constraint satisfaction problems of Jeavons and Cooper (Artificial Intelligence 79 (...
On the numerical inversion of busy-period related transforms
Many quantities of interest in queueing theory can be determined in the form of transforms. Methods for numerically inverting those transforms are well developed. However, some transforms such as that of the busy period distribution can only be ...
Optimal block design models for course timetabling
We seek a timetable for courses offered in S sections to maximize contact among K student cohorts over T terms. For this combinatorial optimization problem we propose both integer programming and constraint programming models. The latter ...
A remark about "A comment on consecutive-2-out-of-n systems"
Dei@?neko and Woeginger (Oper. Res. Lett. 28 (2001) 169) present a proof that a result of Du and Hwang (Math. Oper. Res. 11 (1986) 187) about the optimum arrangement of the items in a consecutive-2-out-of-n cycle system is a simple special case of ...
A nontangential cutting plane algorithm
One method for solving the Lagrangian dual problem of a convex program is the cutting plane algorithm. Although this algorithm generally requires cuts that are tangential, or nearly so, to the dual function, this paper demonstrates that the algorithm ...
On Gaver's parallel system sustained by a cold standby unit and attended by two repairmen
We consider Gaver's parallel system sustained by a cold standby unit and attended by two identical repairmen. The system satisfies the usual conditions (i.i.d. random variables, perfect repair, instantaneous and perfect switch, queueing). Each operative ...