In this paper, we consider maximum integral flow problems with an additional reverse convex constraint involving one or two nonlinear variables. Based on a parametric approach, we propose a polynomial-time algorithm for computing an integral flow globally optimal to the problem with a single nonlinear variable. We extend this idea and solve the problem with two nonlinear variables. The algorithm solves a sequence of ordinary minimum cost flow problems by using a conventional method and yields a globally optimal solution in pseudo-polynomial time. The prob-lem consists in finding an ordering of the jobs such that the completion time of the job sequenced last is minimized.
Some computational experience is reported along with the analysis of a simple case study.
In many important applications, a situation is encountered where the service capacity of a server must be switched between various competing classes of customers. In most situations, this switchover is not costless. A penalty must be paid either in terms of lost service capacity during the switching period or in terms of a cost to carry out the switching or both. Although queues with switchover abound in applications, generally applicable results are not widely available. In this paper, we review and analyze optimal control policies for queues with switchover.