Workshop on Models and Algorithms
for Planning and Scheduling Problems

Queens' College, Cambridge, UK

April 7-11, 1997

picture of QUEENS' COLLEGE

This is an announcement for the

Third Workshop on Models and Algorithms for Planning and Scheduling Problems

Copy of the brochure which will be mailed out (200 K).

The first workshop was held at Lake Como, Italy, in 1993, and a second in Wernigerode, Germany, in 1995. The third workshop is planned for Cambridge, England in 1997. The workshop aims to provide a forum for scientific exchange and cooperation in the field of planning, scheduling and related areas. To maintain the informality of the previous workshops and to encourage discussion and cooperation, there will be a limit of 80 participants and a single stream of presentations.

The workshop has sponsorship from the London Mathematical Society and from the EPSRC. This sponsorship can help support EPSRC and other students who wish to attend the workshop.

Contributions on any aspect of scheduling are welcome. The invited speakers will particularly emphasise the topics of

- analysis of approximation algorithms
- local search
- scheduling of modern manufacturing systems
- stochastic scheduling

The workshop will start with lunch, at 12.30 on Monday and in the morning on Friday. It includes an excursion on Wednesday afternoon and a feast in the mediaeval hall on Thursday evening.

Authors presenting papers at the workshop are invited to submit their manuscripts for possible publication in a special issue of Annals of Operations Research. Papers for this special issue will be refereed in the normal way.

EPSRC Student Funding

Funds have now been made available from the MATHFIT initiative to subsidize student participation in workshop. MATHFIT - Mathematics for IT - is a programme jointly sponsored by the EPSRC and LMS (the London Mathematical Society). We can cover the equivalent of 50% of the registration and accommodation fee for six EPSRC students. So, if you are an EPSRC student, scheduling is your area of research, and you were restrained from applying earlier for lack of funding, then here is your chance!

Students have until 17 February to register for the workshop.


The city of Cambridge is without doubt one of the most beautiful cities in Britain and has captivated countless visitors with its magnificent historic buildings, its elegant bridges, manicured lawns and open parks along the River Cam and the wide variety of architectural styles that are to be found in its college courtyards and chapels.

Originally a Roman Settlement, the growth of Cambridge began in the 5th century, when it began to prosper as a market town and as a trading route between eastern and Central England. By the beginning of the 13th Century the religious orders that had settled in and around the city began to attract scholars and in 1284 the first college, Peterhouse, was founded by the Bishop of Ely. Today the university comprises a total of 32 colleges, each a separate self governing body and each with its own architectural Style and Character. Among the most beautiful are Queens', Trinity, St. John's, Clare and King's.

In recent years there has been a rapid and sustained growth of high-tech firms working at the forefront of technologies such as computing, biotechnology, electronics and telecommunications, and benefiting from close links with the University. This growth is often referred to as the "Cambridge phenomenon".

See here for further tourist information about Cambridge.

Additional tourist information for Cambridge will be available at registration.

Accommodation / Queens' College

The workshop will take place in Queens' College.

Founded in 1448 by Margaret of Anjou, `to laud and honneure of sexe femenine', Queens' has been called `the most complete and compact example of a mediaeval College at Cambridge'. With its mellow red brick, arched windows, setting on the backs of the river Cam, and buildings from each of the last six centuries, the college is a pleasant setting for an intimate workshop.

Accommodation will be in the modern Cripp's Court. Bed and breakfast, with optional lunch, is available for spouses, and double rooms can be provided by request. Bed and breakfast is available for Friday and Saturday nights for persons who want to stay on in Cambridge after the workshop. Please contact Richard Weber if you require any of these extras.


The accommodation fee is 215 pounds. This includes four nights' lodging, lunches Monday-Thursday, breakfasts Tuesday-Friday, coffee and tea each morning and afternoon, and the workshop banquet on Thursday evening.

The registration fee is 80 pounds and covers the reception on Monday evening, and an excursion Wednesday afternoon.

Details of payment method will be advised with acceptance notification in January. Full payment of accommodation and registration (295 pounds) is required by February 17, although late registration will be considered, subject to available space, for an increased registration fee of 120 pounds.

Travel Information

Travel information is the same at that for reaching the Statistical Laboratory in Cambridge.

Queens' College is located on the opposite side of Silver Street to the Department of Pure Mathematics and Mathematical Statistics, as marked in the upper left hand corner of this map of Cambridge, which also shows the relative locations of the coach and train stations.


M. A. H. Dempster, University of Cambridge
C. A. Glass, University of Southampton
C. N. Potts, University of Southampton
V. A. Stusevich, University of Greenwich
F. Vanderbeck, University of Cambridge
R. R. Weber, University of Cambridge

Invited Speakers

Y. J. Crama, University of Liege, Belgium
K. Glazebrook, University of Newcastle, UK
D. S. Johnson, AT&T Bell Laboratories, USA
J. K. Lenstra, Technical University of Eindhoven, The Netherlands
D. B. Shmoys, Cornell University, USA


The following talks will be presented:

A. Agnetis. Scheduling Problems in Robotic Cells with Limited Intermediate Storage

C. Artigues, F. Roubellat. Multi-Resource Shop Scheduling with Sequence Dependent Setup Times

P. Baptiste. Deduction Rules for Cumulative Scheduling

H. Braesel, M. Harborth, P. Willenius. On the Hardness of the Classical Job-Shop Problem

P. Brucker, S. Knust, A. Schoo, O. Thiele. A Branch & Bound Algorithm for the Resource-Constrained Project Scheduling Problem

B. Chen, A. P. Vestjens, G. J. Woeginger. On-line Scheduling of Two-Machine Open Shops where Jobs Arrive Over Time

E. Collingwood, P. Ross. A Genetic Algorithm for Scheduling Chicken Catching

Y. Crama. Production Planning in Printed Circuit Board Assembly

S. Dauzere-Peres. Some New Results on Minimizing Late Jobs in One-Machine Scheduling

J. M. V. de Carvalho. Integer Variable Sized Bin-Packing Problems

M. Dell'Amico, L. Finta. A Lnear Time Algorithm for Three-Processor Scheduling with Communication Delays

F. Della Croce, R. Tadei, P. Asioli. Scheduling a Tennis Tournament with Courts Usage Optimization

I. G. Drobouchevitch, V.A. Strusevich. The Two-Stage Multi-Machine Open Shop with a Bottleneck Machine

A. Gerodimos, C. A. Glass, C. N. Potts, T. Tautenhahn. Scheduling Multi-Operation Jobs on a Single Machine

K. D. Glazebrook, R. Garbe, J. Nino-Mora. Almost Optimal Policies for Stochastic Systems Which Almost Satisfy Conservation Laws

V. S. Gordon, E. Potapneva, F. Werner. Single Machine Scheduling to Minimize the Weighted Number of Late Jobs With Deadlines, Release and Due Dates

C. Gueret, C. Prins. A New Lower Bound for the Open-Shop Problem

J. N. D. Gupta, A. M. A. Hariri, C. N. Potts. Single Machine Scheduling to Minimize Maximum Tardiness with Minimum Number of Tardy Jobs

M. Harborth. Sequence Graph Isomorphism

S. Heipcke, Y. Colombani. A New Constraint Programming Approach to Large Scale Resource Constrained Scheduling

J. A. Hoogeveen, M. van den Akker, S.L. van de Velde. Parallel Machine Scheduling by Column Generation

J. Hurink, P. Brucker, W. Kubiak. Scheduling Jobs with Unit Processing Requirements and Chain Precedences on Two Uniform Machines

C. A. J. Hurkens. Large Scale Periodic Scheduling

A. S. Jain, S. Meeran. Local Search Methods for the Job-Shop: the State-of-the-Art

K. Jansen. Approximation Results for the Optimum Cost Chromatic Partition Problem

D. S. Johnson. The Asymmetric Traveling Salesman Problem: Algorithms and Applications

H. Kellerer. A 5/4 Linear Time Bin Packing Algorithm

S. Knust. Shop Problems with Transportation Times

A. Kononov. Complexity of Scheduling Problems with the Time-Dependent Processing Times

T.-C. Lai. Analysis of Approximation Algorithms for Single Machine Problem with Release Dates

J. K. Lenstra. Computing Near-Optimal Schedules

B. L. MacCarthy. How Do Humans Plan and Schedule?

R. H. Mohring, M. W. Schaffter, A. S. Schulz. Approximation Algorithms for Scheduling Problems with Communication Delays

E. G. Negenman. Local Search Algorithms for the Multiprocessor Flow Shop Scheduling Problem

K. Neumann. Job Shop Scheduling with Stochastic Precedence Constraints

J. Nino-Mora, K.D. Glazebrook. Scheduling Multiclass Qeueing Networks: Performance Analysis of Static Priority Policies

L. Peridy, J. Carlier, E. Pinson, D. Rivreau. Elimination Rules for Disjunctive Scheduling Problem: Some General Tools

U. Pferschy, H. Kellerer. Cardinality Constrained Bin-Packing Problems

A.S. Schulz, M. Skutella. Randomization in LP-Based Scheduling: Approximations for the Average Weighted Completion Time

P. Serafini, G. Lancia, F. Rinaldi. Improving Algorithms for Periodic Scheduling

S. Sevastianov, A. Kononov, I. Tchernykh. Polynomially Solvable Classes of the Open Shop Problem on the Base of Different Machine Loads

Y. M. Shafransky. On Some Contradictions in Theory of Computational Complexity

N. V. Shakhlevich, Y. N. Sotskov, F. Werner. The Complexity of Mixed Shop Scheduling Problems

D. B. Shmoys. Approximation Algorithms for Scheduling Problems via Linear Programming and Randomization

M. G. Speranza, P. Dell'Olmo, R. Pedrini. Approximation Algorithms for Partitioning Items in Unequal Bins to Minimize the Total Size

T. Tautenhahn, M. Harborth, P. Willenius. On the Set of Solutions of an Open Shop Problem

S. L. van de Velde, J. A. Hoogeveen. Linear Programming Bounds for Flow Shop Scheduling Problems

J. I. van Zante - de Fokkert, T. G. de Kok. The Simultaneous Determination of the Assignment of Items to Resources, the Cycle Times, and the Reorder Intervals in Repetitive PCB Assembly

G. Wambach, R. Schrader. The Setup Polyhedron of N-Sparse Posets

R. Wegner. Recovering Cyclic Schedules from Delay

G. Weiss. An Algorithm for Optimal Draining of Fluid Re-entrant Lines

M. Wennink, R. Rudolf. Modeling and Solving Shop Scheduling Problems with Resource Constraints

G. J. Woeginger. Polynomial Time Approximation Schemes for Scheduling Problems

Participants' emails

          de Carvalho 
          Della Croce 
          Dell Amico 
          Harborth Martin.Harborth@Student.Uni-Magdeburg.DE 
          Jones  Jones_G@FS107.NPT.NUWC.NAVY.MIL
          Nino Mora 
          Schols 100430.250@CompuServe.COM 
          van Zante-de Fokkert 
          van de Velde 


April 7, 1997
Start with lunch at 12.30pm

April 7-11, 1997

 8.00- 9.00 breakfast
 9.00-10.40 sessions
10.40-11.10 coffee
11.10- 1.00 sessions
 1.00- 2.30 lunch
 2.30- 4.10 sessions (not Wednesday)
 4.10- 4.40 tea
 4.40- 6.20 sessions (not Wednesday)
 7.0        reception and dinner/banquet (Monday and Thursday)
April 11, 1997
Departure before lunch

June 20, 1997
Deadline for submission of papers to special issue of Annals of Operations Research