A Remark on the Computation of Optimum Media Schedules

The media scheduling problem of Ellis is transformed into an integer linear programming problem in zero-one variables. The transformed problem is recognized as the knapsack problem and exact and approximate algorithms are proposed.     

Building up a Sequence of Optimum Media Schedules

A mathematical model is proposed for finding the response to an advertising campaign. Although, hypothetically, there is no restriction on the media involved, the assumptions made are more suited to a campaign in newspapers or magazines, rather than, for example, on television. The deficiencies in the model are discussed, and the use of such a model is compared with the use of simulation techniques. Two previous attempts to optimize similar models are discussed, and a technique for building up a sequence of optimum schedules with an example and a proof of the optimum properties are presented.     

A Simple Dynamic Method for Obtaining Inspection Schedules

A method for obtaining inspection schedules is proposed for situations where it is difficult to quantify the costs associated with inspections and undetected failure, or when these costs vary in time. After each inspection, the next inspection is scheduled so that there is only a small, specified probability that a failure goes undetected for longer than a specified time. Some properties of the inspection times are derived, and numerical illustrations are given for some particular cases.     

车间作业调度的可行化判定及不可行解的纠正

生产调度过程中出现不可行解是调度研究经常遇到的问题之一.提出了对JSP调度方案进行可行化判定和纠正不可行解的可行算子,算子包括了基于有向图拓扑排序原理对车间作业调度方案进行可行判定的方法和将不可行解纠正为可行解的算法.证明了该纠正算法总能成功,并对算子的功能进行了拓展使之还可应用于不完备调度.最后讨论了可行算子的特点、时间效率和应用前景.     

A System Dynamics Model of Submarine Operations and Maintenance Schedules

The extent to which a proposed military force will achieve operational objectives is a prime concern of defence planners. This paper discusses the problem in the context of the exercise of sea power in distant waters and shows that a model of the whole problem would require a feedback analysis, for which an appropriate approach would be system dynamics. Such models have, in general, been continuous, but ships are discrete objects. The paper therefore addresses the construction of discrete system dynamics models as the basis for a model of the whole problem. Two models of a submarine force are presented. The first deals with the construction and major refit programmes, to evaluate the periods of fleet service availability achievable from a submarine force of a given size. The second examines unit usage during periods of fleet service.     

Generating Acceptable Shift-Working Schedules

When a factory operates a shift system of working, the work patterns are usually laid down at the start and adhered to for long periods. In this case study, small out-stations with frequent changes in manning require the frequent generation of new schedules. Producing and agreeing such schedules with the workforce can be a fraught and time-consuming task. Hence a computer routine was devised which takes over the generation. An interesting feature is that several feasible routines are generated, allowing the final decision to be taken by the workforce itself.     

A Heuristic Tree-search Method of Selecting Face Schedules at a Colliery

In the course of work on developing a planning system covering several levels of operations the problem has arisen of selecting the best schedule of coal faces and methods of work on them over an 18-month period at a colliery. A colliery has a number of faces which can come into operation at any time and in any order. The time at which faces are replaced depends on the time taken to work these out which, in turn, depends on the method of work used. A number of methods can be used on each face producing different results, and using different amounts of resources.Since the method would be used as a routine for a large number of collieries, an empirical near-optimum approach has been used which uses a mixture of heuristics, integer programming and search through a decision-tree.A computer program has been used successfully and is now being introduced for routine use.     

自由作业稠密时间表的性质研究

稠密时间表作为自由作业问题的近似解,其加工总长与最优值之比具有上界2-1/m(m为机器数),是一个尚未证明的猜想.利用组合方法证明了稠密时间表性能比猜想成立的一个充分条件.利用该条件及有关文献的结果,给出了机器数不超过7的自由作业稠密时间表性能比猜想的证明.     

工件有到达时间的两机器自由作业稠密时间表

对于两机器自由作业加工总长问题，工件带有到达时间，我们证明了稠密时间表的性能比为1.5。     

Reliability Characteristics of Alternative Checkup Schedules for Detecting Hidden Failures

We consider a group of N identical objects (machines, etc.) working in similar conditions. In a certain important part of these objects, a specific failure may appear. It has a hidden nature and can be revealed only during special examination (checkup). A schedule for carrying out these checks is fixed in advance. When the failure is revealed for the first time in some object, special reinforcement measures are taken for all functioning objects in order to eliminate the appearance of this failure in the future. Each checkup schedule can be characterized by several reliability indices such as probability of discovering the failure before a certain time, expected time of failure detection, expected time of operation with a hidden failure, etc. We present formulae for computing all of these indices, for a general type schedule, and compare numerically two types of schedules: one when all items undergo the checkup at the same time and the second in which the checkup times are different for different items (by preserving the same checkup frequency). We demonstrate that under certain circumstances, such as N being large, the second type schedules have better reliability indices.     

Nondominated Schedules for a Job-Shop with Two Competing Users

We consider the scenario where two users compete to perform their respective jobs on a common set of resources. The job for each user has a due-date and the cost function associated with the due-date is quasi-convex (i.e., it has a single local minimum). We characterize the set of nondominated schedules over which the users may negotiate and develop a polynomial algorithm to find this nondominated set.     

An Algorithm for Selecting Quantity Discounts from Realistic Schedules

Consideration of bounds, discontinuities and the integrality of decision variables is often helpful for responding to many practical requirements. Using the case of quantity discounting as an example, it is shown why the above considerations add realism to a model, and how they may be incorporated in the solution procedure. The bounds on the order quantity are fulfilled by establishing suitable stopping rules, while gaps in order quantities are resolved by modifying the input data. As for integrality, a result is established which shows that the feasible points for the integer optimum can be obtained by suitably rounding those for the continuous optimum. A comprehensive algorithm containing these features is proposed, and analytical proofs of the results are included.     

An Integrated Framework for Generating and Revising Factory Schedules

Practical solutions to the production scheduling problem must provide two broad capabilities:

1. i)
   an ability to efficiently generate schedules that reflect the actual constraints and objectives of the manufacturing environment, and
    
2. ii)
   an ability to incrementally revise these schedules over time in response to unexpected executional circumstances. In this paper, we advocate a common view of predictive and reactive scheduling as an incremental problem solving process that is opportunistically focused by characteristics of the current solution constraints.
    

We describe the architecture of OPIS (opportunistic intelligent scheduler), which defines a general framework for configuring scheduling systems according to this view. We then examine the scheduling knowledge (e.g. analysis and scheduling methods, schedule generation or revision strategies) that is exploited within this architecture by the current OPIS scheduler. Experimental studies with the OPIS scheduler have demonstrated the potential of this constraint-directed scheduling methodology in both predictive and reactive scheduling contexts.     

An Integer Multicommodity Flow Model Applied to the Rerostering of Nurse Schedules

The problem of rerostering service schedules is very common in organizations that work shifts around the clock every day of the year with a set number of employees. Whenever one or more workers announce that they will not be able to attend to tasks previously assigned in their schedule, those tasks must be performed at the expense of alterations in the schedules of other workers. These changes should not conflict with the rules laid down by the administration and employment contracts and should affect the previous schedules as little as possible. This is a difficult real problem calling for a computational tool to cope with it easily. In the paper the issue is described in detail in the context of nurse scheduling and formulated as an integer multicommodity flow problem with additional constraints, in a multi-level acyclical network. A heuristic was implemented as a first approach to solving the problem. Subsequently the integer linear programming formulation of the multicommodity flow model and two linear relaxations were tested using CPLEX [2] optimizers. The computational results reported regard real instances from a Lisbon state hospital. Satisfactory rosters were obtained within acceptable computational times in all instances tested, either with the integer optimizer, or with the heuristic. This being so, refinements will be undertaken to embed these methodologies in a decision support system that may assist the head nurse in her daily rerostering activities.     

A Canonical Diffraction Problem With Two Media

A Wiener–Hopf equation in L² being equivalent [5] to a boundary value problem (of the first kind) for a wave-scattering Sommerfeld half-plane Σ=ℝ₊×{0} which faces two different media Ω_-: x₂<0, Ω₊: x₂>0, as a special configuration in [3], is solved by canonical Weiner–Hopf factorization of its L²-regular scalar symbol γ_o=γ_o- γ_o+. The factors are calculated by solving a Riemann–Hilbert boundary value problem on the semi-infinite branch cuts of t_j(ξ):=(ξ²−k²_j)^1/2, k_j∈ℂ⁺⁺ for j=1,2: taken parallel to the imaginary axis. The procedure following this idea is known as the Wiener–Hopf–Hilbert(–Hurd) method [2] and requires the evaluation of elliptic-type integrals. Formula (3.7) seems not to be contained in tables of integrals.     

The Design of Routes,Service Frequencies,and Schedules for a Municipal Bus Undertaking: A Case Study

This paper describes a case study of the reorganization of a municipal bus undertaking. The terms of reference were to consider reorganizing the route structure, to advise on frequencies to operate on the chosen routes, to compile timetables, and to design bus schedules so that the recommended system could be implemented with the minimum number of active buses. Theoretically, all of these variables can interact and one global model should be used to optimize the entire system simultaneously. In practice, the components of this problem had to be uncoupled and tackled separately. An heuristic model designed to provide a "good" route network was developed. Service frequencies were allocated to routes so that a measure of service to passengers was maximized. Bus timetables were compiled using conventional methods and a linear programming model used to assign individual buses to journeys. A new scheme based on the recommendations of the study has been implemented. It is expected that it will reduce the annual operating deficit by [pound]35,000 without appreciably decreasing the overall level of service offered.     

Queueing Networks of Random Link Topology: Stationary Dynamics of Maximal Throughput Schedules

In this paper, we study the stationary dynamics of a processing system comprised of several parallel queues and a single server of constant rate. The connectivity of the server to each queue is randomly modulated, taking values 1 (connected) or 0 (severed). At any given time, only the currently connected queues may receive service. A key issue is how to schedule the server on the connected queues in order to maximize the system throughput. We investigate two dynamic schedules, which are shown to stabilize the system under the highest possible traffic load, by scheduling the server on the connected queue of maximum backlog (workload or job number). They are analyzed under stationary ergodic traffic flows and connectivity modulation. The results also extend to the more general case of random server rate.We then investigate the dynamics of acyclic (feed-forward) queueing networks with nodes of the previous type. Their links (connectivities) are stochastically modulated, inducing fluctuating network topologies. We focus on the issue of network throughput and show that it is maximized by simple node server schedules. Rate ergodicity of the traffic flows traversing the network is established, allowing the computation of the maximal throughput.Queueing networks of random topology model several practical systems with unreliable service, including wireless communication networks with extraneous interference, flexible manufacturing systems with failing components, production management under random availability of resources etc.Research supported in part by the National Science Foundation.This revised version was published online in June 2005 with corrected coverdate