The basic cyclic scheduling problem with deadlines

The purpose of this paper is to study the latest schedule existence, calculation and properties of a basic cyclic scheduling problem with deadlines. First it is shown that, in the general case, a latest schedule exists but may be difficult to compute. Then we focus on a special case we call the optimal cyclic production problem. We derive an upper bound for the number of maximal-path values needed to compute the latest starting times and show the K-periodic structure of the latest starting time sequences.     

Computing latest starting times of activities in interval-valued networks with minimal time lags

This paper deals with problems of determining possible values of earliest and latest starting times of an activity in networks with minimal time lags and imprecise durations that are represented by means of interval or fuzzy numbers. Although minimal time lags are practical in different projects, former researchers have not considered these problems.After proposing propositions which reduce the search space, a novel polynomial algorithm is presented to compute intervals of possible values of latest starting times in interval-valued networks with minimal time lags. Then, the results are extended to networks with fuzzy durations.     

Characterizing the set of feasible sequences for n jobs to be carried out on a single machine

This paper deals with the problem of the scheduling of jobs on a single machine presented in terms of decision-aid. This leads to determining the characteristics of the set of schedules which are compatible with the earliest starting times and the latest finishing times of the jobs.A theorem, which enables the determination of the necessary and sufficient conditions for the feasibility of jobs sequences, is proposed. From this basis, an iterative procedure is presented which permits to define the characteristics of the feasible schedules. A Boolean model is used to represent and handle the conditions of feasibility of the schedules.     

A new approach to find project characteristics and multiple possible critical paths in a fuzzy project network

Graphs are widely used to represent data and relationships. Among all graphs, a particularly useful family is the family of trees. In this paper, we utilize a rooted tree to describe a fuzzy project network as it enables simplification in finding earliest starting times and trapezoidal fuzzy numbers to express the operation times for all activities in project network. As there is an increasing demand that the decision maker needs “Multiple possible critical paths” to decrease the decision risk for project management, in this paper, we introduce an effective graphical method to compute project characteristics such as total float, earliest and latest times of activities in fuzzy project network and a new ranking to find possible critical paths. Numerical example is provided to explain the proposed procedure in detail; the results have shown that the procedure is very useful and flexible in finding total floats. By comparing the critical paths obtained by this method with the previous methods, it is shown that the proposed method is effective in finding possible critical paths.     

Labour scheduling at an airport refuelling installation

We have developed an automatic assignment procedure for labour scheduling at a continously operating airport refuelling installation. Different types of workers are subject to different conditions on the shifts they can do (morning, evening or night), shift lengths, days-off, holidays, terms of contract and working hours. The scheduling process is carried out on a weekly basis, but there are mid-term and long-term conditions and objectives which link each week with the preceding and following weeks. Our package uses firstly a tabu search algorithm to find the best schemes of shifts/days-off to be used to cover the requirements. Secondly, an assignment problem is solved to match the schemes with available workers. Finally, the starting and finishing times for each working day are determined for each worker. The system has been designed to run on a personal computer and gives good quality solutions in very short computing times.     

A priority list based heuristic for the job shop problem

A priority list for the job shop scheduling problem is defined to be any permutation of a set of symbols where the symbol for each job appears as many times as the number of its operations. Every priority list can be associated in a natural way with a feasible schedule, and every feasible schedule arises in this way. Priority lists are therefore a representation of feasible schedules that avoid the problems normally associated with schedule infeasibility. As a result, the three ingredients of local search heuristics, namely picking initial starting schedules, constructing search neighbourhoods and computing makespans, become faster and easier when performed in the space of priority lists rather than in the space of feasible schedules. As an illustration of their usefulness, a priority list based simulated annealing heuristic is presented, which, although simple, is competitive with the current leading schedule based simulated annealing and tabu search heuristics.     

Parallel algorithms for analyzing activity networks

Parallel algorithms for analyzing activity networks are proposed which include feasibility test, topological ordering of the events, and computing the earliest and latest start times for all activities and hence identification of the critical activities of the activity network. The first two algorithms haveO(logn) time complexity and the remaining one achievesO(logd log logn) time bound, whered is the diameter of the digraph representing the activity network withn nodes. All these algorithms work on a CRCW PRAM and requireO(n ³) processors.     

Computing eigenvectors of block tridiagonal matrices based on twisted block factorizations

New methods for computing eigenvectors of symmetric block tridiagonal matrices based on twisted block factorizations are explored. The relation of the block where two twisted factorizations meet to an eigenvector of the block tridiagonal matrix is reviewed. Based on this, several new algorithmic strategies for computing the eigenvector efficiently are motivated and designed. The underlying idea is to determine a good starting vector for an inverse iteration process from the twisted block factorizations such that a good eigenvector approximation can be computed with a single step of inverse iteration.     

Improved vehicle scheduling in public transport through systematic changes in the time-table

Vehicle scheduling for a fixed time-table is easy to formulate and solve as a minimal-cost-flow problem. Normally, however, there is considerable flexibility in the time-table. We propose here a method for exploiting this flexibility in order to improve the vehicle scheduling.A given set of trips must be assigned to a fleet of identical vehicles, starting from a common garage. Each trip is characterized by initial stop, final stop, duration, earliest departure time, and latest departure time.The problem is to decide which vehicle should be assigned to each individual trip and when the trip should start, so that a generalized cost is minimized.The minimum-cost-flow problem is first solved for the ‘kernels’ of every trip in order to make clear when the critical time-periods occur and obtain a lower bound for the solution. The kernel is defined as a trip that starts at the latest possible departure time and finishes at the earliest possible arriving time.The departure time for each trip is then chosen, thereby increasing the chances of obtaining a good schedule. The minimum-cost-flow problem is then solved for this fixed time-table.Finally, the departure times for each vehicle are adjusted (blocked) so that each vehicle (and driver) is efficiently used. This method is used as an integral part of the Volvo Traffic Planning Package.     

Fast elliptic curve point multiplication based on binary and binary non-adjacent scalar form methods

This article presents two methods for developing algorithms of computing scalar multiplication in groups of points on an elliptic curve over finite fields. Two new effective algorithms have been presented: one of them is based on a binary Non-Adjacent Form of scalar representation and another one on a binary of scalar representation method. All algorithms were developed based on simple and composite operations with point and also based on affine and Jacobi coordinates systems taking into account the latest achievements in computing cost reduction. Theorems concerning their computational complexity are formulated and proved for these new algorithms. In the end of this article comparative analysis of both new algorithms among themselves and previously known algorithms are represented.     

A starting method for the numerical solution of Volterra's integral equation of the second kind

The acquisition of starting values is one of the chief difficulties encountered in computing a numerical solution of Volterra's integral equation of the second kind by a multi-step method. The object of this note is to present a procedure which is derived from certain quadrature formulas and which provides these starting values, to provide a sufficient condition for the approximate solution to be unique, to bound the approximate solution and the error, and to give a numerical example.     

Facilitating analysis of Monte Carlo dense matrix inversion algorithm scaling behaviour through simulation

With the latest developments in the area of advanced computer architectures, we are already seeing large-scale machines at petascale level and are faced with the exascale computing challenge. All these require scalability at system, algorithmic and mathematical model levels. In particular, efficient scalable algorithms are required to bridge the performance gap. Being able to predict application demeanour, performance and scalability of currently used software on new supercomputers of different architectures, varying sizes, and utilising distinct ways of intercommunication, can be of great benefit for researchers as well as application developers. This paper is concerned with scaling characteristics of Monte Carlo based algorithms for matrix inversion. The algorithmic behaviour on both, a shared memory and a large-scale cluster system will be predicted with the help of an extreme-scale high-performance computing (HPC) simulator.     

Eine Formel von Wronski und ihre Bedeutung für den Quotienten-Differenzen-Algorithmus

Summary In [3], paragraph 6, the author showed how to find the zeros of a polynomial with the aid of the QD-Algorithm. The method required a certain rational function to be developed into a continued fraction of Stieltjes type to give the starting values for the QD-Algorithm. In the present paper the author shows how starting values can be obtainedwithout computing a continued fraction.     

Dynamic lot-sizing problem with demand time windows and container-based transportation cost

In this paper, we study the dynamic lot-sizing problem with demand time windows and container-based transportation cost. For each particular demand, there are corresponding earliest and latest times, and the duration between such earliest and latest times is the demand time window. If a demand is satisfied by a delivery within demand time window, then there is no holding or backlogging cost incurred. Our purpose is to satisfy demand at a minimum total cost, including setup cost, procurement cost, container cost, and inventory holding cost. This research is supported in part by Hong Kong RGC grant HKUST 6010/02E and NUS ARF grant R-266-000-019-112.     

An integrated approach to shift-starting time selection and tour-schedule construction

A common practice in personnel tour scheduling is to limit the number of permissible daily shift starting times. Accordingly, an important subproblem that arises in tour-scheduling problems is the selection of those starting times that are conducive to efficient satisfaction of labour requirements. A previously published heuristic for this problem is sequential in nature, whereby a subset of starting times is selected in the first stage and tours are constructed using the chosen starting times in the second stage. We propose an integrative procedure that overcomes many of the limitations inherent in the sequential approach. Our procedure, which uses tabu search for starting time selection and a cutting plane method for tour construction, was compared to integer programming and the previously published heuristic in two experiments using test conditions from the airport staffing literature. Although all methods performed well when the labour requirement patterns were consistent across days of the week, the new procedure yielded the best performance when such patterns were inconsistent.     

The multi-armed bandit, with constraints

Presented in this paper is a self-contained analysis of a Markov decision problem that is known as the multi-armed bandit. The analysis covers the cases of linear and exponential utility functions. The optimal policy is shown to have a simple and easily-implemented form. Procedures for computing such a policy are presented, as are procedures for computing the expected utility that it earns, given any starting state. For the case of linear utility, constraints that link the bandits are introduced, and the constrained optimization problem is solved via column generation. The methodology is novel in several respects, which include the use of elementary row operations to simplify arguments.     

Exponential lower bounds for finding Brouwer fix points

The computation of Brouwer fixed points is a central tool in economic modeling. Although there have been several algorithms for computing a fixed point of a Brouwer map, starting with Scarf's algorithm of 1965, the question of worst-case complexity was not addressed. It has been conjectured that Scarf's algorithm has typical behavior that is polynomial in the dimension. Here we show that any algorithm for computing the Brouwer fixed point of a function based on function evaluations (a class that includes all known general purpose algorithms) must in the worst case perform a number of function evaluations that is exponential in both the number of digits of accuracy and the dimension. Our lower bounds are very close to the known upper bounds.     

An unconditionally convergent method for computing zeros of splines and polynomials

We present a simple and efficient method for computing zeros of spline functions. The method exploits the close relationship between a spline and its control polygon and is based on repeated knot insertion. Like Newton's method it is quadratically convergent, but the new method overcomes the principal problem with Newton's method in that it always converges and no starting value needs to be supplied by the user.

     

带强制工期的双机开放车间排序问题

讨论了强制工期相等的n个工件在双机开放车间加工.在允许机器空闲的条件下,寻找一个工件排序,使得最大提前完工时间最小.由于工件不允许延迟,同题可能会无可行排序.先讨论了问题的可行性.如果问题可行,找出一个可行序列作为预排序列,并提出了一个算法计算每个工件尽可能迟的开工时间.而后,提出了一个多项式时间最优算法,在预排序列的基础上,通过调整两台机器上最先加工的工件来获得最优排序.     

The significance of reducing setup times/setup costs

Scheduling with setup times or setup costs plays a crucial role in todays modern manufacturing and service environments where reliable products/services are to be delivered on time. Scheduling activities profoundly depend on the times/costs required to prepare the facility for performing the activities. However, the vast majority of existing scheduling literature ignores this fact. We define and emphasize the importance, applications, and benefits of explicitly considering setup times/costs in scheduling research. Moreover, a review of the latest research on scheduling problems with setup times/costs is provided.