摘要:

AbstractIn the school timetabling problem a set of lessons (combinations of classes, teachers, subjects and rooms) has to be scheduled within the school week. Considering classes, teachers and rooms as resources for the lessons, the problem may be viewed as the scheduling of a project subject to resource constraints. We have developed an algorithm with three phases. In Phase I an initial solution is built by using the scheme of parallel heuristic algorithm with priority rules, but imbedding at each period the construction of a maximum cardinality independent set on a resource graph. In Phase II a tabu search procedure starts from the solution of Phase I and obtains a feasible solution to the problem. The solution obtained is improved in Phase III. Several procedures based on the calculation of negative cost cycles and shortest paths in a solution graph are used to get more compact timetables.The algorithms have been imbedded in a package designed to solve the problem for Spanish secondary schools. The computational results show its performance on a set of real problems. Nevertheless, it can be applied to more general problems and results on a set of large random problems are also provided.

ISSN:0160-5682    

DOI:10.1057/jors.1996.149

出版商:Taylor&Francis    

年代:1996

数据来源: Taylor

摘要:

AbstractResearch on the planning and scheduling issues of flexible manufacturing systems (FMS) has not been sparse. Most, if not all, studies, however, have focused on either developing the planning model or examining the performance of different scheduling rules. To date, the FMS planning and scheduling problems have not been studied together, though they are highly interrelated.This paper takes a first step to simultaneously address the planning and scheduling problems of flexible manufacturing systems. The problems are solved as a hierarchical process. We first integrate and formulate batching, loading, and routeing, three of the most important FMS planning problems, as a 0–1 mixed integer program. According to the optimal decisions provided by the integrated planning model, we then develop an off-line scheduling scheme that is capable of generating detail parts sequencing in the sequence independent environment (i.e. the operations are not constrained by a process sequence). Finally, we suggest several extensions and future research directions.

ISSN:0160-5682    

DOI:10.1057/jors.1996.150

出版商:Taylor&Francis    

年代:1996

数据来源: Taylor

摘要:

AbstractIn this paper, optimal inventory lot-sizing models are developed for deteriorating items with general continuous time-varying demand over a finite planning horizon and under three replenishment policies. The deterioration rate is assumed to be a constant fraction of the on-hand inventory. Shortages are permitted and are completely backordered. The proposed solution procedures are shown to generate global minimum replenishment schedules for both general increasing and decreasing demand patterns. An extensive empirical comparison using randomly generated linear and exponential demands revealed that the replenishment policy which starts with shortages in every cycle is the least cost policy and the replenishment policy which prohibits shortages in the last cycle exhibited the best service level effectiveness. An optimal procedure for the same problem with trended inventory subject to a single constraint on the minimum service level (maximum fraction of time the inventory system is out of stock during the planning horizon) is also proposed in this paper.

ISSN:0160-5682    

DOI:10.1057/jors.1996.151

出版商:Taylor&Francis    

年代:1996

数据来源: Taylor

摘要:

AbstractA nonpreemptive single stage manufacturing process with parallel, unrelated machines and multiple job types with setups (PUMS) is considered. We propose a hybrid approximation procedure where a Lagrangean relaxation dual and a Lagrangean decomposition dual are solved one after the other to generate a good lower bound on the optimal makespan value. Computational results are reported.

ISSN:0160-5682    

DOI:10.1057/jors.1996.152

出版商:Taylor&Francis    

年代:1996

数据来源: Taylor

摘要:

AbstractIn all large scale projects, there correspond cash flows that incur throughout the life of the project. The scheduling of these projects to maximize the present value of the cash flows has been a topic of recent research. The basic assumption of earlier research is that the cash flows are mainly associated with some events of the project and they occur at the event realization times. However, in several real life projects, the cash inflows do not occur at the event realization times, rather they occur at the end of some time periods, like months, as progress payments. In this article, maximizing the present value of the cash flows in such projects is considered and a mixed-integer formulation of the problem is presented. In this formulation, activity profit curves are defined and used. Computational experience on some randomly generated test problems provides promising results especially when the Benders Decomposition technique is employed for solving the problem.

ISSN:0160-5682    

DOI:10.1057/jors.1996.153

出版商:Taylor&Francis    

年代:1996

数据来源: Taylor

摘要:

AbstractBeasley studied the multiproduct Decision Making Unit, and offered a model for the joint determination of efficiencies within a Data Envelopment Analysis context. He applied his model to evaluating the efficiency of teaching and research activities at universities. This paper explores the theoretical justifications for Beasley's approach by concentrating on the dual of his model.

ISSN:0160-5682    

DOI:10.1057/jors.1996.154

出版商:Taylor&Francis    

年代:1996

数据来源: Taylor

摘要:

AbstractIn this paper, a set of jobs is scheduled using the SLK due-date determination method, according to which all the jobs are given the same flow allowance. The single machine case is considered. The objective function is a cost function including three components, namely flow allowance and weighted earliness and tardiness. An analytical solution is given and an algorithm, which provides optimal solutions, is presented. Finally, the parallel machines case is discussed.

ISSN:0160-5682    

DOI:10.1057/jors.1996.155

出版商:Taylor&Francis    

年代:1996

数据来源: Taylor

摘要:

AbstractIn the past few years, considerable attention has been given to the inventory lot sizing problem with trended demand over a fixed horizon. The traditional replenishment policy is to avoid shortages in the last cycle. Each of the remaining cycles starts with a replenishment and inventory is held for a certain period which is followed by a period of shortages. A new replenishment policy is to start each cycle with shortages and after a period of shortages a replenishment should be made. In this paper, we show that this new type of replenishment policy is superior to the traditional one. We further propose four heuristic procedures that follow the new replenishment policy. These are the constant demand approximation method, the equal cycle length heuristic, the extended Silver approach, and the extended least cost solution procedure. We also examine the cost and computation time performances of these heuristic procedures through an empirical study. The number of test problems solved to optimality, average and maximum cost deviation from optimum were used as measures of cost performance. The results of the 10 000 test problems reveal that the extended least cost approach is most cost effective.

ISSN:0160-5682    

DOI:10.1057/jors.1996.156

出版商:Taylor&Francis    

年代:1996

数据来源: Taylor

摘要:

AbstractExpensive renewable spares known as‘insurance type’spares are often a major concern in the design and setting up of industrial, commercial and military systems. These spares, though low in demand, are critical to the system's operation and their unavailability can lead to excessive downtime costs. Due to their nature, the (S-1,S) inventory control model provides an appropriate replenishment policy for this class of items, whereSis the maximum number of spares in inventory. A (S-1,S) model with Exponential distribution of failure-free operating time at each of a finite number of machines and Exponential distribution of re-supply lead-time is developed. A graphical aid is presented which, for a given number of machines, indicates the range of the ratio {mean lead-time/mean failure-free operating time} for which a minimumSis required in order to satisfy a service level constraint on the service measure Pr[a spare is available at a machine stoppage due to part failure].

ISSN:0160-5682    

DOI:10.1057/jors.1996.157

出版商:Taylor&Francis    

年代:1996

数据来源: Taylor

摘要:

AbstractTraditional approaches to stochastic resource allocation problems (including the classical multi-armed bandit problems) have usually made use of dynamic programming (DP) methodology, perhaps buttressed by furtherad hocarguments. While such approaches seem‘natural’they have usually proved technically very difficult. Bertsimas and Niño-Mora have recently given a radically new account of many important results in this area which relate to Gittins indices. The key to their approach is in the characterisation of the region of achievable performance. The optimisation problems of interest are then solved as linear programs over this region. Here we exploit elements within the Bertsimas and Niño-Mora framework (in particular, its capacity to give formulae for the total return of a given policy in closed form) to obtain (i) a simple dynamic programming proof of the optimality of Gittins index policies and (ii) a range of index-based suboptimality bounds for general policies for a variety of stochastic models for resource allocation.

ISSN:0160-5682    

DOI:10.1057/jors.1996.158

出版商:Taylor&Francis    

年代:1996

数据来源: Taylor