Search

A promising solution approach called Meta-RaPS is presented for the 0-1 Multidimensional Knapsack Problem (0-1 MKP). Meta-RaPS constructs feasible solutions at each iteration through the utilization of a priority rule used in a randomized fashion. Four different greedy priority rules are implemented within Meta-RaPS and compared. These rules differ in the way the corresponding pseudo-utility ratios for ranking variables are computed. In addition, two simple local search techniques within Meta-RaPS improvement stage are implemented. The Meta-RaPS approach is tested on several established test sets, and the solution values are compared to both the optimal values and the results of other 0-1 MKP solution techniques. The Meta-RaPS approach outperforms many other solution methodologies in terms of differences from the optimal value and number of optimal solutions obtained. The advantage of the Meta-RaPS approach is that it is easy to understand and easy to implement, and it achieves good results.

Generating a project schedule that meets all activity precedence constraints while minimizing the overall project duration is often difficult. The complex project-scheduling problem is further complicated by the real-world constraint that often a limited number of resources must be allocated to competing activities. This paper investigates the application of the computer method COMSOAL to this resource allocation problem. COMSOAL (Computer Method of Sequencing Operations for Assembly Lines), originally a solution approach for the assembly line balancing problem, is a computer heuristic that can be used to generate a feasible solution to the resource allocation problem at each iteration of the heuristic. A solution methodology of repeatedly running COMSOAL will result in many feasible solutions from which the best is chosen. This solution approach now becomes viable given the increased speed of inexpensive computers. This paper discusses the adaptation of the COMSOAL approach to the resource allocation problem as well as a designed experiment used to investigate the appropriateness of COMSOAL for a known set of resource allocation test problems. Results from this experiment show COMSOAL is a viable method to solve these resource allocation problems when compared to the results from several well-known resource allocation algorithms and to the optimal solutions.

The software-oriented, multi-processor database systems are characterized by a set of processing elements (PEs) which run identical software and operate on a partitioned database in parallel. Performance improvements and capacity growth can be achieved in this type of system by adding PEs to the configuration and replicating the existing software on the added PEs. Much work has been done applying graph theory, queuing theory, algorithmic approaches, and analytical techniques towards the design of multi-processor database systems. This paper describes a simulation approach and the application of a simulation language, SLAM, to the design and performance analysis of one such multi-processor database system. The system, relational replicated database system (RRDS), was developed using a five-phase design process. Simulation and analytical techniques were used throughout the development to determine critical elements, components, and design issues, and to evaluate proposed solutions. RRDS was modeled as an open queuing system with SLAM service times determined analytically. The model consisted of a workload scenario generator, a query processing module, and a statistics collection module. In phase one of the simulation study, different hardware organizations were evaluated. Results indicated that the RRDS approach performs approximately three times better than other approaches such as SIMD, MIMD, and functional specialization. In phase two, algorithms and mechanisms for data access were developed. Results favored the B + -tree approach over the clustering approach. A data placement strategy was determined in phase three. Results indicated that the value range partitioning (VRP) approach is more desirable than the round-robin (RR) approach. In phase four, a directory management strategy was selected. Results favored a partitioned and parallel-processed directory, as opposed to a rotating approach. Finally, phase five consisted reveal system strengths and weaknesses, and gain insight into optimal RRDS operating environments. This approach to database system design is both iterative and evolutionary, and can be applied regardless of the type of system being considered. Simulation can be a useful tool in all phases of database system design, from the actual physical hardware architecture to the resolution of software design questions. It plays an important role in predictive performance analysis to determine the extent to which original design goals are achieved.

The main objective of this study was to find a simple and quick procedure on the microcomputer for scheduling activities of a constrained multiple resource single project network that would minimize project duration. From this research there are two different types of results presented. First, a combination of simple heuristics which find the average of the minimum project durations for the constrained resource problem is presented. This combination not only supports the previous research on successful simple heuristic methods which set the priorities for constrained resource problems, but also produces results which are significantly better than those obtained by single heuristics. Second, a procedure for determining this combination of heuristics is introduced. A computer algorithm, COMAL, was developed for this study with constrained resource problems, but in the future its use may be expanded into other fields.

In project scheduling by network analysis, traditional critical path methods fail to include resource considerations. Other methods must be used to allow for resource considerations. This article explores one area of resource considerations: project scheduling under resource constraints. The specific case investigated is the single resource, single project schedule. A model, entitled the GENRES search model, is developed. The model utilizes Brooks Algorithm (BAG) to generate the project schedule. The criteria used are various weighted combinations of ACTIM and ACTRES (Bedworth, Industrial Systems ). The best project schedule is that which gives the least project duration. The GENRES model was found effective in finding project durations equal to or less than that of ACTIM, ACTRES or TIMRES (the combination of ACTIM and ACTRES with each given equal weight). The research also found that when the project completion time found by the algorithm approaches the critical path duration, resource leveling may be preferred.

This paper describes the use of spreadsheets as a tool for macro-manpower modeling. The model defines drivers which are “output measures” for an organization. These drivers are quantified for a Base Case and for points in the future. Staffing for the various departments of the organization are defined for the Base Case. Next, estimates are made of the percent effort by department for each driver. The model also includes a number of damping factors which affect reaction of the model to changes in values of the Drivers. The model can also accommodate special features of a particular organization's manpower needs. The model is a menu-driven LOTUS 1-2-3 template which outputs estimated staffing by department, standards associated with each driver, and graphical output. The approach is presented in connection with a specific application at the Naval Training Systems Center in Orlando.

The system by which the U.S. Navy trains personnel is modeled using the SLAM computer language. By incorporating both network simulation techniques and discrete event logic, the flow of students from a Recruit Training Center (RTC) through the Basic Electricity and Electronics (BEE) schools, the “A” schools and eventually to the fleet, is modeled to a level of detail represented by an individual BEE/“A” school classroom. Inputs for the model include the daily influx of trainees into an RTC for each classification, as well as the various drop, attrition and setback rates. Since the objective of the study was to allow Navy representation to identify potential bottlenecks prior to their occurrence, the output variables depict both resources utilization and queuing statistics. The simulation model was executed, and the resulting outputs were used to test hypotheses.

This paper discusses the development, operation, and testing of a heuristic line balancing program that solves the Type I Line Balance problem using a microcomputer. The line balancing method selected was based on previous studies that compared different line balancing techniques. The model is built primarily using the Hoffman (1963) procedure with modifications described by Gehrlein and Patterson (1975). For purposes of comparison the Rank Positional Weight technique (Helgeson and Birnie, 1961) is also included in the model. Testing included thirty-seven different balances using problems from the literature. For each balance both Rank Positional Weight and Hoffmann solutions were obtained in the forward and reverse directions. Delay factors used for the Hoffmann balances were 0.0, 0.5, 1.0, 1.25, 1.5, and 2.0. Thus for each balance problem a total of fourteen tests were conducted. The total number of tests was 518. Four measures of performance were considered in this study. These measures of performance were: (1) the average percent a balance is above the optimum solution, in terms of number of stations; (2) time to obtain a balance; (3) the best solution in terms of the lowest number of stations and lowest standard deviation of the slack times, and (4) the largest value of minimum station slack time. Overall it was found that the Modified Hoffmann procedure with a delay factor of 1.5 performed best. The time to obtain a balance using the Modified Hoffmann procedure is significantly less than the time for a solution without the modifications.