In this paper, we study a scheduling problem on a single machine, provided that the jobs have individual release dates and deadlines, and the processing times are controllable. The objective is to find a feasible sche...
详细信息
In this paper, we study a scheduling problem on a single machine, provided that the jobs have individual release dates and deadlines, and the processing times are controllable. The objective is to find a feasible schedule that minimizes the total cost of reducing the processing times. We reformulate the problem in terms of maximizing a linear function over a submodular polyhedron intersected with a box. For the latter problem of submodular optimization, we develop a recursive decomposition algorithm and apply it to solving the single machine scheduling problem to achieve the best possible running time.
A fluid network is a deterministic network model in which dynamic continuous flows are circulated and processed. among a set of stations. A fluid network often describes the asymptotic behavior of a stochastic queuein...
详细信息
A fluid network is a deterministic network model in which dynamic continuous flows are circulated and processed. among a set of stations. A fluid network often describes the asymptotic behavior of a stochastic queueing network via functional strong law of large numbers. We study the dynamic scheduling of multiple classes of fluid traffic in such a network. An algorithm is developed that systematically solves the dynamic scheduling problem by solving a sequence of linear programs. It generates a policy, in the form of dynamic capacity allocation at each station (among all fluid classes), that consists of a finite set of linear ''pieces'' over the entire time horizon. In a single-station, or equivalently, single-server, network, this solution procedure recovers the priority index set that is optimal for the corresponding discrete queueing model, generally known as Klimov's problem.
The phenomenal growth of microcomputers in both market size and technology has resulted in a proliferation of management science/operations research science software, including linearprogramming (LP) software. An ear...
详细信息
The phenomenal growth of microcomputers in both market size and technology has resulted in a proliferation of management science/operations research science software, including linearprogramming (LP) software. An earlier survey of LP software was published three years ago. This broad summary of LP software highlights recent advances, such as spreadsheet-based software and model generation systems, and discusses its enhanced capability to handle larger problems, greater speed, and better user interfaces.
An embedded network within a linear program is, roughly speaking, a subset of constraints that represent conservation of flow. We examine three broad classes of heuristic techniques—row-scanning deletion, column-scan...
详细信息
An embedded network within a linear program is, roughly speaking, a subset of constraints that represent conservation of flow. We examine three broad classes of heuristic techniques—row-scanning deletion, column-scanning deletion, and row-scanning addition—for the extraction of large embedded networks. We present a variety of implementations, and compare their performance on realistic test problems. The success of our tests depends, in part, on several preprocessing steps that scale the constraint matrix and that set aside certain rows and columns. Efficiency of the subsequent network extraction is dependent on the implementation, in predictable ways. Effectiveness is harder to explain; the more sophisticated and expensive implementations seem to be most reliable, but much simpler implementations sometimes find larger networks. The largest networks are obtained by applying a final augmentation phase, which is studied in the second part of this paper.
Within 21 months Blue Bell reduced its inventory by more than 31 percent, from 371 to 256 million dollars, with no decrease in sales or services by applying management science models. A combination of innovative probl...
详细信息
Within 21 months Blue Bell reduced its inventory by more than 31 percent, from 371 to 256 million dollars, with no decrease in sales or services by applying management science models. A combination of innovative problem solving and enthusiastic management support ensured success. Many of the models are standard, but a new marker design and selection model makes the systems approach practical. Management paid close attention to systems development and provided resources that enhanced the effectiveness of the project.
We pose the following problem: given m jobs, each of which requires a certain total amount of labour that must be performed within specified time periods, how should one schedule the jobs' execution to obtain a to...
详细信息
We pose the following problem: given m jobs, each of which requires a certain total amount of labour that must be performed within specified time periods, how should one schedule the jobs' execution to obtain a total workload that is as even as possible? A related question is: what is the minimal work capacity needed to accomplish all jobs? These questions can be formulated as a linear program, but the number of variables and constraints required usually will be large. Using linear duality theory we instead derive a purely combinatorial problem whose resolution leads to the needed minimal capacity, and thus to the imposed bottleneck. Then we concentrate on the important special case where the time constraints for performing each job are in the form of a single time interval: We detail a simple procedure that efficiently determines the minimal capacity and the bottleneck. A second efficient combinatorial algorithm determines a feasible execution schedule which minimizes the maximum total workload. These algorithms require a computational time of the order of m2 and negligible core memory, and for most practical applications can be implemented on microcomputers.
作者：
SHARDA, ROklahoma State Univ
Coll of Business Administration Stillwater OK USA Oklahoma State Univ Coll of Business Administration Stillwater OK USA
Growth of microcomputers has led to proliferation of Management Science/Operations Research software. Some linearprogramming packages running on popular microcomputers are compared and summarized. A directory of soft...
详细信息
Growth of microcomputers has led to proliferation of Management Science/Operations Research software. Some linearprogramming packages running on popular microcomputers are compared and summarized. A directory of software, publishers, and prices is also included.
Multiple objective seed orchards have been proposed for some time, but techniques for their management have not been forthcoming. The concept developed here facilitates genetic diversity in the breeding population, ch...
详细信息
Multiple objective seed orchards have been proposed for some time, but techniques for their management have not been forthcoming. The concept developed here facilitates genetic diversity in the breeding population, changes in breeding objectives without going back to earlier generations of selection, and the provision for genetic improvement in any selected direction. Problems with inbreeding are considered and application of the concept to current tree improvement programs is discussed.
To comply with the National Forest Management Act of 1976, operations research analysts were placed in nearly all of the 121 national forest headquarters to perform forest-level planning using large and complex linear...
详细信息
To comply with the National Forest Management Act of 1976, operations research analysts were placed in nearly all of the 121 national forest headquarters to perform forest-level planning using large and complex linearprogramming models. In spite of early criticism, the models and the analysts are now being accepted by middle managers as valuable aids to modern forest management. As more advanced technology reaches the Forest Service through—among other things—a newly purchased distributed computer system, these gains in operations research will be the groundwork for extensive future applications.
We develop a production planning model in the context of a system of assembly lines or production lines. The model is a large-scale linear program and we provide a polynomial column generation technique for its effici...
详细信息
We develop a production planning model in the context of a system of assembly lines or production lines. The model is a large-scale linear program and we provide a polynomial column generation technique for its efficient solution. The column generation technique and the approach therein are also of interest in certain other problems. A numerical example to illustrate the algorithm is included. Finally computational experience with the algorithm is summarized.
暂无评论