INFORMS Journal on Computing articles from January 2005

INFORMS Journal on Computing archives from January 2005

From the Editor.
January 1, 2005... Over the past year, the submission rate to JOC has climbed fairly rapidly, and shows no signs of abating. At the same time our acceptance rate has decreased, but the net effect is that our backlog of accepted papers has grown to the point that...

On the generality of event-graph models.
January 1, 2005... Event graphs model the dynamics of a discrete-event simulation model. This paper demonstrates the modeling power of event graphs by presenting a model that simulates a Turing machine. Therefore, according to Church's thesis, event-graph models...

Meta-heuristics for a class of demand-responsive transit systems.
January 1, 2005... The demand-adaptive systems studied in this paper attempt to offer demand-responsive services within the framework of traditional scheduled bus transportation: Users call to request service between two given points and, in so doing, induce...

Oblique multicategory decision trees using nonlinear programming.
January 1, 2005... Induction of decision trees is a popular and effective method for solving classification problems in data-mining applications. This paper presents a new algorithm for multi-category decision tree induction based on nonlinear programming. This...

A GRASP for parallel machine scheduling with time windows.
January 1, 2005... This paper presents a greedy randomized adaptive search procedure (GRASP) for scheduling n jobs on m nonhomogeneous parallel machines with time windows. An additional feature of the problem is that each job falls into one of [rho] priority...

Constraint-propagation-based cutting planes: an application to the resource-constrained project scheduling problem.
January 1, 2005... We propose a cooperation method between constraint programming and integer programming to compute lower bounds for the resource-constrained project scheduling problem (RCPSP). The lower bounds are evaluated through linear-programming (LP)...

Numerical solutions of renewal-type integral equations.
January 1, 2005... The integral equation of renewal type has many applications in applied probability. However, it is rarely solvable in closed form. In this paper, we describe a numerical method for finding approximate solutions to integral equations of renewal...

A two-moment approximation for the GI/G/c queue with finite capacity.
January 1, 2005... In this paper, we consider the steady-state queue length of the multiserver finite-capacity GI/G/c/c + r queue. As a result, we first obtain an exact transform-free expression for the steady-state queue-length distribution. Making use of this...

A local-search-based heuristic for the demand-constrained multidimensional knapsack problem.
January 1, 2005... We consider an extension of the 0-1 multidimensional knapsack problem in which there are greater-than-or-equal-to inequalities, called demand constraints, in addition to the standard less-than-or-equal-to constraints. Moreover, the objective...

Optimal processing policies for an e-commerce web server.
January 1, 2005... The explosive growth in online shopping has provided online retailers impressive opportunities to extend revenue and profit. However, retailers may lose considerable online business from slow response times at electronic shopping sites....

Context-independent scatter and tabu search for permutation problems.
January 1, 2005... In this paper, we develop a general-purpose heuristic for permutations problems. The procedure is based on the scatter-search and tabu-search methodologies and treats the objective-function evaluation as a black box, making the search algorithm...

An experimental study of LP-based approximation algorithms for scheduling problems.
January 1, 2005... Recently there has been much progress on the design of approximation algorithms for a variety of scheduling problems in which the goal is to minimize the average weighted completion time of the jobs scheduled. Many of these approximation...