Search

Abstract: An efficient exterior point simplex type algorithm for the assignment problem has been developed by Paparrizos [K. Paparrizos, An infeasible (exterior point) simplex algorithm for assignment problems, Math. Program. 51 (1991) 45–54]. This algorithm belongs to the category of forest algorithms and solves an assignment problem in at most iterations and in at most time. In this paper worst case examples are presented. Specifically, a systematic procedure to construct worst case assignment problems is presented for the exterior point algorithm. The algorithm applied to these examples executes exactly iterations. This result verifies that the bound is the best possible for the above-mentioned algorithm. [Copyright &y& Elsevier]

Abstract: Consider a problem of scheduling activities of a research and development project, where precedence relations of the activities constituting the project are represented by edges of an in-forest. Each activity is characterized by two parameters: a cost for attempting that activity and a probability that attempting the activity will lead to successful completion. The problem is to find a policy for attempting activities that minimizes the expected cost incurred until termination (successful completion of the project or the first activity failure). The main result of the paper is the design of an efficient algorithm to determine an optimal sequence in which to attempt the activities; a result which is established for linear and exponential utility functions. It is also shown that, unlike the related problem with out-forest precedence relations, there need not exist an optimal policy that is based on an index-rule for determining priority of edges by evaluating their successors. [Copyright &y& Elsevier]

Abstract: This paper considers how to optimally set the basestock level for a single buffer when demand is uncertain, in a robust framework. We present a family of algorithms based on decomposition that scale well to problems with hundreds of time periods, and theoretical results on more general models. [Copyright &y& Elsevier]

Abstract: In a recent paper [Discrete Appl. Math. 130 (2003) 449–467], Yang, Ye, and Zhang investigate the problem of scheduling independent jobs on two identical machines, with a limit on the number of jobs that can be assigned to each single machine, so as to minimize the total weighted completion time of the jobs. They provide a semidefinite programming based, polynomial time approximation algorithm with a worst case ratio of . In this short technical note, we establish the existence of an FPTAS for this problem, and for the corresponding makespan minimization problem. [Copyright &y& Elsevier]