UBC Theses and Dissertations

UBC Theses Logo

UBC Theses and Dissertations

The operator scheduling for Singapore mass transit system Goh, Lek-Oon 1984

Your browser doesn't seem to have a PDF viewer, please download the PDF to view this item.

Item Metadata

Download

Media
831-UBC_1984_A4_6 G63.pdf [ 4.73MB ]
Metadata
JSON: 831-1.0096023.json
JSON-LD: 831-1.0096023-ld.json
RDF/XML (Pretty): 831-1.0096023-rdf.xml
RDF/JSON: 831-1.0096023-rdf.json
Turtle: 831-1.0096023-turtle.txt
N-Triples: 831-1.0096023-rdf-ntriples.txt
Original Record: 831-1.0096023-source.json
Full Text
831-1.0096023-fulltext.txt
Citation
831-1.0096023.ris

Full Text

9$  ; THE OPERATOR SCHEDULING FOR SINGAPORE MASS TRANSIT SYSTEM by LEK-OON|GOH B.Sc,  Babson C o l l e g e M a s s a c h u s e t t s , 1 981  A THESIS SUBMITTED IN PARTIAL FULFILMENT OF THE REQUIREMENTS FOR THE DEGREE OF MASTER OF SCIENCE In Business Administration in THE FACULTY OF GRADUATE STUDIES lr.  SacultyK:  Of Commerce And B u s i n e s s A d m i n i s t r a t i o n  We accept t h i s t h e s i s as conforming t o the r e q u i r e d s t a n d a r d  THE UNIVERSITY OF BRITISH COLUMBIA May 1984  ©  Lek-Oon Goh, 1984  In p r e s e n t i n g requirements  this thesis f o r an  of  British  it  freely available  agree t h a t for  Library  shall  for reference  and  study.  I  f o r extensive copying of  h i s or  her  copying or  f i n a n c i a l gain  be  shall  g r a n t e d by  not  be  of  The U n i v e r s i t y o f B r i t i s h 1956 Main Mall V a n c o u v e r , Canada V6T 1Y3  DE-6  (3/81)  of  Columbia  make  further this  thesis  head o f  this  my  It is thesis  a l l o w e d w i t h o u t my  permission.  Department  the  representatives. publication  the  University  the  s c h o l a r l y p u r p o s e s may  understood that  the  I agree that  permission by  f u l f i l m e n t of  advanced degree a t  Columbia,  department or for  in partial  written  i i  ABSTRACT  This paper presents a mathematical formulation of the train operator scheduling problem in a Mass Rapid Transit System. Integer programs (IP) with 0-1 constraints matrices arise frequently in scheduling and staffing methods. The formulation of the train operator scheduling problem a as set-partitioning or set-covering integer program gives rise to IP problems with excessive size and computational complexity. Subproblems of the original problem can however be solved by relaxing the integer program to an LP and introducing some heuristics to round off the fractional parts of the solution. Near optimal solutions to these problems can be found and can be easily implemented using reasonable computing resources. The method is demonstrated on the original data given by the Provisional Mass Rapid Transit Authority of Singapore and on several other variations of the data set The results compare favorably with other methods in computational efficiency.  i i  i i i  Table of Contents Chapter 1 INTRODUCTION 2 STAFF SCHEDULING PROBLEMS 2.1 Basic Structure of a Transit System 2.2 Review of Literature 2.2.1 Run Cutting Approaches 2.2.2 Service Profile Decompositions Algorithm 2.2.3 A Matching Based Algorithm 2.3 The Daily Scheduling Problem 2.4 The Days-off Scheduling Problem 2.5 The Singapore Mass Rapid Transit System 2.5.1 Operating Conditions 2.5.2 Daily Shift Specifications 2.5.3 Bi-weekly Roster Specifications 3 DAILY SCHEDULING PROBLEM 3.1 Statement of the Problem 3.2 A Set Partitioning Formulation 3.3 A Set Covering Formulation 3.3.1 Crew Requirement in Daily Shift Scheduling 3.4 Set Covering Formulation vs Set Partitioning Formulation 3.5 Solving the Set Covering Problem 3.6 Some Heuristics 3.6.1 Round-Up Heuristic 3.6.2 Set Covering Heuristic 3.6.3 Zero-One Integer Programming Heuristic : 3.7 Generating Feasible Daily Schedules 4 DAYS-OFF SCHEDULING 4.1 Introduction , 4.2 Requirements for the Days-off Problem 4.3 Formulation of the Days-off Problem 4.4 Generating Feasible Bi-weekly Rosters 5 PRELIMINARY IMPLEMENTATION 5.1 The Use of a Matrix Generator 5.2 Conversion Program 5.3 Results for the Daily Scheduling Problem 5.3.1 The Linear Programming Relaxation Solution 5.3.2 The Linear Programming Relaxation with Rounding-off Solution 5.4 Results for the Days-off Problem 5.4.1 The Integer Programming Solution 6 CONCLUSION 6.1 Performance Evaluation 6.2 Sensitivity Analysis 6.3 Extension of Analysis BIBLIOGRAPHY APPENDIX A PHASE I SINGAPORE MRT SYSTEM MAP APPENDIX B WEEKDAY TRAIN TIMETABLES APPENDIX C WORK RULES iii  Page 1 6 6 8 11 12 12 14 14 15 15 18 18 19 19 27 31 37 40 42 43 43 45 47 49 51 51 53 54 57 59 59 61 63 63 Heuristic 63 72 72 76 76 79 83 85 ...92 93 104  iv  APPENDIX D MATRIX GENERATOR APPENDIX E CONVERSION PROGRAM  iv  106 113  v'  List of Tables Table  Page  1 Work Schedule of Service Intervals for Train Operators  17  2 Daily Requirements for the Original Set of Weekday, Saturday and Sunday Schedules  38  3 Optimal Results of the LP Relaxation and the 3 Heuristics for the Shift Scheduling Problem  66  4 Number of Operators and Shift Types Required to Man the Schedules for the Shift Scheduling Problem  71  5 Number of Operators Required on the Payroll for the 4 different sets of Schedules for the Days-off Problem  73  6 Integer Programming Optimum Gap from the LP Relaxation Optimum  77  7 The number of LP and IP Iterations and the Computational Times for the 4 Different Sets of Daily Schedule Runs  78  8 Sensitivity Analysis Results on the Weekday Schedules - Inclusion of Additive Cost (k) for the Split Shift Operators  81  9 Sensitivity Analysis Results on the Weekday Schedules - Forcing in x number of Straight Shift Operators  82  v  vi  List of Figures Figure  Page  1 Example of Variation in Number of Trains in Service by Time of Day  20  2 Structure of the Trick Matrix A for the Daily Shift Scheduling Problem  34  3 Pattern Matrix of Days-off Scheduling Problem  56  4 Daily Schedule Generated for the Original Set of Weekday Schedule  67  5 Daily Schedule for the Train Operators  68  . 6 Bi-weekly Schedule Generated for the Original Set of Weekday, Saturday and Sunday Schedules  74  7 Assigning Daily Shifts to the Bi-weekly Schedule  vi .  75.  1  1  INTRODUCTION  Traditionally there has been considerable use of mathematical  models in  operations management particularly in the deployment of physical resources. In recent years, there has also been increased emphasis in both research and application of the use of similar techniques in the deployment of human resources. Especially in service oriented industries where labor is a very significant input factor, the trend toward greater use of mathematical models is reflected in the design and implementation of sophisticated manpower scheduling systems. At the same time, the special characteristics of manpower scheduling problems have stimulated researchers to investigate special purpose models and techniques for such problems.  Staff scheduling problems arise in a variety of service delivery system settings including nurses in hospitals, baggage handlers in airports and airline companies, telephone operators, patrol personnel in police and security departments, firemen and toll operators etc. Many such systems or portions thereof operate 24 hours a day and seven days a week with demand for service varying (usually in daily and weekly patterns) over each hour of the week.  The basic scheduling problem is easy to state. We are given a set of activities to be serviced, with the times these activities are to be carried out The problem is to construct a low-cost , feasible set of assignments, one for each activity.  2  In scheduling problems, a time is associated with each activity. For example, each location may require a delivery at a specified time. Thus, the temporal aspects of vehicle movements have to be considered explicitly. As a result, the activities are followed in both time and space. In crew scheduling, the primary concern is to sequence the movements of a crew in space and time so as to staff the desired vehicle movements. Crew scheduling problems also have to involve complicated restrictions such as requirements for lunch breaks, union regulations, governmental restrictions etc. Section 2 will discuss the work done in the area of crew or staff scheduling.  An important consideration in the formulation and solution of the scheduling problem is the computational burden associated with various solution techniques for the problem. The computational burden of solving a given problem clearly increases as the size of the problem becomes larger. The nature of this growth in computational time as a function of problem size is an issue of both theoretical and practical interest. If this growth is too rapid, the computational burden may become prohibitive even for moderate problem size, thereby limiting the applicability of a solution technique in a realistic environment where the problems encountered are typically large scale.  The aim of this thesis is to simplify and accelerate the scheduling process using simple computer techniques so as to reduce the workload for staff in the time-tabling and scheduling offices and to allow faster and easier adaptation to meet the changing environment of the transport situation. Governmental regulations , labor union restrictions and internal agreements must be taken into account to provide more economical  planning without lowering the quality of service. In particular, the  3  automation of the scheduling process should give schedulers much more flexibility and allow planners to evaluate quickly and accurately the effects of changes in system specifications. This should reduce overhead associated with the schedulers.  The problem of crew scheduling has been widely discussed over the last 30 years. The techniques developed have been of a heuristic nature and these have been used successively for a number of transport organizations (for example, Landis [1981], Volksw and Hoffstadt [1981], Rousseau [1981] etc.). Section 2.3 and Section 2.4 will briefly discuss two subproblems of crew scheduling - daily scheduling and days-off scheduling.  This thesis will present a simple procedure for determining the scheduling of train operators for the first phase of the Singapore Mass Rapid Transit System. This phase is a 20-mile mass transit system linking the largest satellite town Ang Mo Kio to the Central Area. (See Appendix A for Phase I of the Singapore MRT System Map). The mass transit train operator scheduling problem involves establishing for each day in the week a list of workdays which assigns at minimum cost a driver to each train in the time-table with respect to the clauses in the workers contract and restrictions of the operating conditions of the system. Thus the objective is in solving the problem to minimize the number of operator hours needed to satisfy the half-hourly demand requirements over a bi-weekly period. Section 2.5 will decribe the Singapore system in detail.  Therefore we can see that the Singapore Mass Rapid Transit System train operator scheduling problem involves two different types of staff scheduling problems:  4  the daily shift scheduling problem and days-off scheduling problem. Daily shift scheduling is to determine what shift the operator should be assigned each workday and the days-off scheduling problem is to determine what days of the bi-weekly period the operator should be assigned off. *  The method used here formulates both the daily scheduling problem and the days-off problem as set covering models. The first problem i.e. the daily scheduling problem is relatively large, therefore the problem is first solved as a linear programming relaxation, and then some heuristics are used to round off the fractional parts of the solution, before daily schedules are produced. The second problem i.e. days-off scheduling problem is solved directly as an integer program because it is a relatively small problem. Thus bi-weekly rosters are produced so as to minimize the number of people on the payroll. In Section 3 and Section 4 we will address the daily scheduling and days-off scheduling seperately. In Section 3 we develop a simple set covering model and introduce a simple heuristic procedure for solving the problem. In Section 4 we will formulate the days-off problem in a similar way, but because of the relatively small model size for the days-off problem, solving the days off problem will be very straightforward and simple.  The procedures introduced in this thesis are very straightforward and simple. They do not require the solving of the large mathematical  structure of integer  programming nor the use of sophisticated computer techniques to obtain a near optimal solution. Some preliminary implementation techniques making use of available packages in UBC and some very simple programs are introduced in Section 5. The results of the problems using these techniques are shown too. Section 6 will look at the  5  performance of the heuristics and techniques introduced in the earlier sections. In this section we will also perform some sensitivity analysis and discuss further work and extensions.  Though the procedure was developed for the Singapore Mass Rapid system, it can be applied to other situations having similar crew scheduling problems where it is possible to treat the workforce as homogeneous for the purpose of scheduling.  6  2  2.1  STAFF SCHEDULING PROBLEMS  Basic Structure of a Transit System  Before going any further, it is worthwhile to describe the basic structure of a mass transit system.  Passenger service for a mass transit system is defined by means of a set of line schedules. Each traversal of a line must be performed by a single vehicle so that continuous passenger service can be provided. We can characterize trips by their start time and start location and end time and end location. A trip represents the minimal amount of work that must be performed by a single vehicle.  To define the crew scheduling problem, we must consider the nature of crew movements. Each line has one or more relief points which are stops along the line where one crew may relieve another. Relief points do not necessarily coincide with the start or end of a trip. Thus a crew's period of work on a single vehicle starts and ends at either a relief point or at the end stations. We create a set of driver trips by partitioning each trip at its relief points. The set of driver trips make up the set of input tasks for the mass transit crew scheduling problem.  A driver trip represents the minimal amount of work that must be performed by a single crew.  7  A crew operates a single vehicle during a continuous portion of work called a piece. A piece consists of one or more driver trips. A sequence of these pieces into a daily crew schedule is called a run. A shift is the work to be performed by a single crew in a day, i.e. a sequence of the runs into an acceptable set of assignmnets which meet the staff work rule specifications. (Hartley [1981]). If the end location of one piece and the start location of another does not coincide, then the crew must walk or use the transit system to go from one location to another. In general, crew are paid for this deadhead time.  Part of the challenge in mass transit crew scheduling results from the fact that the service profile of a mass transit system is rather ill-suited for decomposition into desirable crew runs. In particular, it is clear that compared to mid-day, there will be a large number of pieces required during the morning and evening peak periods. It is natural to join the peak period pieces into split shifts i.e. shifts with a very long break between pieces. Transit crew however prefer straight shifts which consist of a single piece or contains a short break between pieces. The typical union contract places cost penalties on split shifts or limits the percentage of split shifts used. To complicate matters further, the nature of the union regulations, governmental restrictions and the service profile can vary from one situation to another.  8  2.2  Review of Literature  Considerable research has been directed toward solving the staff scheduling problem. Much of this previous research has focused on solving the problem by offering a heuristic or an optimizing approach. This section will review the research that has been done over the last two to three decades.  Staff scheduling problems (for example in Baker [1976], Bartholdi [1980], Maier- Rothe and Wolfe [1973] etc.) arise in a variety of service delivery system settings. This kind of problem is most commonly encountered in public service and transportation industries and sometimes in manufacturing firms as well. The scheduling problem has been analyzed in many papers. In these papers, the requirements pattern is given and the problem is to determine the optimal workforce size. Thus the main difficulty arises directly from the kind of service that the system must offer. Many methods are available to analyze problems of this kind, including linear programming, integer programming, quadratic programming, solutions for special cases and enumeration.  The  earliest version was stated by Edie [1954] and formulated by Dantzig  [1954] as a linear programming problem requiring integer values. Balinski [1965] and Bennett and Potts [1968] also used integer programming in their approach to workforce scheduling. Up  to now, many examples have been studied including minimizing the  number of telephone operators (Shepardson and Marsten [1981] .Wilson and Willis [1983]), toll booth attendants (Dantzig [1954]), nurses (Maier-Rothe and Wolfe [1973]), baggage handlers (Monroe [1970]) and bus drivers (Lessard, Rousseau and Dupuis  9  [1981] and Bennett and Potts [1968]). Manpower scheduling has generated considerable discussion in the literature. Other papers include those by Baker,[1974,1975]), Brownel I 2  and Lowerre [1976] and Tibrewala, Philippe and Browne [1972].  Most of these scheduling problems can be formulated as a special class of zero-one integer programs known as set partitioning or set covering problems. Basically, a set covering problem involves a given 0-1 matrix with costs attached to all columns. The  objective is to choose a minimum-cost collection of columns such that the  number of l's appearing in each row of the selected columns is at least one. If this number is required to be exactly one, the set partitioning problem results. In this case the rows are partitioned into a number of subsets each "covered" by exactly one selected column. Set covering and  set partitioning problems have been studied  extensively over the last two decades. (See Garfinkel and Nemhauser [1969] ,[1972])  Considerable research has been directed toward solving this problem using some heuristic approach. However the choice of heuristics for different operations and different situations and  environments have proven to be  fairly unclear and also  non-uniform (Parker and Smith [1981], and Bodin et al. [1981]).  Dantzig and Fulkerson [1954] pioneered the use of such a formulation in their solution of the tanker scheduling problem. Although  more recent variations and  extensions (e.g. Miller [1976], Showalter and Krajewski [1978], Wilson and Willis [1983] etc.) have been used to solve a wide class of scheduling problems, the set partitioning and set covering methods have not been used extensively in mass transit systems because of the relatively large problem that it must handle.  10  As Rousseau [1982] stated, there are quite a number of techniques available fo the scheduling of crews in transport situation for which a solution approach can be adapted. However, the techniques finally implemented or used must be suitable and acceptable to the operational environment  While set covering and set partitioning provide a valid conceptual framework for the formulation of the scheduling problems, their practical ability may be limited if the resulting integer program is too large. In the last decade it has been possible to solve set partitioning problems of some 150 rows and a few thousand columns, (see Marsten [1974]) However, since all columns corresponding to feasible options must be enumerated, in most cases a full-scale representation of a scheduling problem as an integer program leads to problems of an enormous size. As a result, researchers have employed heuristics for decomposing set covering or set partitioning problems (e.g. Mitra and Welsh [1981], Parker and Smith [1981] etc.). The heuristics used were only able to provide approximate solutions to set partitioning or set covering problems.  For the system we are dealing with, we are basically looking at a particular class of set covering or set partitioning problems called the two-shift period scheduling problem for the daily scheduling of personnel (Shepardson and Marsten [1980]). There may be different shift stations , each of which has a minimum staffing requirement at each period of the working day. The staffing requirements thus vary as a function of the time of day. In particular, most staffing locations require increased demand during the morning and evening rush hours.  —  11  Since the matrix of this two-shift scheduling problem for the Singapore  MRT  system is relatively dense and non-circular, it will not be possible to apply a network approach to the problem (Segal [1972]. Thus there was reason to take the conventional LP and IP approach.  The approach used here to solve the relatively large set covering problem (i.e. the daily scheduling problem) is somewhat similar to the integer linear programming heuristic introduced by Bartholdi, Orlin and Ratliff [1980]. All possible shifts were included and the set of columns (variables) to be considered were not restricted. The procedure was therefore to generate all possible shifts and use LP to select from that set a set of shifts that cover all the work in the most efficient way. That is, instead of solving the problem as a integer program, we  solve the linear programming  relaxation. Some rounding off heuristics were then used to round off the fractional results. For the small set covering problem (i.e. the days-off problem), the problem was solved directly using integer programming.  However before going into the actual problem itself, we want to look at some other procedures that have been used for the scheduling of mass transit crew.  2.2.1  Run Cutting Approaches  Generally manual schedulers produce extremely good solutions. The  primary  disadvantage of the manual approach is the time it takes to produce a new solution (several weeks) and the time it takes to train new schedulers (several years). While this assessment is true to a certain extent, there has been significant cost savings  12  shown in recent studies (Landis [1981]) using computerized techniques based on the heuristics used by manual schedulers. The first large scale computerized  implementation  of run cutting was the RUCUS run cutting package (Landis [1981]). The results for this package were mixed. It is cumbersome to use, operates in batch and is rather inflexible in that it is difficult to incorporate minor changes in work rules and problem parameters.  2.2.2  Service Profile Decomposition  This method developed  Algorithm  by Lessard, Rousseau and Dupuis [1981] uses the  information contained in service profiles to generate the pieces of work and the matching problem is then used to form workdays. This is called the Hastus-Macro model. The model takes the problem and relaxes it to get a smaller and more simplified problem.  2.2.3  A Matching Based Algorithm  In Ball, Bodin  and Dial  [1983], the crew and vehicles are scheduled  simultaneously. The first phase specifies pieces and the second phase merges these pieces into runs. The problem of combining these pieces into runs can be solved as a matching problem. This  approach  was proposed  for an interactive  model for  simultaneous solution to the vehicle and driver scheduling problem.  We now want to look at the train operator scheduling problem for the Singapore MRT system. The scheduling of the train operators for the system can be  13  looked at as two seperate scheduling problems - the scheduling of the train operators to daily shifts i.e. daily scheduling problem and the scheduling of the train operators to bi-weekly rosters i.e. days-off scheduling problem.  14  The  2.3  Daily Scheduling Problem  The most detailed staff scheduling problem arises in situations where demand for staff fluctuates in the course of a day. This problem is • to minimize the cost of assigning operators with different shifts to meet daily staffing requirements.  The  difficulty of this problem arises directly from the kind of service that a transit system must offer. The number of trips requested at peak hours is usually much greater at peak hours than at off-peak hours. This will necessitate split shift, straight shift operators or both in a single workday. In most situations, labor-management agreements and governmental regulations specify operators by type, according to a particular time when they start and finish work, when they take their break, and the total maximum and/or minimum number of hours that may be worked etc. Moreover some agreements even specify the maximum and/or minimum number of a given type of shift which are permissible in the final operator schedule.  The  2.4  Days-off Scheduling Problem  A different scheduling problem arises when the length of an operators work period does not match the facility's operating week. This is the problem.  days-off  scheduling  It seeks to minimize the number of operators required to meet daily staffing  requirements where each operator is alloted a specified number of days off each work period (a week, a fortnight or a month). This problem basically involves the combining of daily schedules into weekly, fortnightly or monthly schedules by solving the case in  15  which weekday staffing requirements are identical, and weekend requirements may or may not be identical. This problem is to find a workforce allocation which avoids excess staffing and which minimizes the number of man-days in the schedule.  2.5  2.5.1  The Singapore Mass Rapid Transit System  Operating Conditions  The daily operating schedule covers a period of 18 hours from 06.00 in the morning to midnight City bound trains (southbound) start at 06.00 at the Ang Mo Kio  station with the frequency of the trains building  up to gradually meet the  morning peak requirements. At Outram Park, the first trains leave at 06.00, 06.10 and 06.30 with frequencies building up to the level of the city bound train service. At night, the last northbound train leaves Outram Park just before midnight and arrives at Ang Mo Kio at approximately 20 minutes past midnight The last two city bound trains leave Ang Mo Kio at 23.30 and 23.45 arriving at Outram Park at 23.50 and 24.05. Train operations on Sundays and holidays start half an hour later and end half an hour earlier. The relief points are only at the start and end of a trip i.e. a crew's work period on a single train start and end at the end stations Ang Mo Kio and Outram Park.  Traffic flow estimates form the essential basis for the planning of the service frequencies. These estimates together with the peak factor are adopted mostly from  16  observations  on  the Hong  Kong  MTR  System.  These  estimates  are  then  used to  determine design volumes, and thus together with the running times, dwell times and terminal times, the  service  frequencies  and  the  total  requirements  for  trains  were  determined.  Table 1 summarizes  the anticipated service intervals throughout workdays. Train  service on Sundays and holidays would be operated with intervals of 6 minutes from 06.30 to 10.00 and 18.30 to 23.30. Between the hours of 10.00 and 18.30, the intervals would be 4 minutes. Given the service intervals we are able to generate a detailed train  time-table for  all trains  leaving  both  the  Ang  Mo  Kio  and  Outram  Park  stations. See Appendix B for the detailed train train timetable.  The  total  requirements  for  trains  needed  to operate  the  indicated level  of  service was determined on the basis of running times and terminal times. Running time is the time take for the train to travel from one end of the line to the other end of the and back again. Running times including dwell times at intermediate stations amount to 46.9 minutes during morning and evening peak operations and 44.9 minutes outside of peak periods. Running time is the time taken for the train to travel from one end of the line to the other end and back again. Terminal time is the time that the train must stop at either end stations. Terminal times including dwell times at Ang Mo  Kio and Outram Park are 2 minutes and 3.5 minutes respectively, that the train  has to stop at either end stations. The trains stop at every station along the way, but crew changes occur only at the end stations.  TABLE 1  WORK SCHEDULE OF  SERVICE  INTERVALS  T i m e o f Day  Service  6 :00- 6 : 30 6 :30- 7 :00 7 :00- 7 : 30 7 :30- 9 :00 9 :00- 9 : 30 9 :30-12 :00 12 :00-12 :30 12 :30-14 : : 30 14::30-16 :00 16 : :00-16 : 30 16 : :30-18::00 18 : :00-18::30 18 : :30-19::00 19: 00-24::00  Mon-Fr i 6 5 4 3/2 4 5 5 5 5 4 3/2 4 5 6  * Peak-within-peak s e r v i c e a p p r o x i m a t e l y 25 m i n u t e s  FOR  TRAIN  Intervals  OPERATIONS.  (minutes)  Sat G 5 4 3/2.5* 4 4 4 3/2.5* 4 4 4 4 5 6  intervals only  Sun 0 6 6 6 6 6/4** 4 4 4 4 4 4 6 6**  operated f o r  ** T r a i n s on S u n d a y s and p u b l i c holidays operating with i n t e r v a l s of 6 minutes to 10.00 and 18.30 t o 23.30. B e t w e e n 18.30 t h e i n t e r v a l s w i l l b e 4 m i n u t e s .  will be f r o m 6.30 10.00 a n d  *  the  From t h i s t a b l e we a r e a b l e t i m e - t a b l e i n A p p e n d i x B.  to generate  train  18  2.5.2  Daily Shift Specifications  Operators work in shifts where each shift is characterized by a start time, an end time and a break time. To simplify the problem, we have shifts start and end on the hour and on the half hour. The duration ( spread) of a shift may vary from 9 to 12 1/2 hours, depending on the particular shift type. Straight shifts are 9 1/2 hours long, and split shifts have a maximum spread of 12 1/2 hours with a minimum of 4 hours break in between. The maximum number of hours without a break inbetween for both straight shifts and split shifts is 5 1/2 hours.  2.5.3  Bi-weekly Roster Specifications  Finally provisions must be made for restdays for the bi-weekly operating period which is 3 days per 14-day period. The maximum number of consecutive working days per week is 6 days.  19  3  3.1  DAILY SCHEDULING PROBLEM  Statement of the Problem  Train schedules and the time and location of relief points are defined and fixed. The line schedules are determined by the demand for trains throughout the day, measured in terms of the number of passengers. Therefore, the number of trains varies and is a function of the time of day. The task of management here is to decide how much of this demand to meet The train requirements are thus guided by a service level policy in the form of "no more than p% of passengers may be delayed more than q% units of time" as described by Segal [1972] for telephone operators. From the given requirements for service, we can generate a schedule and thus determine the number of trains running in any given time interval. From there, the operator requirements for each time interval can be determined. The allocation and determination for trains and operator service in this problem is an external process.  The number of trains required can be represented by a graph as shown in Figure 1. This graph shows the number of trains required for the Singapore MRT system.  ro o FIGURE  1  EXAMPLE OF V A R I A T I O N  »  I N NUMBER OF T R A I N S  I N SERVICE  BY TIME  OF DAY  Of  trains  20 + X X  x x X  x X  X  x X  15 +  10 +  x  XXXXXXXXXXXXXXXXXXXXXXXXX  X  xxxxxxxxxxxxxxxxx  5 +  0G.00  12 . 0 0  18 . 0 0  24 . 0 0 Time o f Day  21  The actual positions of the peaks, troughs and their relative heights and depths for operator requirements depend on the community being served. Usually the morning peak occurs just before the start of the normal working day and the evening peak just after its end. It is thus impossible for a train operator working a normal day (straight shifts) of about 8 to 9 hours to be cover both peaks. There are at least two possibilities: either crews work straight shifts, each covering one peak only, or they work split shifts which cover both peaks but allow a considerable amount of free time during the day. In the first case, crews may be idle for large periods of time for which they must be paid. In the second  case, they have to be paid some  compensation for the inconvenience involved in split shifts.  One of the objects of the daily scheduling problem is thus to minimize this unproductive time. This is complicated by the agreements between the management and the unions regarding the types of shift which may be worked. There is considerable variation between the operating agreements. Thus it may be important to examine the different provisions which are to be found and the effects these may have on the costs of schedule operation.  Such conditions can be divided into two main categories: * those relating to individual shifts * those relating to a group of shifts.  Some of these conditions are fixed; others concern values or wishes; others are only valid under certain circumstances. In certain cases, these different conditions are interdependent  22  The conditions concerning individual shift types are related to: 1. Upper limit to the  spread  of a shift, that is, the time which elapses between a  crew signing on for its first piece of work of the day and the signing off after its last piece of work.  2. Maximum total time spent operating the train in the course of a day.that is, the working time.  3. The stations where crews get on and off.  4. Maximum legal spell for a shift without a meal break (e.g. about 5 hours). After this time, a break (usually of at least 30 minutes) must be taken.  5. Signing on and off times.  6. Payments made for various factors, for instance, the idle time within a shift in addition to platform time.  Conditions relating to a group of shifts are important for the total quality of the crew schedule. The more important conditions are: 1. The numbers of shifts, split shifts , train changes and shifts with a long break between shifts, may be restricted.  2. The average working time should not exceed a certain number of hours.  23  The above list is by no means exhaustive but illustrates the type of restrictions which complicate the scheduling process.  Associated with each shift is a cost. For our current objective function fomulation for the daily scheduling problem, the total number of hours worked is the current cost We have not indicated extra pay for working split shifts (for example, based on increasing spread premium) or additional compensation for unusually long spreads or breaks because the cost structure for the system has not yet been determined since the Singapore Mass Transit System is an entirely new system. Each shift type that can be considered may have a different cost structure and desirability. We can also build equity into it by insuring that all operators' schedules are of "equal difficulty". This can be accomplished by changing the daily shift that a particular driver follows every day so that all schedules are of about the same difficulty. This combining of daily schedules into bi-weekly schedules is addressed in the days-off scheduling (crew rostering) problem later on.  The cost used for the daily shifts is the total number of hours worked per shift. This number does not include the break time for split shifts. Ideally there should be some preferential allocation (for example higher hourly wages or more rest days etc.) for split shifts, which can be incorporated into the objective function later 1  on. For now the objective is to minimize the total number of hours required to -man the schedules.  24  A trick specifies the actual timing of the break periods, start and end times. The tricks in this formulation have been built according to the detailed work rules given in Appendix C. 1. Straight shift operators 2. Split shift operators  Presented in this light, the problem is limited and also well defined, but at the same time it has proven to be computationally difficult (Wren [1981]). In practice, mass transit crews are still typically scheduled manually by skilled human schedulers who can often compile an optimal or near optimal schedule. However this procedure is relatively cumbersome, time consuming and above all costly.  Manual crew scheduling is time consuming because: -  the constraints to which the data and roster are subject are very complicated.  -  often a new  time-table and schedule is required more than once a year for  Saturdays, Sundays and weekdays, that is , there are 3 different schedules to consider each time there is a change.  -  changes in personnel work rules and union demands  -  the information needed for a quick design of a new schedule is not computerized. Retrieving information and providing information are bottlenecks in the entire crew scheduling process.  25  Recognizing the difficulties posed by the scheduling problem, we can see that there is a great deal of pressure on the scheduling department when the transit planner needs feasible crew and vehicle schedules on a relatively frequent basis, as seasonal variations and changes in demand patterns require new schedules be produced several times a year. Producing  this manually  takes schedulers and planners a  significant amount of time. Consequently, it is impossible to alter the schedules on short notice and to perform a variety of planning functions without a computer procedure. This also makes it virtually impossible to determine changes in crew and vehicle costs as a function of changes in work rules.  To determine the sensitivity of crew and vehicle costs to changes in demands and to determine the effects of a system growth on operating costs, it is often not sufficient to simply compile a list of shifts which satisfy all the restrictions imposed. There are usually many possibilities, all with different costs, and the scheduler's objective is to find a cheapest one. The final acceptance of schedules is usually in the hands of the union representatives on a negotiating committee and the scheduler has to put forward a set of shifts which he thinks will satisfy the workers.  The  main difficulty of the problem thus arises directly from the kind of  service that the urban mass transit system must offer and the travel patterns of the population. Because of its complexity, it is unlikely to have a compact statement for which an exact solution procedure exists.  26  Scheduling constraints can vary significantly from situation to situation. The fact that management-union agreements differ very widely from system to system make the scheduling development of a general application program difficult A second related difficulty involves the degree to which the human scheduler has to control the schedule output by the computer. No matter how the schedules are generated, before they  are finally  implemented, they  must be approved  by the scheduler and  management But before giving the approval, the scheduler must also have the ability to alter the schedule. The type of alterations required would probably arise from many less tangible political issues. The consideration of the two difficulties just described is essential to the development of a successful system.  Schedule updating, however, can be prompt and efficient if all the different stages can be computerized: processing of passenger requirements and running time surveys; train scheduling; and crew scheduling in compliance with union agreements, transit restrictions and relevant regulations.  We will now discuss two simple formulations for the daily scheduling problem: The set partitioning problem and the set covering problem.  27  3.2  A Set Partitioning Formulation  A set partitioning formulation is defined as follows: Starting with the first train leaving at 06.00 index each trip leaving either stations successively by i, 1 < = i < = N, and index each possible trick by j, 1 < = j <=  J (where N is the total number of trips made in a day, and J is the total  number of possible tricks).  The trick matrix A* =[a* ] iJ  i = l,2, ,N j = l,2 ,J  is defined by: a* = 1 iJ  if the i-th trip is service by trick j  0  otherwise.  Let x* be the number of operators that are assigned to the j—th trick, x* is j ' j 1 if the operator is assigned to the j-th trick and 0 otherwise.  Let c* be the unit cost of trick j. c* >0. The right-hand side requirements j j are all ones since we need only one operator per train. C,X and b are  b* i compatibly dimensioned vectors.  28  Therefore to assign one operator exactly to each train leaving the station, we formulate the following problem : Minimize SUM  (c* x*:j = l,..,J) j j  (1)  subject to SUM  (a* x* :j = l,..,J) = l for all i = l,..,N ij J  x* =0 or 1 j  for all j = l,...,J  Problem (l)-(3) with c* > partitioning problem.  (2)  (3)  0 and all a* = ij  0 or 1, is called a set  Application of the above formulation supposes the generation of all the possible tricks which can be used to cover the demand required by the train schedule. The number of variables possible is equal to the number of tricks. The objective of the set partitioning problem is to select a subset of tricks from all the variables so as to cover the work at minimum cost  Conditions (3) involve techniques for zero-one programming, and may  imply  high computation times. Considerable research has been done in developing algorithms for specific problems which allow for noticeable reduction of computation time (e.g. Garfinkel and Nemhauser [1969]).  29  Foster and  Ryan [1976] reduced the complexity  of the set partitioning  formulation by imposing additional constraints. These constraints remove many of the variables from the original model on the grounds that they have a structure that is most unlikely to be present in an optimal solution. The definition of "unlikely" is found by  examining the routes occurring in the optimal solution to small test  problems. In this way, a much smaller problem can be solved, hopefully, with the optimum unlikely to be seriously affected.  Shepardson and Marsten [1980] reformulated the two-shift scheduling problem as a one-shift problem. This results in a minimal cost network problem with side constraints. They  formed  a  Lagrangian  relaxation which  can  be  easily solved.  Subgradient optimization is then used to maximize the Lagrangian. Their computational experience with large real life problems seems quite promising. With subgradient optimization they were able to get, on the average, within 3% of the continuous optimun value in a quarter of the time it would take to solve the linear program.  Though the set partitioning formulation gives an exact method for the the daily scheduling problem, the computation for a full column-generation approach will be fairly exorbitant and the generation of all the possible shifts will be a relatively complicated and tedious task. In addition, the set partitioning problem may  not always  be feasible because of the enornous number of rows and columns in the mathematical formulation. For the Singapore Mass Rapid System, there are more than 18,000 tricks (variables) and about 240 trips (rows).  •30  The  reduce the problem, we  gather the constraint rows into larger time  intervals where each row in the constraint matrix corresponds to a time period instead of each instant for which a train leaves the station. The columns of the matrix i.e. the shifts will cover a few trips of the time-table. This gathering of the constraint rows into larger time intervals will give the set covering formulation.  31  3.3  A Set Covering Formulation  Let the total working day be divided into periods. The periods need not necessarily be of equal duration, but usually identical periods of a quarter, a half or one hour are used. For our problem we have chosen the time intervals to be half an hour. Let N denote the number of periods in a day. Furthermore, let J denote the number of admissible shift tricks. Then contraints for this new  problem can be  fomulated as follows:  SUM  a* x ij j > = b (i) min  and  <=b  (i) max  where = 1 if trick j is used in time period i y  =0 otherwise.  b (i) and b (i) give the minimum or maximum number of operators min max required in period i. The constraints in (2) of the set partitioning problem require that each of the tricks is used at most once in any solution. The set covering problem obtained by replacing this system of constraints (2) with the constraint system Ax> = b  32  which requires that each trick is performed at least once. In this way,  the  dimensionality of the set partitioning problem is reduced dramatically and thus the computation complexity of the problem is reduced. For the set covering problem we are dealing with for the Singapore Mass Transit system, there are 2391 variables or shift types and only 36 rows.  Now  we want to look at the set covering formulation for the Singapore  MRT  system. The trick matrix is defined as follows: Starting at 6.00 index each half-hour successively by i, 1 <=  i <=  N, index all possible tricks j, 1 <=  j <=  J (N is  the total number of time periods in a day and J is tht total number of possible tricks). The trick matrix is as follows:  A* =[a*  ]  i = 1,2,  N  ij j = 1.2,  a* = 1 ij  if the ith half-hour falls in the work period trick j  0  We ones  J  otherwise.  see that the constraint matrix A has two segments of ones. A segment of  is a consecutive set of column elements a* , ij a* =1 ij  i = k,  ,k+p  33  for all j.  and a* =0 if k>l k-lj a* = 0 if k + p<N k + p+lj  Figure  2 shows the pattern  for all j.  of trick matrix  A. Each half-hour  period  corresponds to a constraint, that is, each row. Each shift type corresponds to a column. The actual trick matrix A has 2391 columns (i.e. variables) and 36 contraint rows.  FIGURE  2  •STRUCTURE OF THE TRICK  MATRIX  A FOR THE OA ILY  SHIFT  SET COVERING  OJ -1^  PROBLEM  1 1 1 ' 1 1 1 1 1 1 1 1 1 1 1 1  1 ' 1 1  1 1' 1 1 1 1 1 1 1 1 ' 1 1 1 1 1 1  1 1 1 1 1 1 1 1 1  The A m a t r i x f o r t h e d a i l y s c h e d u l i n g s t r u c t u r e of the matrix o n l y .  i s 2931 c o l u m n s .  This  figure  i s t o show  the p a t t e r n  35  Let x* be the number of operators assigned to the j—th trick and c* the j j unit cost of trick j and c* >0. c* in this formulation is the total number of hours j j worked per day by shift j (usually different wage-benefit rates are allocated for various trick types). In this formulation we have not indicated extra pay for working split shifts and our cost function is to minimize the total number of half-hours worked. Let b* be the number of operators required during the half hour-period i. For the Singapore MRT  problem, the x* is categorized into 6 different j  variables types for the split shift operators and a seperate one for the straight shift operators. Let m* be the number of 5-hour split-shift operators assigned to the j-th trick. (372 j m variables) Let n* be the number of 5 1/2-hour split-shift operators assigned to the j—th trick, j (420 n vairables) Let p* be the number of 6-hour split-shift operators assigned to the j—th trick. (435 j p variables) Let q* be the number of 6 1/2-hour split-shift operators assigned to the j—th trick, j (420 q variables) _ Let s* be the number of 7-hour split-shift operators assigned to the j—th trick. (378 j s variables) Let t* be the number of 7 1/2-hour split-shift operators assigned to the j—th trick, j (312 t variables) Let r* be the number of 9 1/2-hour straight shift operators assigned to the j—th j trick. (54 r variables)  36  The unit cost used for this problem is the total number of half-hours worked. The cost for the various types of shifts are:  10 for the 5-hour split-shift operators (i.e. the m variables) 11 for the 5 1/2-hour split-shift operators (i.e. the n variables) 12 for the 6-hour split-shift operators (i.e. the p variables) 13 for the 6 1/2-hour split-shift operators (i.e. the q variables) 14 for the 7-hour split-shift operators (i.e. the s variables) 15 for the 7 1/2-hour split-shift operators (i.e. the t variables) and 19 for the 9 1/2-hour straight-shift operators (i.e. the r variables).  Now  we want to see how the requirements i.e. the b* are calulated from the i detailed train time-table in Appendix B.  37  3.3.1  Crew Requirement in Daily Shift Scheduling  An important step in the solution of the daily shift scheduling problem is the determination of operator requirements (b*) for each time interval in the set covering i problem. The service intervals of the trains leaving the stations is an external process. Then given the train time-table as in Appendix B, we can easily assign trains to the trips to both the stations. First a histogram ( called the demand histogram) of the number of crew requirements to cover all the trips over the day. The input is the set of aggregated trips in the time-table. To construct this histogram, the time of day is broken down into 30 minute time intervals. In order to set the crew requirements, we want to count for each 30 minute time interval, the inventory of trains needed to cover round-trips. Within each time interval, if a additinal train is required to be on the tracks, we will increase the inventory of trains by one and also increase the crew requirement for that time interval by one. For example if there is a trip from Ang Mo Kio at 07.15 which cannot be covered by a train coming in from Outram Park, an additional train will be needed to be put on tracks to cover this 07.15 trip. This therefore generates an requirement for an additional opertor for the time period 07.00 to 07.30. However if this 07.15 trip can be covered by a train comming in from Outram Park, the requirement for an additional train is not required. Therefore the requirement for an additional is also not increased. Thus we can count the number of operators required at each of the 30 minute time intervals. Table 2 shows the requirements for operators to cover the trips for the weekday, Saturday and Sunday schedules.  38 Table  2  D A I L Y R E Q U I R E M E N T S FOR THE O R I G I N A L S E T OF WEEKDAY, AND SUNDAY S C H E D U L E S  T I M E OF DAY 06.00 06.30 07.00 07.30 08.00 08.30 09.00 09.30 10.00 10.30 11.00 11.30 12.00 12.30 13.00 13.30 14.00 14.30 15.00 15.30 16.00 16.30 17.00 17.30 18.00 18.30 19.00 19.30 20.00 20.30 21.00 21.30 22.00 22.30 23.00 23.30  -  06.30 07.00 07.30 08.00 08.30 09.00 09.30 10.00 10.30 11.00 11.30 12.00 12.30 13.00 13.30 14.00 14.30 15.00 15.30 16.00 16.30 17.00 17.30 18.00 18.30 19.00 19.30 20.00 20.30 21.00 21.30 22.00 22.30 23.00 23.30 24.00  NUMBER OF OPERATORS R E Q U I R E D Weekday Saturday Sunday 7 12 16 20 24 20 13 12 12 12 12 1 2 1 2 12 1 2 1 2 12 1 2 1 2 1 2 1 6 18 23 21 14 1 3 8 10 10 10 10 10 10 10 10 7  7 12 16 20 24 20 1 4 16 14 16 14 16 14 20 24 16 1 4 1 6 14 16 14 1 6 14 16 14 12 10 10 10 10 10 10 10 1 0 10 7  0 7 10 10 10 10 10 10 16 14 16 14 1 6 14 16 14 16 1 4 16 14 16 14 16 14 16 10 10 10 10 10 10 10 10 10 7 0  SATURDAY  39  The set covering formulation can therefore be formulated as follows: Minimize SUM c* x* j j  with c* >=0 j j = l,2, ,J  (4)  subject to SUM a* x* >= b* iJ j i i = l,2,  N  with a* =0 or 1 all i j iJ (5)  with x* nonnegative integers. j  (6)  To further simplify the problem, we have also tried an hourly formulation. For this simplified version, we have only 210 tricks and 18 constraints. However, in this very simplified formulation, we have to give up some of the precision and also relax some of the restrictions. For example, meal breaks for the straight shifts who normally should work 9 1/2 hours are ignored because meal breaks are 30 minutes and the smallest time period here is one hour. In addition if operators have to work shifts up to the full hour, there will be a lot of wasted or idle time.  40  3.4  Set Covering Formulation vs Set Partitioning Formulation  Using the set partitioning model we are able to get directly from the solution a detailed and exact schedule for assigning each operator to every train leaving the stations. However using the set covering model can only generate schedules for assigning a list of operators at each time period i.e. it will not come up with a detailed schedule as to which operator will service the trips leaving both the stations. Thus an additional step of assigning the operators to individual trips will be required after obtaining the solution to the set covering problem.  The set covering formulation may also allow any piece of work to be covered by more than one shift since the set covering problem only ensures that every piece of work is covered  at least once whereas constraint (2) of the set partitioning  formulation ensures that each period belongs to one shift only and constraint (3) represents the individuality of each shift Clearly the solution to this set covering problem will not be the optimal solution to the set partitioning problem which allows the piece of work to be covered exactly once. Therefore the solution to the set covering model will only yield sub-optimal  results. The  set covering formulation  however is preferable to the set partitioning formulation because much fewer tricks (variables) need to be considered in the formulation. In practice, covering a piece of work more than once is not a problem. If any bit of work is over-covered (i.e. covered more than once), it is possible to remove the over-covered time periods from one or more of the shifts on the schedule. Such a procedure will not adversely affect the restriction set out in constraint (5) of the set covering formulation but makes the  41  set covering formulation more equivalent to the set partitioning formulation as long as the modified shift remains a valid shift to the problem. Also if a "good" schedule is produced, the number of surplus operators (i.e. the amount of overcovered work) for the schedule will be very small and in situations where spare operators are required, the surplus operators can be used for meeting the spare operators requirements.  Another factor which tends to make the set partitioning problem considerably more complex is the requirement for breaks (i.e. long breaks between shifts or meal breaks) implied by government legislation. The consequence of the breaks is that any given shift will cover at least two full trips. This results in a much larger number of columns (i.e. possible shifts) and a much greater degree of interaction between the columns. The problem thus becomes highly degenerate and the set of all possible shifts to the set partitioning problem is very large. Therefore solving the complete problem optimally will be computationally difficult and a feasible solution may  not  even be obtainable. However for the set covering problem, a feasible solution is always guaranteed.  The  reduction in problem size, and the fact that the simplified formulation  with fewer rows and variables to be considered affects the degree of degeneracy in the problem has led us to believe that solving the set covering model is a better and more practicable model.  42  3.5  Solving the Set Covering Problem  The idea of using set covering in scheduling problems has been used for the past 20 years. In these applications, the rows represent the entities that require service whereas the columns of the integer programs correspond to ways in which service may be provided to a subset of demand entities. The column cost would then be the total cost associated with each column.  While set covering provides a valid conceptual framework for the formulation of scheduling problems, its practical utility may  be limited if the resulting integer  program is too large, as in this case. Even for the half-hourly and hourly models, solving a problem of this size tends to be impractical (e.g. UBC  LINDO only takes  up to 200 integer variables). Since all columns corresponding to feasible options must be enumerated, solving a full scale representation of the problem as an integer program will be very costly.  As a result, heuristics were looked into to provide an approximate solution to the set covering problem.  We  will solve the set covering problem using a heuristic approach which is  similar to the one in a paper by Baker et al. [1976]. The procedure is very simple and straightforward. The set covering is relaxed into a linear program, and then a rounding off heuristic is used to round off the fractional parts into zero or one. The fractional solution is then rounded up or down to meet the integrality constraint  43  without violating the demand constraints.  The following section looks into some heuristics for rounding off the fractional solutions of the problem. Bartholdi [1981] offers a linear programming round-off algorithm for which a bound on the absolute error is guaranteed. However this is specifically for cyclic staff scheduling for the days-off problem. In Balas' [1984] paper offers a sharp bound heuristic for the rounding problem which is basically the second heuristic described below in the study.  3.6  Some Heuristics  Let IP denote the integer program for fixed constraint matrix A and variable right-hand side b and let LP denote its continuous relaxation. LP IP An optimal solution to IP and LP is denoted by x* and x* respectively IP LP with corresponding values z* and z* . A straightforward heuristic is to solve the problem by an LP rounding-up heuristic. See Bartholdi [1981]. 3.6.1  Step 1  Step 2  Round-up Heuristic  LP Solve LP to get x* .>-. h LP Round up to get heuristic solution x =UP(x* ) with objective value  h Z =  LP C X*  where UP(x)= MIN  (N:N integer and N  >  45  Another heuristic as suggested by Balas [1984] called the set covering, heuristic offers the best possible bound on the ratio between optimal integer and fractional covers.  3.6.2  Step 1  Set Covering Heuristic  LP LP Solve LP to get x* . If x* is not integer, Let LP X = DOWN(x ) rounded down j j f LP x =x - x (fractional part) j J j  (where DOWN(x) = MAX (N:N integer and N<= x))  F={j:ji 4= j  x  LP } be the set of fractional variables j  =b - SUM (A _x.:j = l,2 ,n) i i ij j  h  and  U={ i: h >0 } be the set of uncovered rows, i  46  Step 2 Rank the fractional variables of the optimal solution such that f  f  >= j(l) j(2) (where p = |F|) X  >  = X  f > =x J(P)  Step 3 Compute the smallest t, K = t<=p such that  SUM (A (k): k= l,2,..,t) >=h for all i e U. iJ i (**note that SUM ( A  f f x ) >=b for all i, and x < = 1 so t<=p ) iJ j i j  and define the heuristic solution h x j(k)  = x + 1 all k=l,..,t j =i all k=t+l,..,p j  The third heuristic is similar to Balas' . It takes the fractional parts of the solution and formulates a small zero-one integer program.  47  3.6.3  Zero-One Integer Programming Heuristic LP Let x denote the optimum solution to the LP relaxation. Let y be the LP j  variables associated with the fractional variables in x Consider Min SUM (c y : j e F) j j st  SUM (A y: j e F) >=b all i e U ij j i  where F,U and h are defined as above, i  Solving the above zero-one integer problem will round off the fractional parts h (the y) up or down and yield a feasible integer solution x : j h x =1 + y all j e F j j j LP =x  all j £ F j  The performance of the 3 heuristics are shown later in Section 5.3.2.  49  3.7  Generating Feasible Daily  Schedules: Disaggregation of the Set Covering  Problem  It is not enough to just get a list of the shift types required to meet the service levels of the trips for each 30 minute interval in the workday of the system. We  must be able to determine detailed feasible crew schedules to cover each and  every trip in the train time-table. A simple procedure is described below which will assign individual operators to the different trains to cover all the trips. This procedure is a variation of the Concurrent Scheduler Heuristic introduced by Bodin [1979]. 1. Match and merge the trips in the train timetable leaving both stations into round trips. 2. Order these trips by starting time from the beginning time of the day (For the Singapore MRT  system this beginning time of day is 06.00). Call this list of trips,  the "sorted trip list". 3. Split the shifts generated by the set covering problem into individual runs (i.e. shifts without lunch breaks or long breaks). 4. Sort these runs by the time of day and call this the "sorted crew list". 5. Starting at the First time interval (06.00 yo 06.30), assign trip 1 in the sorted list of trips to crew 1 in the sorted crew list 6. Assign subsequent round trips from the same time interval in the sorted trip list to the other crew available in that time period. At this point it may be necessary to re-sort the sorted crew list for the current time interval, if not all the trips can be covered. However we must still keep in mind that whilst assigning the operators to the individual trips, we must not violate the shift specification rules. 7. When every trip has been assigned for that current time interval, go look at the  50  trips in the next time interval. 8. Repeat Step 6 and 7 for all the round trips in the sorted list until all trips are covered.  The above procedure will give a daily crew schedule which is feasible. Section 5.3.2 discusses the results of the daily scheduling problem and will give an example of the detailed schedules produced by this simple disaggregation procedure.  51  4  4.1  DAYS-OFF SCHEDULING  Introduction  After solving the daily scheduling problem, we need to solve the days-off scheduling problem. For this problem we need to generate a bi-weekly crew roster for the train operators i.e. assign the straight shift and split shift operators to a prescribed work schedule for each two-week period. This combining  of daily schedules into  bi-weekly schedules is called the days-off problem or the crew rostering problem.  We need to be able to assign the set of Weekday, Saturday and Sunday shifts from the daily scheduling problem and create a roster (Wren [1971]). The roster is a cycle of daily shifts for a week, or longer, which a crew works in sequence. The roster is usually constructed in such a way so as to ensure that rest days occur at regular intervals, that there is a minimum interval between consecutive shifts and that the weeks of different shifts are alternated. In a simplified case, the operator simply rotates through all the shifts on the roster so that after doing one cycle of the roster, all the operators have, in theory, all the same amount of work. In practice, absenteeism and annual leaves cause considerable uneveness in the distribution of work. In addition, the introduction of new  schedules and consequently new  rosters, causes  even more disruption to the work pattern, although new rosters should be designed to keep this to a minimum. Thus the effects of uneven distribution of work are much more complicated to control when large rosters are being handled.  52  The days-off problem is thus required is to perform the function of a roster and to compensate for uneven work distribution caused by absenteeism and changes to schedules. The system has to work out which operators are available for work and what work has to be done. The two sets are then matched according to the criteria that would apply to the rosters and also taking into account the even distribution of work. Because a roster should enable staff to see well in advance what shifts they are to work, the system must be able to produce a provisional roster two weeks ahead of when the work is required to be done. The roster is updated two weeks later in. order to compensate for changes due to absenteeism.  Certain rules govern the grouping of weeks into a rotating roster, thus we have to consider the following details before a crew roster can be set up: 1. The number of shift weeks (cycles) required for this case: 2 weeks. 2. The number of days-off for the period is 3 days. 3. The maximum number of consecutive working days,in this case 6 days.  Shift rostering must again take into account government restrictions and company regulations. The ultimate aim is to minimize the number of operators on the payroll to satisfy the half-hourly requirements over the bi-weekly period.  53  4.2  Requirements for the Days-off problem  As in the daily shift scheduling problem, the model for the days-off problem is based on a given requirements (r). In particular, the parameter (r) might be t t determined from a service level analysis of demands for service on day t Nevertheless, some care must be taken in quantifying the "demand on day t". For a mass transit system, the daily train operating schedules indicates how many operators will be needed and this quantity can be converted to a specific demand for the days-off problem.  A more direct approach to obtain daily requirements  is to use the daily  staffing allocation yielded by the solution of the daily shift scheduling problem. There is clearly a need to link the days-off scheduling problem with the daily shift scheduling problem. In principle, there is an inescapable relationship between the two and the implication is that they should be solved in an integrated fashion. An example of an integrated model can be seen in the paper by Guha and Browne [1975]. This integrated model has not yet been fully achieved, so usually the two problems are dealt with separately as in this study. The approach taken to somewhat link the two is to solve the daily scheduling problem first Its allocations are then taken as requirements to be the input in the days-off scheduling problem.  54  4.3  Formulation of the Days-off problem  Starting on Sunday of week 1, index each day successively by t, 1 <= t <=  T, index all possible patterns k; 1 <=  k <=  K. We can thus define the  days-off scheduling problem as follows: The days-off pattern matrix A= [a ] tk where a* = tk  1  if the t-th day falls in the work period of pattern k  0  otherwise.  Let s* be the number of operators assigned to the days-off pattern k. k Let r* be the number of operators required on the t-th day of the 2-week period, t (the r* are taken from the results of the first shift scheduling problem.) t  55  The formulation is as follows:  Min (SUM s* : k  k = l,2,  K)  Subject to SUM  (a* s* : k = l,2,...K) >= r* tk k t t=l,2, ,T.  with s* nonnegative integers, k  This is a relatively small problem with only 17 variables and 14 constraints thus this problem can be solved directly using integer programming.  The structure of the A matrix is shown in Figure 3 below.  FIGURE 3  PATTERN MATRIX OF THE DAYS-OFF SCHEDULING PROBLEM  1 1 1 1 1 1 1 1 1 1 1 1 1 1 1' 1 1' 1 1 1 1 1 ' 1 1 1 1 1 1 1 11 1 1 » 1 1 1' 1 1 1 1 1 1 ' 1 1 1 1 1 I ' 1 1' 1 1 II ' 1 1 1 1 1 1 ' 11 1 1' 1 1 ' 1 1 1 1 1 1 1 1 1 1 1 1 ' 1' 1 1 1 ' 1 1  1 1 1 1 1 1 1 1 1 1 1 1 1 1 I ' 1 1' 1 1 1 II ' 1 1 1 1 1 1 1 ' 1 1 1 1 1 '1 1 ' 11 1 1 1 1 1 ' 1 ' 1 1 1 1 1 ' I ' 1 1 1' 1 1 II 1 1 1 1 1 1 1 1 ' 1 1 1 1 1 1' 1 1 ' 1 1 1 1 1 1 1 1 11 1 1 1 1 1 1 ' 1 ' 1 1 1 1' 1 1 1  57  4.4  Generating Feasible Bi-weekly Schedules: Allocation of Daily Shifts to patterns  in the Roster  As discussed earlier, a roster is constructed so as to ensure that restdays occur at regular intervals and to ensure that operators have equally desirable and equitable schedules. In a simplified case, the operators simply rotate through all the shifts on the roster or all the shifts in the daily schedules. More sophisticated systems which allow preferences of individual workers, subject to certain feasibility constraints, may be possible. For example, a preference scheduling system for nurses is discussed by Miller [1976].  However in the absence of more specific information pertaining to the rules for the roster of operators on a bi-weekly basis, we have come up with a very simplified rule-of-thumb which assigns daily shifts to meet the requirements of the bi-weekly roster. First the operators in the weekday, Saturday and  Sunday schedules are  categorized into the seven major shift types i.e. the 5-hour operators, the 5 1/2-hour operators, the 6-hour operators etc. For each roster pattern in the days-off solution, assign the operators to the daily shifts so as to meet the requirements of the seven categories. On certain days of the week, the operator may need to change to different shift type to meet the requirements of a particular category in that day. However for the bi-weekly period, we would like to keep the operator to the same daily shift type throughout that period. That is, we will like to keep a particular pattern k operator to a particular shift type M, N, P, Q, S, T, or R for the entire bi-weekly period. Then to give all the operators an equitable schedule, in each month, we will pair the shortest shifts together with the longest shifts. For example, pair the 5-hour  58  shifts (i.e. M variables) with the 9 1/2-hour shifts; the 5 1/2-hour shifts with the 7 1/2-hour shifts etc. The aim here is to try to get all the operators to work as many hours in a month so that their monthly pay will be more equitable. The list of bi-weekly patterns for the roster and an example of assigning daily shifts to the biweekly roster are discussed and shown in Section 5.4.1.  59  5  PRELIMINARY IMPLEMENTATION  In the preceding chapters, we presented a simple model and a simple procedure fo solving the crew scheduling problem for the Singapore MRT  system. As mentioned  above, crew schedule is comparatively slow and cumbersome if done "by hand", but crew scheduling prompt and efficient if it can be computerized. We  did not in this  thesis produce a single program to process all the different stages of the scheduling problem. Instead, a number of simple programs and packages and a few simple heuristics and rules-of-thumb were used to come up with a daily shift schedule and a bi-weekly roster.  5.1  The Use of a Matrix Generator  The generation of all the possible shifts covering the set covering model for the daily scheduling problem can be a tedious and time consuming task if done manually even though the number of constraints may be relatively small. Moreover the potential for error is very great Thus to automate this repetitive part of the construction of the model, and to concentrate only on the structural aspects, a matrix generator was used to generate all the shifts (variables).  The advantages of such a program for building the model are: 1.  Data for the matrix generator can be presented in a more realistic form bearing the practical application in mind.  2. Repetitive aspects of the formulation can be automated by the program.  60  3. Formulation errors are less likely to occur. 4. Modification to the model with new data are more straightforward.  The matrix generator used in this study is a special purpose built one for the set covering formulation of the daily crew scheduling problem. The matrix generator program is shown in Appendix D.  The program is written in FORTRAN. It only has to read in the data for the right-hand side and it will generate the input matrix to cover the daily scheduling problem when it is called into the linear programming package UNDO as a subroutine. (LINDO was written by and the copyright owned by Linus Schrange of the University of Chicogo.)  The program first reads in the right-hand side from an external file. It then starts to generate the rows of the input matrix. After defining the objective function, the program starts to define the constraint rows. The program then generates the variables for the constraint matrix. There are 7 sets of different variable types. The first set of variables generated are the 5-hour split-shift operators. In this set there are 3 subsets of different pattern types, and within each subset there are 8 different possibilities for break periods. The program first varies the break periods then goes on to vary the shift pattern. When all the variables of the first set are generated, the program then goes on to generate the 6 other different sets of variables i.e the 5 1/2, 6, 6 1/2 etc. hour operators in a similar fashion.  61  The matrix generator takes 2.543 seconds to generate the 2391 variable input matrix for the half hour daily shift scheduling problem on the University of British Columbia Amdahl 470 V/6-II.  After using the matrix generator to generate the input matrix for the daily scheduling problem, we use the UBC linear programming package LINDO to solve for the LP relaxation. If the results of the daily scheduling problem are not integer (i.e. fractional), the 3 heuristics discussed previously have to be applied to round off the fractional parts of the solution.  5.2  Conversion Program  A small program was written in PASCAL to automate the process of reading the fractional parts of the solution, reformulating and generating the input matrix for the third heuristic (Zero-one integer programming heuristic). See Appendix E for the conversion program. This program will read in the fractional parts of the solution from the LP relaxation. It will add up the fractional values of the variables in each row to get the values for the right-hand sides. It will then generate the small zero-one integer program input matrix for heuristic 3. This input matrix in diverted into an output file which can then called into LINDO and solved directiy as a zero-one integer program. After solving this small zero-one integer program, we can round off the fractional solutions of the LP relaxation up or down to obtain integer results to  62  the set covering model for the daily scheduling problem.  Since the input matrix to the days-off problem is relatively small, a matrix generator was not used. The integer programming option available in UBC LINDO was directly used on the days-off problem for solving the set covering formulation.  For generating the detailed daily schedules and bi-weekly rosters, the two simple procedures as described in Section 3.7 and 4.4 respectively were applied. These two procedures were relatively simple to do manually. They could however be easily converted into programs so that the detailed scheduling procedures can be computerized.  63  5.3  Results for the Daily Scheduling Problem  5.3.1  The Linear Programming Relaxation Solution  The model includes all conditions for the full half-hour problem except the integrality constraint The LP solution that appears is, most of the time, not integer. This type of a solution is clearly not realistic without the integrality constraint, however, in some cases, the LP solution may be integer.  5.3.2  The Linear Programming Relaxation with Rounding-off Heuristic Solution  After the LP relaxation is solved, the 3 heuristics discussed previously were used to round-off the fractional parts of the solution to zero or one, so as to meet the integrality constraint.  The work done concentrates on the weekdays (i.e. Monday to Friday), Saturday, and  Sunday schedules supplied  by the Singapore Mass Rapid Transit Provisional  System.  For the different heuristics used, heuristic 3, the zero-one heuristic gives the best results.  64  Table 3 summarizes the optimum results for the LP relaxation together with the 3 different heuristics used for the 4 different sets of Weekday, Saturday and Sunday schedules. The first set of data follows the original set requirements for the train schedules given.  To examine the effects of changes in different demand patterns, 3 other sets were simulated for the weekday, Saturday and Sunday schedules. The second set increases the requirements at the two peaks and the third set smooths out the fluctuations between the peaks and the troughs. Finally, the fourth set lowers the troughs for the mid-day time interval. These 3 other sets we generated by varying the original data given in the report by the Provisional Mass Rapid Transit Authority of Singapore. . 71  It can be seen from table 3 that up to 495 half-hours (i.e. 247.5 man-hours) and 43 weekday operators are required to man the weekday schedule. For Saturday and  Sunday 554 half-hours and 430 half-hours (i.e. 277 man-hours and 215  man-hours) and 49 and 41 operators are required respectively.  Figure 4 presents the list of daily shifts generated by the LP relaxation and the heuristic 3 round off algorithm for the first set of Weekday schedules. Figure 5 shows part of the detailed daily schedule of assigning operators to trains for both the Ang Mo Kio and Outram Park stations generated by the simple heuristic procedure discussed in Section 3.7.  65  Table 4 summarizes the total number of operators and the number of shift types required to man these four different sets of Weekday, Saturday and Sunday schedules.  TABLE 3  CTl CTi OPTIMAL RESULTS OF THE LP RELAXATION THE SHIFT SCHEDULING PROBLEM  SET tt o f half hours  1  AND  THE  3 DIFFERENT HEURISTICS  SET 2  FOR  SET 3  SET 4  WKD  SAT  SUN  WKD  SAT  SUN  * WKD  SAT  SUN  WKD  SAT  * SUN  4G8  519  424  494  550  458  471  507  421  443  49G  393  596  716  539  614  757  458  662  654  580  573  660  393  481  554  404  527  576  458  505  535  451  513  508  393  469  552  430  495  554  458  472  510  427  448  497  393  LP  RELAX.  HEURI. 1 HEURI . 2  HEURI. 3  * T h e LP r e l a x a t i o n f o r t h e Sunday s c h e d u l e s resu1ts.  f o r s e t 2 and s e t 4 has  integer  67  > X.  LU 3 o 1UJ Ul  _1 <  Z  C3 D: o I iCC  O J s. D  0) ••~ u_  O U_ Q LU 1 < D: LU z o LU —1 Z5 Q LU I o in > <  Q  OOO o - o o o O O O O CM ooo ooo o o o o o O CM CM CM CM CM CM CM CM CM O o o O CM CM CM CM O o o *- o CO CO OOO OOO ooo ooo o o CO CO CO CO CO CO o o o o •q- T O O O f O co co CO CO CO o o o o o OOO o o o o o OOO o o O O O O O O O CM OOO O - O O O OOO o o  D. CMCT)05 0. ••- 0) 0) o. co co a. *- io t0. O co co D. O co in Z f OO Z n in i Z CN 0) 1 Z CM CO 10 Z CN 15 CM 2 CM CM 0) Z ^ CO CO Z ••- t- co z Z Z Z £  ••- o O CD LP O in cn O CM CO CO — t CM  1- LU U. 01-1 > I 1-  o oo CM CM o CM O O O O o O O O O O CM OOO O O o OOO O O o CO CO o o o o *- o o o o o O co co CO CO CO OOO o o o ooo o oo ooo o oo ooo o oo O O co CO CO co OOO o o o CM CM CM o o o OOO o o o O O O CO CO CO  oo oo oOO- - - - - o oo o o o o o o O O O CM CM CM CM CM CM o o oo oo oooo o o o o o o o o o o CM CM CM CM CM CM CM O CM CM CM CM CM CM O O o o O O o o o o o CM CM CM CM CM CM CM CM O O O o o o o oOOOOOO - Oo oo o o O O O O O co co OOo oo o oOOOOboo - oo o CO o o o o o o o O O o o O co CO CO o o o co co CO CO CO O O o o O O o o o - OO o o o o o o o o o O O o o O t -ao oo o o O O O co co co co CO CO o o o o o o o o o O O O O O o o o o o o CO CO O O O O o o o o o o O -ao o o O O O O O CM CM CM CM CM CM CM O oo o o oo oOO CO co co o o o o o o o o o o o o o  < T  o o o o o o o o o  o o o o o o o o o  CO CO  o o o o  o o o o  CO CO  o o o o o o  o o o o o o o o o o o o o o  o o o o o o o o o o o o o o  o o o o o o o o o o o o o o  o o o o o o o o o o o o o o CO CO CO o 1- T •qo o o o o o o o CO CO CO CO  o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o coocoocoocoocoocoocoocoocoocoocoocoocoocoocoocoocoocoo lot^t^cococflcnoO'- *- c M C N C o c o T f r f i n t n c i i c i i i ^ r - c o c o c n c n o o - — ' - C M C M C O C O ^  aO >-  OOOOOOO'-'-^'-'-'-'-'-'-'-'-'-'-'-'-'-'-'-'-'-CVCMCNCNCilnCNMCN  oI o I o I o I o o LU < oI oIoIoIoIoIoIoIoIoIo Io Io Io Io Io Io Io Io Io Io Io Io Io Io Io Io Io I i o i o ii Ooocoocoocoocoocoocoocoocoocoocoocoocoocoocoocoocooro co^o^^(X)cOl^)(nOO^^cNc^lnn4^LnL^lco^^^oc^)0)cIlOO'-'-CNC^lnc ) ,  OOOOOOOO'-'-'-'-'-'-'-'-'-'-'-'-'-'-'-'-'-'-'-'-cMiNCNPiMMMn  CC  3 o I U_ _l < I HE  Q LU I u  -•—! LU _l z> Q X o in I i3  hz o o _l =>  o X U_ o O c/> Q lf> UJ cc _J o O< LU cc I LU o a I/)o or u .  o I  o cc  u . CO  -1 £ < I Z ii ll O  Figure 5  D a i l y schedule  D a i l y Schedule  Operator assigned N229a N262a N262c N409 P088b N1 73a N262b N1 73b P088a N1 73c N229a N1 88a N262a N262c N409 P088b P0'3 5 N1 88c N1 88d N262b N1 73a P088a N1 73b N1 73c Nl88b N1 88c N354a N354b N294 N229a N262a N262c N409 P088b P035 N1 88a N1 88c P1 67a  f o r the t r a i n  operators  f o r o p e r a t o r s a t Ang Mo K i o S t a t i o n  Time to leave  6.000 6.060 6. 1 20 6. 180 6.240 6.300 6.350 6.400 6.450 6.500 6.550 7.000 7.040 7.080 * 7. 1 20 7 . 1 60 7.200 7.240 7.280 7.310 7.340 7.370 7.400 7.430 7.460 7.490 7. 520 7.550 7.580 8.010 8.035 8.060 8.085 8.110 8. 1 35 8. 1 60 8.185 8.210  Time arr ives at other s t a t ion  Time ready to leave  6.225 6.285 6.345 6.405 6.465 6. 525 6.575 7.025 7.075 7. 125 7. 175 7.225 7.265 7.305 7.345 7.385 7.425 7.465 7.505 7.555 7.585 8.015 8.045 8.075 8. 105 8.135 8. 1 65 8. 195 8.225 8.255 8.280 8.305 8.330 8.355 8.380 8.405 8.430 8.455  6.260 6.320 6.380 6.440 6.500 6.560 7.010 7.060 7.110 7. 160 7.210 7.260 7.300 7.340 7.380 7.420 7.460 7.500 7.540 7.590 8.020 8.050 8.080 8.110 8. 140 8. 170. 8.200 8.230 8.260 8.290 8.315 8.340 8.365 8.390 8.415 8.440 8.465 8.490  69  N1 88d N354c N262b N1 73a Nl73b N1 73c N023  8.235 8.260 8.290 8.320 8.350 8.380 8.410  8.480 8.505 8.535 8.565 8.595 9.025 9.055  8.5156 8.540 8.570 9.000 9.030 9.060 9.090  D a i l y s c h e d u l e f o r o p e r a t o r s a t Outram Park S t a t i o n  Operator assigned N262b P088a N229a N262a N262c N409 P088b P035 N1 73a N262b N1 73b P088a N1 73a N1 88b N1 88d N229a N294 N262a N262c N409 P088b P035 Nl88a  Time to leave  Time arrives at other stat ion  Time ready to leave  6. 1 00 6.200 6.300 6.350 6.400 6.450 6.500 6.550 7.000 7.040 7.080 7. 120 7. 1 60 7.200 7.240 7.280 7.310 7.340 7.370 7.400 7.430 7.460 7.490  6.325 6.425 6.525 6.575 7.025 7.075 7. 125 7.175 7.225 7.265 7.305 7.345 7.385 7.425 7.465 7.505 7.555 7.585 8.015 8.045 8.075 8. 105 8. 135  6.345 6.445 6.545 6.595 7.045 7.095 7. 145 7. 195 7.245 7.285 7.325 7.365 7.405 7.445 7.485 7.525 7.575 8.005 8.035 8.065 8.095 8. 125 8.155  x  N1 88c N1 88d N354c N262b N1 73a P088a N1 73b N1 73c N023 N1 88b N188C  N354a N354b N294 N229a N262a N262c N409 P167b  7.520 7.550 7.580 8.010 8.035 8.060 8.085 8.110 8. 135 8. 160 8. 185 8.210 8.235 8.260 8.290 8.320 8.350 8.380 8.410  8. 165 8. 1 95 8.225 8.255 8.280 8.305 8.330 8.355 8.380 8.405 8.430 8.455 8.480 8.505 8.535 8.565 8.595 9.025 9.055  8. 185 8.215 8.245 8.275 8.300 8.325 8.350 8.375 8.400 8.425 8.450 8.475 8.500 8.525 8.555 8.585 9.015 9.045 9.075  TABLE 4  NUMBER OF OPERATORS AND SHIFT TYPES REQUIRED TO MAN FOR THE SHIFT SCHEDULING PROBLEM  SET  1  THE SCHEDULES  SET 2  SET 3  SET 4  * WKD  SAT  SUN  53  58  51  H shf.  27  33  HEURI. tt o p r .  43  shf.  HEURI. # o p r .  HEURI. H o p r . 1  2  3  H  ff  shf.  SAT  SUN  53  66  40  23  26  32  45  44  46  20  26  21  42  43  19  24  * The LP r e l a x a t i o n results.  WKD  * SAT  SUN  50  57  56  17  30  31  51  40  45  23  26  17  41  43  49  20  20  24  f o r t h e Sunday s c h e d u l e s  WKD  SAT  SUN  53  61  38  29  30  30  17  46  44  43  47  38  24  28  23  27  25  17  40  42  46  38  41  46  38  17  21  26  21  25  25  17  f o r s e t 2 and s e t 4 has  WKD  Integer  72  5.4  5.4.1  Results for the Days-off Problem  Integer Programming Solution  This model takes into account the requirements of the daily schedules for Weekdays, Saturdays and Sundays and puts it into a bi-weekly formulation and solves for the integer solution to the bi-weekly crew rostering problem. The integer result is obtained direcdy through the integer option available in LINDO as this is a relatively small problem with only 17 variables (patterns). The requirements for the days-off problem are taken from the results generated by the daily scheduling problem as summarized in Table 4. The days-off problem results are summarized in Table 5.  For the original set of data, it can be seen that up to 69 operators are required per bi-weekly period on and the optimal number of operators required to be on the payroll for the bi-weekly period is 54 operators.  Figure 6 presents the list of bi-weekly patterns generated by the integer programming model for the first set of daily schedules and Figure 7 presents the bi-weekly roster generated by the simple rule-of-thumb procedure described in Section  TABLE  5  CO NUMBER OF OPERATORS REQUIRED ON THE PAYROLL OF THE 4 DIFFERENT SETS OF SCHEDULES FOR THE DAYS-OFF PROBLEM  SET  1  SET 2  SET 3  SET 4  HEURI. 69  70  71  69  56  59  58  55  54  57  54  53  1  HEURI. 2  HEURI. 3  74  FIGURE  6  BI-WEEKLY SCHEDULE GENERATED FOR THE ORIGINAL SET OF WEEKDAY, SATURDAY AND SUNDAY SCHEDULES  -OFF TYPE  S s S S S S s s S S S S 0 0 0 0 0 0 0 1 1 1 1 1 1 3 4 6 7 8 9 0 1 3 4 6  DAY SUN1 : 2 MON1 : 2 TUE1 : 2 WED 1 : 2 THR1 : 2 FRI 1 : 0 SAT1 : 0 SUN2 : 2 MON2: 2 TUE2: 2 WED2 : 2 THR2 : 2 FRI 2: 2 SAT2-: 0  6 0 6 6 6 6 6 0 0 6 6 6 6 6  6 6 0 6 6 6 6 6 0 0 6 6 6 6  8 4 8 4 8 4 8 4 0 4 8 0 8- 4 8 4 8 4 8 4 0 4 0 0 8 0 8 4  2 2 2 2 2 2 0 2 2 2 2 2 0 0  3 3 3 3 3 0 3 3 3 3 3 3 0 0  0 4 4 4 4 4 0 4 4 4 4 4 4 0  0 0 6 6 6 6 6 0 6 6 6 6 6 6  6 6 0 0 6 6 6 6 6 0 6 6 6 6  4 4 4 0 0 4 4 4 4 4 0 4 4 4  3 3 3 3 3 0 0 3 3 3 3 3 0 3  0 = DAY SHEDULED OFF = NUMBER OF OPERATORS SCHEDULED ON DAY t WITH PATTERN k.  FIGURE  7  ASSIGNING DAILY SHIFTS TD THE BI-WEEKLY SCHEDULE  DAYS-OFF S S TYPE 0 0 1 3 DAY SUN 1 :2M 6M MON1 : 2M TUE 1 :2M WED 1 :2M THR1 : 2M  S 0 4  S 0 6  S 0 7  6M  7M 4N 1N 0 1M 8N 4N 5N 1M 0 8N 4N 5N 1M 4P 8N 4N 5N 2* 1M 6N 0 4N 5N 1M 6N 8N 0 5N 6S 6N 8N 4N  cn  S 0 8  S 0 9  S 1 0  S 1 1  S 1 3  S 1 4  S 1  6  2N  3N  0  0  6N  4N  3*  2N  3N  4N  0  6P  4P  3N  2N  3N  4N  GP  0  4P  3N  2N  3N  4N  6P  0  0  3N  2N  3N  4N  6P  SUN2 : 2M 0  6N  8N  4N  2N  2N 0 3N 4P 0 4N 6P 2M 4P 0 4N 3M 0 1M 6S 4S 0 5P 3M 4M 0 GM 4M 3M  MON2 : 2M 0  0  8N  4N  2N  3N  4N  GP  TUE2 : 2M  0  8N  4N  2N  3N  4N  6P  6N  0  4N  2N  3N  4N  GP  6N  0  0  2N  3N  4N  6N  8N  0  0  0  6N  8N  4N  0  0  FRI 1 : 0 SAT 1 :0  1M 5N WED2 : 2M 1M 5N THR2 : 2M 1M 5N FRI2 : 2M 1M 5N SAT2 : 0 6S  2N 0  1M 4P 5N O 4P  3N  0  3N  GP  2N 4P 6N  4P  3N  4N  6N  6P  4P  0  0  1M 6S 5P  4S  3M  3N  0 = DAY SHEDULED OFF # = NUMBER OF SHIFT TYPE OPERATORS SCHEDULED ON DAY t WITH PATTERN k. * = SURPLUS OPERATORS.  76  6  6.1  CONCLUSION  Performance Evaluation  The values of the different heuristics used for rounding off were compared LP against z*  for each of the different cases investigated. Table 6 summarizes the  performance results. The observed percentage error bounds for heuristic 1, 2 and 3 average 34.5%, 5.69% and 0.63% with ranges of from 24.29% to 45.76%, 2.42% to 9.43% and 0.2% to 1.43% respectively. For the weekday schedules for the different cases, we have been able to produce a solution for the LP relaxation in an average of 273 LP interations and with a maximum of 299 LP iterations. For the zero-one heuristic 3, it required an average of 263 pivots with a maximum of 694 pivots.  On the University of British Columbia Amdahl 470 V/6-II, the LP solution times average 2.71 seconds with a maximum of 4.23 seconds. The total time to construct the zero-one solutions from the zero-one heuristic (i.e. heuristic 3) from the LP solution averages 3.25 seconds with a maximum of 6.91 seconds.  Table 7 summarizes the detailed computational results of the LP relaxation and the heuristic 3 zero-one integer program for the 4 different sets of Weekday, Saturday and Sunday schedules.  TABLE G  INTEGER  PROGRAMMING  OPTIMUM GAP FROM THE LP RELAXATION  WEEKDAYS  OPTIMUM  SATURDAY  SUNDAY  PERCENT *  GAP  x  SET 1  SET 2  SET 3  SET 4  SET 1  SET 2  SET 3  SET 4  SET 1  SET 2  SET 3  27.35  24.29  32.06  24.35  37.96  37.64  28.99  33.06  27.12  -  37.77  2.78  6.68  7.33  4.29  6.74  4.73  5.52  2.42  9.43  -  7.13  0.21  0.20  0.21  1.13  0.20  0.73  0.59  0.20  1.42  -  1.43  HEURI.  1 HEURI. 2  HEURI . 3  LP The  percnntage  optimum  - IP optimum  gap = LP  * T h e LP r e l a x a t i o n resuIts.  optimum  f o r t h e Sunday s c h e d u l e s  f o r s e t 2 and s e t 4 has  integer  SET 4  TABLE 7 i  |  CO  THE NUMBER OF LP AND IP ITERATIONS AND THE COMPUTATIONAL FOR THE FOUR DIFFERENT SET OF DAILY SCHEDULE RUNS  WEEKDAYS  TIMES  SATURDAY  SUNDAY *  SET  1  N  SET 2  SET 3  SET 4  SET 1  SET 2  SET 3  SET 4  SET 1  SET 2  SET' 3  SET 4  H LP  ITERAT.  299  286  221  285  248  181  188  143  132  170  108  116  TIME SEC.  4.23  2.03  3.35  3.10  3.66  2.43  3.46  1.43  2.38  2.31  3.10  1.09  155  694  700  423  656  157  103  -  0.80  1.47  5.18  5.68  2.99  1.60  1.24  -  PIVOTS TIME SEC.  *  4  3.88  T h e LP r e l a x a t i o n results.  197  2.74  f o r t h e Sunday s c h e d u l e s  f o r s e t 2 and s e t 4 has  integer  1405  6.91  79  In our work to establish methods for producing train operator schedules, our objective is to assist a manual scheduler in his job. We seek to relieve the scheduler of much of the routine work involved in constructing the schedule and to produce a schedule which can be altered easily and speedily. Hopefully with the computerization of some of the procedures described, the scheduler will be able to revise and test new  schedules more easily. We feel that the integer programming formulation with the  LP relaxation and a round off heuristic may be the best for this problem.  For all the 4 different sets generated, the schedules do not seem to follow any particular pattern. One result is that the straight shift operators do not seem to appear in any of the solutions at all. This could be because of the objective function chosen since we did not give any additional costs for working split shifts or for working long spreadovers, nor did we put in any restrictions as to the ratio of split shifts to straight shifts. We will look into this further in the next section on sensitivity analysis.  6.2  Sensitivity Analysis  In this section we would like to do some sensitivity analysis on the daily scheduling problem. Two cases are investigated in here: 1. How different cost preference allocations for split shifts will affect the solution: i.e. the sensitivity of the final solution as a function of an additive cost allocation (k) for the split shifts. 2. The effects of forcing a certain number of straight shift operators into the basis  80  i.e. the sensitivity of the optimal solution as a function of the number of split shifts in the final solution.  Sensitivity analysis was performed on the original set of weekday schedules.  Results for Case 1 can be seen in Table 8. Results for Case 2 can be seen in Table 9.  For Case 1, we can see that by giving an additive cost (k) to the split shifts, the straight shift operators start appearing in the solution. The optimal solution does not seem to increase dramatically as higher additive costs are added to the split shifts. The solution will replace the types of shifts used. In Case 2 however, the results are slightly different The optimal increases at an increasing rate when the straight shift operators are forced into the solution.  TABLE  8  S e n s i t i v i t y A n a l y s i s R e s u l t s on on t h e S p l i t S h i f t operators.  Additive  LP  cost  relax,  Hueristic  %  gap  from  the  Weekday s c h e d u l e s  - I n c l u s i o n of  Additive  k=0  k=1  k=2  k=3  k =4  opt.  468  502  524  546  568  3 opt.  469  517  529  .21  2.99  LP  opt.  .19  565  587  3.48  3.35  cost  (k)  k=5  590  594  .68  cc  TABLE  Sensitivity  9  A n a l y s i s R e s u l t s on t h e Weekday  schedules  - Forcing  i n x number  of s t r a i g h t  Number o f straight shift operators LP  0  8  11  13  17  21  opt.  4G8  47G  479  485  507  3 opt.  469  48 1  484  492  522  1.05  1.04  1.44  2.96  relax,  Heuristic  '/.error  from  LP o p t .  .21  25  32  38  42  531  575  G73  757  813  53 1  575  702  770  842  0  0  4.31  1.72  3.57  shift  operators  83  6.3  Extension of Analysis  Our  model is developed in a deterministic framework. Each production of a  schedule identifies a unique combination of inputs to be used to produce the level of service  required  by  the  mass  transit  system.  However,  sometimes  personnel  input  requirements are not always deterministic, due to absenteeism etc. Thus there must be some  way  to  estimate  the  expected resource  requirements  for  producing  a  given  schedule such as forcasting operator requirements using past data and a post processor to allow the user to override the suggested schedule by adding or deleting tricks.  Additional  constraints  may  be  imposed  to  capture  other  restrictions of  the  system. For example, short coffee or relief breaks may be needed.  Another  aspect  is  that  the  model  may  be  extended  to  include part-time  operators by redefining the possible set of tricks x* different part-time operators  available and  choose  appropriately. We consider the j schedules from a new set y* (n) j  where part-time operators can be considered together with the full-time straight and shift operator. Schedules requirements. adjustments  could also be produced and posted ahead of the based on forecast  Their  incoming  load  is  monitored  can be made, for instance, by  in  bringing  real  time  and  in operators on  further call. For  minor this  reason, it may be advisable not to insist on schedules with zero shortage. Features can be added in the LP program to assist in controlling the general level of shortage at  84  major iterations. For example, only Max [ b-t, 0 ] is added to the right-hand sides i i where (t) is the half hourly column of tolerances that may be prespecified. i In conclusion, the area of workforce scheduling should be vertically integrated not only into the vehicle scheduling and routing process but also into the planning process. Full integration of the scheduling process thus would involve "higher-level" questions  concerning  accuracy  of timing considerations, the  procedures for generating the schedules and  relationship between  the issue of solving the problems  independently. And we may to address the question of having a feedback loop to deal with employee preferences and potential errors associated with different approaches.  85  BIBLIOGRAPHY  1. Baker,K.R.," Scheduling a Full-time Workforce to Meet Cyclic Requirements", Management Science, vol. 20, (1974), pp. 1561-1568.  Staffing  2. Baker,K.R.,"Scheduling a Full-time and Part-time Staff to Meet Cyclic Staff Requirements", Operational Research Quarterly, vol. 25, no. 1, (1975), pp. 65-76. 3. Baker,K.R., "Workforce Operational  Allocation in Cyclical Scheduling Problems: A Survey", Research Quarterly, vol. 27, no. 1, (1976), pp. 155-167.  4. Baker,K.R. and Magazine,M.J., "Workforce Scheduling with Cyclical Demands and Days-off Constraints", Management Science, vol. 24, (1977), pp. 161-167. 5. Balas.E., "A Sharp bound on the Ratio between Optimal Integers and Fractional Covers", Mathematics of Operations Research, vol. 9, no. 1, (1984), pp. 1-5. 6. Balas,L.D., "Set Partitioning: A Survey" in Combinatorial Optimization, Edited by Christofides,H., Mingozzi,A., Toth.P. and Sandi.C, John Wiley and Sons, (1979). 7. Balinski,M.L., "Integer Programming: Methods, uses, computation", Science, vol. 12, (1965), pp. 253-313.  Management  8. Ball,M., Bodin,L. and Dial.R., "Experimentation with a Computerized system for Scheduling of Mass Transit Vehicles and Crew" in Computer Scheduling of Public Transport: Urban Passenger Vehicle and Crew Scheduling , Edited by A. Wren, North Holland, Amsterdam (1981), pp. 313-336. 9. Ball,M., Bodin,L. and Dial,R., "A Matching Bound Heuristic for Scheduling Mass Transit Crew and Vehicles", Transportation Science, vol. 17, no. 1, (1983), pp. 4-31. 10. Bartholdi IIIJ.J., "A Guaranteed Accurancy Rounding Off Algorithm for Cyclic Scheduling and -Set Covering" Operations Research, vol. 29, (1981), pp. 501-510. 11. Bartholdi IIIJ.J. and Ratliff.H.D., "Unnetworks, with Applications to Idle Time Scheduling" Management Science, vol. 24, no. 8, (1978), pp. 850-858.  86  12. Bartholdi IIIJ.J., OrlinJ.B. and Ratliff.H.D., "Cyclic Scheduling via Integer Programming with Circular Ones", Operational Research Quarterly, vol. 28, (1980), pp. 1074-1085. 13. Bellman, R. (ed), Press, 1963.  Mathematical  Optimization  Techniques,  no.  5,  University of California  14. BennettB.T. and Potts,R.B., "Rotating Roster for a Transit System", Science, vol. 2, no. 1, (1968), pp. 14-34.  Transportation  15. Bodin,L.D. Golden.B., Assad,A. and Ball,M., "Routing and Scheduling of Vehicles and Crew: The State of the Art", Computers and Operations Research, vol. no. 2, (1981), pp. 63-211.  10,  16. Bodin,L.D. and Dial,R.B., "Determining Vehicle and Crew Requirements for Mass Transit Systems" 1979, January. 17. BorreU-MJ. and Roes,A.W., "Crew scheduling by Computer: A Test on the Possibility of Designing Shifts for a certain Bus Line" in Computer Scheduling of Public Transport: Urban Passenger Vehicle and Crew Scheduling , Edited by A. Wren, North Holland, Amsterdam (1981), pp.237-253. 18. Brownel.W.S. and LowerreJ.M., "Scheduling of Workforce Requirements in Continuous Operations Under Alternative Labor policies", Management Science, 22, (1976), pp. 597-605. 19. Booler,J.M.P., Research  "A method  Quarterly,  vol.  for solving 26,  no.  1,  crew scheduling Problems" (1975), pp. 55-62.  20. Dantzig.G., "A comment on Edie's traffic delays at toll booths", Research, vol. 2, no. 3, (1954), pp. 339-341. 21. Dantzig,G.,  Linear  Programming  and  Extensions,  vol.  Operational  Operations  Princeton University Press, 1963.  22. Dantzig.G.B. and Fulkerson,D.R., "Minimizing the Number of Tankers to Meet a Fixed Schedule", Naval Research Logistics Quarterly, vol. 1, (1954), pp. 217-222. 23. Edie.LG., "Traffic Delays at Toll Booths" (1954), pp.  Operations  Research,  vol.  2,  no.  107-139.  2,  87  24. Fisher.M., "The Lagrangian Relaxation for Solving Integer Programming Problems", Management Science, vol. 27, (1981), pp. 1-12. 25. Foster,B.A. and Ryan,D.M., "A Integer Programming Approach to the Vehicle Scheduling Problem", Operational Research Quarterly, vol. 27, (1976), pp. 367-384. 26. Garfinkel.N.S and Nemhausser.G.L., "The Set Partitioning Problem: Set Covering with Equality Constraints", Operations Research, vol. 17, no. 5, (1969), pp. 848-856. 27. Garfinkel,N.S and Nemhausser.G.L.,  Integer  programming.  Wiley, New York (1972).  28. Geoffrion,A.M., "A Lagrangian Relaxation for Integer Programming", Programming, vol. 2, (1974), pp. 82-114.  Mathematical  29. Guha,D. and Browne J., "Optimal Scheduling of Tours and Days-off", ORSA/TSS Proceedings of the Workshop on Automated Techniques for Scheduling of Operators for Urban Public Transportation Services, Chicago (1975). 30. Hadley,D., Linear  Programming,  Addisson- Wesley, Reading, Massachusetts (1962).  31. Hartley,T., "A Glossary of Terms in Bus and Crew Scheduling", in Scheduling  of Public Transport:  Urban Passenger  Computer  Vehicle and Crew Scheduling  Edited by A. Wren, North Holland, Amsterdam (1981) pp.343-359.  32. Henderson,W.B. and Berry,W.L., "Heuristic Methods for Telephone Operator Shift Scheduling : An Experimental Analysis", Management Science, vol. 22, (1976), pp. 1372-1380.  33. Hilyard,P.M. and Wallis,H.V., "Advances in Computer-assisted Run-cutting in North America", in Computer Scheduling of Public Transport: Urban Passenger Vehic and Crew Scheduling , Edited by A. Wren, North Holland, Amsterdam (1981), pp.183-191. • 34. Hiller,F.S. and Lieberman,G.J., Introduction San Francisco (1974).  to Operations  Research,  Holeman Day,  35. Hosios,A.J. and RousseauJ.M., "A Heuristic Scheduling Algorithm", Journal of Operational Research So., vol. 31, (1980), pp. 749-753.  88  36. JachnikJ.K., "Attendance and Rostering Systems", in Transport:  Urban Passenger  Computer  Scheduling  Vehicle and Crew Scheduling  North Holland, Amsterdam (1981), pp.337-343.  of Public  , Edited by A. Wren,  37. Landis,R., " A Perspective on Automated Bus Operator Scheduling: 5 years Experience in Portland, Oregon", in Computer Scheduling of Public Transport: Urban Passenger Vehicle and Crew Scheduling , Edited by A. Wren, North Holland, Amsterdam (1981), pp. 61-70. 38. LeBlanc.L., "The Use of Large Scale Mathematical Programming Models in Transportation Systems", Transportation Research, vol. 10, pp. 419-421. 39. Lessard,R., Rousseau.J.M. and Dupuis,D., "Hastus I: A Mathematical Programming Approach to the Bus Driver Scheduling Problem" in Computer Scheduling of Public Transport: Urban Passenger Vehicle and Crew Scheduling , Edited by A. Wren, North Holland, Amsterdam (1981), pp.259-268. 40. Maier-Rothe.C. and Wolfe,H., "Cyclic Scheduling and Allocation of Nursing Staff, Socio-Econ. Ping. Ses., vol. 7, no.5, (1973), pp 471-487. 41. Marsten,R.E., " An Management  42. Miller,H.E., Research,  Algorithm for Large Scale Set Partitioning vol. 20, no. 5, (1974), pp. 774-787.  Problems",  Science,  "Nurse vol.  24,  Scheduling using Mathematical 5, (1976), pp. 857-879.  Programming",  Operations  no.  43. Mitra,G. and Welsh,A., "A Computer Based Crew Scheduling System using a Mathematical Programming Approach" in Computer Scheduling of Public Transport: Urban Passenger Vehicle and Crew Scheduling , Edited by A. Wren, North Holland, Amsterdam (1981), pp.281-296. 44. Monroe.G., "Scheduling Manpower for Service Operators." vol. 2, no. 8, (1970).  Industrial  Engineering.,  45. Morris,J.G. and Showalter.MJ., "A Simple Approach to Shifts, Days-off and Tour Scheduling Problem", Management Science, vol. 29, no. 8, (1983), pp. 442-450. 46. Murty, K.G., 1976.  Linear and Combinatorial  Programming,  John Wiley and Sons Inc.,  89  47. Parker.M. and  Smith.B., "Two  Approaches to Computer Crew Scheduling", in  Computer  Scheduling of Public Transport:  Scheduling  , Edited by A. Wren, North Holland, Amsterdam (1981), pp. 193-213.  Urban Passenger  Vehicle and  Crew  48. Piccione.C, Cherici,A., Bielli,M., and LaBella,A., "Practical Aspects in Automatic Crew Scheduling", in Computer Scheduling of Public Transport: Urban Passeng Vehicle and Crew Scheduling , Edited by A. Wren, North Holland, Amsterdam (1981), pp. 223-235. 49. PierceJ., "Applications of Combinatorial Programming Algorithm for a Class of all Zero-one Integer Programming Problems" Management Science, vol. 15, (1968), pp. 191-209. 50. Plane,D.R., McMillan,! and Claude.C, and Network Analysis  Cliffs, NJ. (1971).  for  Discrete  Management  Optimization:  Decisions,  Integer  Programming  Prentice Hall Inc., Englewood  51. RousseauJ.M., "Crew Scheduling Methods in Operational Planning of Transit Systems", Paper presented at the "1st course on Transportation Planning Models of the International School of Transportation Planning (I.C.T.S.)", Amalf, Italy, October, 1982. 52. Ryan,D.M. and Foster,B.A., "A Integer Programming Approach to Scheduling", in Computer  Scheduling of Public Transport:  Scheduling  ,  53. Salkin,H.M„  Urban Passenger  Vehicle and  Edited by A. Wren, North Holland, Amsterdam (1981), pp. 269-281.  Integer  Programming,  Cre  Addisson-Wesley, (1975).  54. Schmidt,!W. and Knight,R.L., "The Status of Computer-aided Scheduling in North America", in Computer Scheduling of Public Transport: Urban Passenger Vehic and Crew Scheduling , Edited by A. Wren, North Holland, Amsterdam (1981), pp. 17-33. 55. Segal,M., "The Operations  Operator  Research,  Scheduling Problem: A Network 22, (1972), pp. 808-823.  Flow Approach",  vol.  56. Senju,S. and Toyoda,Y., "An Approach to Linear Programming with 0-1 Variables", Management Science, vol. 15, no. 4, (1968). 57. Shepardson,F.,and  Marsten,R.E., "A  Lagrangian  Relaxation Algorithm  for the  90  Two-shift Period Scheduling Problem", pp. 274-281.  Management  Science,  vol.  26,  no.  (1980),  3,  58. Showalter,M.J. Krajewski,L.J. and Ritzman,L.P., "Manpower Allocation in U.S. Postal Facilities : A heuristic apporach", Journal of Computer Operations Research, vol. (1978), pp.141/1-141/13. 59. Spivey.W.A., Thrall,R.,  Linear  Optimization,  2,  Holt, Rienhurt and Wiston Inc, 1970.  60. Tibrewala,R, Philippe,D. and Browne,!, "Optimal Scheduling of 2 Idle Periods", Management Science, vol. 19, (1972), pp. 71-75. 61. Stern H., "Bus and Crew Scheduling (Note)", (1980), pp. 154. 62. Vadja, S.,  Mathematical  63. Vienott,A.F. and Research,  vol.  10,  Programming,  Transportation  Research,  vol.  14,  Addisson-Wesley Piblishing Co., 1961.  Wagner,H.M., "Optimal Capacity no. 4, (1962), pp. 518-532.  Scheduling  I",  Operations  64. Volksw.D. and HoffstadtJ., "Computerised Vehicle and Driver Scheduling for the Hamburger Hochnahn Aktiengesellschaft", in Computer Scheduling of Public Transport: Urban Passenger Vehicle and Crew Scheduling , Edited by A. Wren, North Holland, Amsterdam (1981), pp.35-52.  65. Ward,R.E., Durant,P.A. and Hallman,A.B., "A Problem Decomposition Approach to Scheduling the Driver and Crews of Mass Transit System", in Computer Scheduling of Public Transport: Urban Passenger Vehicle and Crew Scheduling , Edited by A. Wren, North Holland, Amsterdam (1981), pp.297-312. 66. Warner,M.D, "Scheduling Nursing Personnel According to Nursing Preference: A Mathematical Programming Approach", Operations Research, vol. 24, no. 5, (1976), pp. 842-856. 67. Warner,D. and PrawdaJ., "A Mathematical Programming Model for Scheduling Nursing Personnel in Hospitals", Management Science, vol. 19, (1972), pp. 411-422. 68. Wilson,E.J.G. and Willis,R.J., "Scheduling of Telephone Betting Operators: A case study", Journal of Operational Research So., vol. 34, (1983), pp. 991-998.  91  69. Wren,A., "A General Review of the use of Computers in Scheduling Buses and their Crews", in Computer Scheduling of Public Transport: Urban Passenger and Crew Scheduling , Edited by A. Wren, North Holland, Amsterdam (1981), pp. 3-16. 70. Wren,A. (Editor), in Vehicle  Computer  and Crew Scheduling,  71. Wren,A., Computers  in  Scheduling  of Public Transport:  Urban  Vehi  Passeng  North Holland, Amsterdam (1981).  Tranport  Planning  and Operation,  Ian Allan, London (1971).  72. System Design and Project Staging: Railyway Operation Provisional Mass Rapid Transit Authority of Singapore. Mott, Hay and Anderson Asia Pte. and Wilbur Smith and Associates in association with London Transport International Sir William Halcrow and Partners., February, 1983. 73. Carraresi,P. and Gallo.G., "Network models for vehicle and crew scheduling: Invited Review", European Journal of Operational Research, vol. 16, (1984), pp. 139-151. 74. Carraresi,P. and Gallo.G., "A multi-level bottleneck assignment approach to the bus drivers' rostering problem ", European Journal of Operational Research, (1984), pp. 163- 173.  vol.  16  93  APPENDIX B 1. T i m e t a b l e  WEEKDAY TRAIN TIMETABLES f o r Ang Mo K i o S t a t i o n  Time to leave.  Time arrives at other station  6.000 6.060 6.120 6.180 6.240 6.300 6.350 6.400 6.450 6.500 6.550 7.000 7.040 7.080 7.120 7.160 7.200 7.240 7.280 7.310 7.340 7.370 7.400 7.430 7.460 7.490 7.520 7.550 7.580 8.010 8.035 8.060 8.085 8.110 8.135 8.160 8.185 8.210 8.235 8.260 8.290  6.225 6.285 6.345 6.405 6.465 6.525 6.575 7.025 7.075 7.125 7.175 7.225 7.265 7.305 7.345 7.385 7.425 7.465 7.505 7.555 7.585 8.015 8.045 8.075 8.105 8.135 8.165 8.195 8.225 8.255 8.280 8.305 8.330 8.355 8.380 8.405 8.430 8.455 8.480 8.505 8.535  Time ready to leave  6.260 6.320 6.380 6.440 6.500 6.560 7.010 7.060 7.110 7.160 7.210 7.260 7.300 7.340 7.380 7.420 7.460 7.500 7.540 7.590 8.020 8.050 8.080 8.110 8.140 8.170 8.200 8.230 8.260 8.290 . 8.315 8.340 8.365 8.390 8.415 8.440 . 8.465 8.490 8.515 8.540 8.570  8 .320 8 .350 8 .380 8 .410 8 .440 8 .470 8 .500 8 .530 8 .560 8 .590 9 .030 9 .070 9 .110 9 . 1 50 9 .190 9 .230 9 .270 9 .320 9 .370 9 .420 9 .470 9 .520 9 .570 1 0.020 10 .070 1 0. 1 20 10 .170 10 .220 1 0.270 1 0.320 10 .370 10 .420 10 .470 1 0.520 1 0.570 1 1.020 1 1.070 1 1. 1 20 11 . 1 70 1 1.220 1 1.270 1 1.320 1 1.370 1 1.420 11 .470 1 1.520 1 1.570  8 .565 8 .595 9 .025 9 .055 9 .085 9 .115 9 . 145 .9 . 175 9.205 9 .235 9 .255 9 .295 9 .335 9 .375 9 .415 9 .455 9 .495 9 .545 9 .595 1 0.045 1 0.095 10 . 1 45 10 . 195 10 .245 1 0.295 1 0.345 10 .395 10 .445 1 0.495 1 0.545 10 .595 1 1.045 1 1.095 1 1. 1 45 1 1. 1 95 1 1.245 1 1. 2 9 5 1 1.345 1 1.395 1 1.445 1 1.495 1 1. 5 4 5 1 1.595 12 .045 12 .095 1 2. 1 45 1 2.195  9 .000 9 .030 9 .060 9 .090 9 .120 9 .150 9 .180 9 .210 9 .240 9 .270 .9 .290 9 .330 9 .370 9 .410 9 .450 9 .490 9 .530 9 .580 10 .030 10 .080 10 . 1 30 10 .180 10 .230 1 0.280 1 0.330 1 0.380 1 0.430 10 .480 1 0.530 1 0. 580 1 1.030 1 1.080 1 1. 1 30 1 1. 180 1 1.230 1 1.280 1 1.330 1 1.380 1 1.430 1 1.480 1 1.530 1 1.580 1 2.030 1 2.080 1 2.130 1 2.180 1 2.230  1 2.020 12.070 1 2.120 12.170 12.220 12.270 12.320 1 2.370 12.470 12.520 12.570 13.020 1 3.070 1 3 . 120 1 3. 170 13.220 13.270 13.320 13.370 13.420 13.470 13.520 1 3.570 14.020 14.070 14.120 14.170 14.220 14.270 14.320 14.370 14.420 .1 4 . 4 7 0 14.520 14.570 15.020 15.070 1 5.120 15.170 15.220 15.270 15.320 15.370 15.420 15.470 15.520 15.570  12.245 12.295 12.345 12.395 12.445 12.495 12.545 12.595 13.095 1 3 . 145 13.195 13.245 13.295 1 3.345 13.395 13.445 13.495 13.545 13.595 14.045 14.095 14. 145 14.195 14.245 14.295 14.345 14.395 14.445 14.495 14.545 14.595 15.045 15.095 15.145 15.195 15.245 15.295 15.345 15.395 15.445 15.495 15.545 15.595 16.045 16.095 16.145 16.195  12.280 12.330 12.380 12.430 12.480 12.530 12.580 13.030 13.130 13.180 13.230 13.280 13.330 13.380 13.430 13.480 13.530 13.580 14.030 14.080 14.130 14.180 14.230 14.280 14.330 14.380 14.430 14.480 14.530 14.580 15.030 15.080 15.130 15.180 15.230 15.280 15.330 15.380 15.430 15.480 15.530 15.580 16.030 16.080 16.130 16.180 16.230  6.010 6. 050 6.090 6. 130 6. 170 6.210 6.250 6.290 6.330 6.360 6.390 6.420 6.450 6.480 6.510 6.540 6.570 7.000 7.030 7.055 7.080 7. 105 7. 1 30 7.155 7. 180 7.205  7.230 7.255 7.280 7.310 7.340 7.370 7.400 7.430 7.460 7.490 7.520 7.550 7. 580 8.020 8.060 8. 100 8. 140 8. 180 8.220 8.260  6.235 6.275 6.315 6.355 6.395 6.435 6.475 6.515 6. 575 7.005 7.035 7.065 7.095 7. 125 7. 1 55 7. 185 7.215 7.245 7.275 7.300 7.325 7.350 7.375 7.400 7.425 7.4507.475 7.500 7. 525 7.555 7.585 8.015 8.045 8.075 8. 105 8.135 8. 165 8. 1 95 8.225 8.245 8.285 8.325 8.365 8.405 8.445 8.485  6.270 6.310 6.350 6.390 6.430 6.470 6.510 6.550 7.010 7.040 7.070 7.-100 7. 1 30 7. 160 7. 190 7.220 7.250 7.280 7.310 7.335 7.360 7.385 7.410 7.435 7.460 7.485 7.510 7.535 7.560 7.590 8.020 8.050 8.080 8.110 8.140 8. 170 8.200 8.230 8.260 8.280 8.320 8.360 8.400 8.440 8.480 8.520  97  18.300 18.350 18.400 18.4 50 18.500 18.550 19.000 19.060 19.120 19.180  19.240 19.300 19.360 19.420 19.480 19.540 20.000 20.060 20.120 20.180 20.240 20.300 20.360 20.420 20.480 20.540 21.000 21.060 21.120 21.180 21.240 21.300 21.360 21 .420 21.480 21.540 22.000 22.060 22.120 22.180 22.240 22.300 22.360 22.420 22.480 22.540 23.000 23.060 23.120 23. 180 23.240 23.300 23.450  18.525 18.575 19.025 1 9.075 19.125 19.175 19.225 19.285 19.345 19.405 19.465 19.525 19.585 20.045 20.105 20.165 20.225 20.285 20.345 20.405 20.465 20.525 20.585 21.045 21.105 21.165 21.225 21.285 21.345 21.405 21.465 21.525 21.585 22.045 22.105 22.165 22.225 22.285 22.345 22.405 22.465 22.525 22.585 23.045 23.105 23.165 23.225 23.285 23.345 23.405 23.465 23.525 24.075  18.560 19.010 19.060 19.110 19.160 19.210 19.260 19.320 19.380 19.440 19.500 19.560 20.020 20.080 20.140 20.200 20.260 20.320 20.380 20.440 20.500 20.560 21.020 21.080 21.140 21 .200 21.260 21 .320 21.380 21.440 21.500 21.560 22.020 22.080 22.140 22.200 22.260 22.320 22.380 22.440 22.500 22.560 23.020 23.080 23.140 23.200 23.260 23.320 23.380 23.440 23.500 23.560 24. 110  98  2. T i m e t a b l e f o r Outram Park S t a t i o n  Time to leave  6. 1 00 6.200 6.300 6.350 6.400 6.500 7.000 7.040 7.080 7. 120 7. 160 7.200 7.240 7.280 7.310 7.340 7.370 7.400 7.430 7.460 7.490 7.520 7.550 7.580 8.010 8.035 8.060 8.085 8.110 8. 135 8. 160 8. 185 8.210 8.235 8.260 8.290  Time arrives at other stat ion  Time ready to leave  6. 325 6.425 6.525 6.575 7.025 7. 1 25 7.225 7.265 7.305 7.345 7.385 7.425 7.465 7.505 7.555 7.585 8.015 8.045 8.075 8. 1 05 8.135 8. 165 8. 1 95 8.225 8.255 8.280 8.305 8.330 8.355 8.380 8.405 8.430 8.455 8.480 8.505 8.535  6.345 6.445 6.545 6.595 7.045 7. 145 7.245 7.285 7.325 7.365 7.405 7.445 7.485 7.525 7.575 8.005 8.035 8.065 8.095 8.125 8. 1 55 8. 185 8.215 8.245 8.275 8.300 8.325 8.350 8.375 8.400 8.425 8.450 8.475 8.500 8.525 8.555  99  8.320 8.350 8.380 8.410 8.440 8.470 8.500 8.530 8.560 8.590 9.030 9.070 -9.110 9. 1 50 9. 190 9.230 9.270 9.320 9.370 9.420 9.470 9.520 9.570 10.020 10.070 10.120 10. 170 10.220 10.270 10.320 10.370 10.420 10.470 10.520 10.570 11.020 11.070 1 1 . 1 20 11.1 70 11.220 11.270 11.320 11.370 1 1 . 420 1 1 .470 11.520 11.570  8.565 8.595 9.025 9.055 9.085 9.115 9.145 9. 1 75 9.205 9.235 9.255 9.295 9.335 9.375 9.415 9.455 9.495 9.545 9.595 10.045 10.095 TO.145 10.195 10.245 10.295 10.345 10.395 10.445 10.495 10.545 10.595 11.045 11.095 11.145 11.195 11.245 11.295 1 1 .345 11.395 1 1 .445 11.495 11.545 1 1.595 12.045 12.095 1 2 . 145 12.195  '  8.585 9.015 9.045 9.075 9.-J 05 9. 135 9.165 9. 195 9.225 9.255 9.275 9.315 9.355 9.395 9.435 9.475 9.515 9.565 10.015 10.065 10.115 I 0.165 10.215 10.265 10.315 10.365 10.415 10.465 10.515 10.565 11.015 11.065 11.115 11.165 11.215 11.265 11.315 11.365 11.415 11.465 11.515 II .565 12.015 12.065 12.115 12.165 12.215  100  12.020 12.070 12.120 12.170 12.220 12.270 12.320 12.370 12.420 12.470 12.520 12.570 13.020 13.070 13.120 1 3. 170 13.220 13.270 13.320 13.370 13.420 1 3.470 13.520 13.570 14.020 14.070 14.120 14.170 14.220 14.270 14.320 14.370 14.420 .14.470 14.520 14.570 15.020 15.070 15.120 15.170 15.220 15.270 15.320 15.370 15.420 15.470 15.520 15.570  12.245 12.295 12.345 12.395 12.445 12.495 12.545 12.595 13.045 13.095 13. 145 13.195 13.245 13.295 13.345 13.395 13.445 13.495 13.545 13.595 14.045 14.095 14.145 14.195 14.245 14.295 14.345 14.395 14.445 14.495 14.545 14.595 15.045 15.095 15.145 15.195 15.245 15.295 15.345 15.395 15.445 15.495 15.545 15.595 16.045 16.095 16. 145 16.195  12.265 12.315 12.365 12.415 12.465 12.515 12.565 13.015 13.065 13.115 13.165 13.215 13.265 13.315 13.365 13.415 13.465 13.515 13.565 14.015 14.065 14.115 14.165 14.215 14.265 14.315 14.365 14.415 14.465 14.515 14.565 15.015 15.065 15.115 15.165 15.215 15.265 15.315 15.365 15.415 15.465 15.515 15.565 16.015 16.065 16.115 16.165 16.215  16.010 16.050 16.090 16.130 16.170 16.210 16.250 16.290 16.330 16.360 16.390 16.420 16.450 16.480 16.510 16.540 16.570 17.000 17.030 17.055 17.080 17. 105 17. 130 17.155 17.180 17.205 17.230 17.255 17.280 17.310 17.340 17.370 17.400 17.430 17.460 1 7.490 17.520 17.550 17.580 18.020 18.060 18.100 18.140 18. 180. 18.220 18.260  1 6.235 16.275 16.315 16.355 16.395 16.435 16.475 16.515 16.575 17.005 17.035 17.065 17.095 17. 125 17. 155 17. 185 17.215 17.245 17.275 17.300 17.325 17.350 17.375 17.400 17.425 17.450 17.475 17.500 17.525 17.555 17.585 18.015 18.045 18.075 18.105 18.135 18.165 18.195 18.225 18.245 18.285 18.325 18.365 18.405 18.445 18.485  16.255 16.295 16.335 16.375 16.415 16.455 16.495 16.535 16.595 17.025 17.055 17.085 17.115 17. 145 17. 175 17.205 17.235 17.265 17.295 17.320 17.345 17.370 17.395 17.420 17.445 17.470 17.495 17.520 17.545 17.575 18.005 18.035 18.065 18.095 18.125 18.155  18. 185 18.215 18.245 18.265 18.305 18.345 18.385 18.425 18.465 18.505  102 18.300 18.350 18.400 18.450 18.500 18.550 19.000 19.060 19.120 19.180 19.240 19.300 19.360 19.420 19.480 19.540 20.000 20.060 20.120 20. 180 20.240 20.300 20.360 20. 420 20.480 20.540 21.000 21.060 21.120 21.180 21.240 21.300 21.360 21.420 21.480 21.540 22.000 22.060 22.120 22. 180 22.240 22.300 22.360 22.420 22.480 22.540  18.525 18.575 19.025 19.075 19.125 19.175 19.225 19.285 19.345 19.405 19.465 19.525 19.585  20.045 20. 105 20.165 20.225 20.285 20.345 20.405 20.465 20.525 20.585 21 .045 21 .105 21.165 21 .225 21 .285 21 .345 21 .405 21 .465 21 .525 21 .585 22.045 22.105 22.165 22.225 22.285 22.345 22.405 22.465 22.525 22.585 23.045 23.105 23.165  18.545 18.595 19.045 19.095 19.145 19.195 19.245 19.305 19.365 19.425 19.485 19.545 20.005 20.065 20.125 20.185 20.245 20.305 20.365 20.425 20.485 20.545 21.005 21.065 21.125 21.185 21.245 21.305 21.365 21.425 21.485 21.545 22.005 22.065 22.125 22.185 22.245 22.305 22.365 22.425 22.485 22.545 23.005 23.065 23.125 23.185  103  23.000 23.060 23.120 23. 180 23.240 23.300 23.360 23.420 23.480 23.540 24.000  23.225 23.285 23.345 23.405 23.465 23.525 23.585 24.045 24. 105 24. 165 24.225  23.245 23.305 23.365 23.425 23.485 23.545 24.005 24.065 24.125 24. 185 24.245  104  APPENDIX C  WORK RULES  I  DAILY SCHEDULING  1.  Straight  shift  meal b r e a k  2.  Maximum meal  3.  workers  work 9 1/2 h o u r s  with  '1/2  hour  i n between.  of  5 1/2 h o u r s  of u n i n t e r r u p t e d  work w i t h o u t a  break.  Split  shift  workers  work a t o t a l  o f 5 t o 7 1/2  hours  a  have a maximum s p r e a d o f s h i f t s  of  day. 4.  Split  shift  workers  12 1/2 h o u r s the  first  i . e . the e l a p s e d shift  t i m e between t h e s t a r t  t o t h e end of t h e l a s t  shift  i s 12  of 1/2  hours.  5.  The minimum d u r a t i o n  II  6.  DAYS-OFF  Working  of o f f - t i m e  between  shifts  SCHEDULLING  days p e r b i - w e e k l y p e r i o d  i s 11 d a y s .  i s 4 hr.  105  7.  Mimimum  r e s t d a y s p e r week i s 1 d a y .  106  APPENDIX  In  D  LINDO,  first  row.  to  current  the  row  to  first  The  be  row  a  i.e.  constraint using all  the >=  formulation.  the  coeffients this  The  be  rows  the  the are  column  to  need  be  be  input  defined.  makes  use  to  of  coefficients parmeteras  for a  our  of  The the  It  has  second  vector.  >  constraints  constraints of >=  ADDROW  coefficients  input  matrix,  The  the  another  for  appends  name is is  fourth  the  program  parameters  the  of  subroutine,  subroutine  which  are  option.  parameter  variable  the  The  the  is  it  generated.  various  parameter  adds  defines  therefore,  The APPCOL  first  genrated.  the  the  the  or  the  row,  one,  one.  matrix.  The  at  For  or  LINDO.  variable  third  zero  =,  as  p r o b l e m when  parmeter  fixed  of  <,  to  row a n d  is  Since  objective  zero  then in  is  a  parameter  be  first  defined.  either to  to  ADDROW.  constraints  available  the  first  defined  subroutine  program  nozero  The  objective  can  value  be  ADDROW d e f i n e s  function  APPCOL,  to  referred  the  are  the  is  minimization  defining  constraint  function  m a x i m i z a t i o n or  constraints,  After  fixes  objective  subroutine  rows same  generating  the  the  the  of  a that the  number  stored parameter  in is  107  another rows matrix  vector  and  which stores  the  generator  nonzero program  t h e numbers  entries.  Below  of  the  associated  is a listing  of  the  108  LISTING OF THE MATRIX GENERATOR PROGRAM MICHIGAN TERMINAL SYSTEM FORTRAN G(21.8) 0001 0002 0003 0004 0005 0006  USER  SUBROUTINE USER DIMENSION VAL(37),IRO(37),RHS(36) REAL NAME( 8 ),LABLE( 17 ) LOGICAL TOOBIG DATA BLANK/' '/ DATA LABLE/'0','1','2','3','4','5','6', 2'7*,'8','9','M','N','P','Q ,'S','T','R'/ ,  0007 0008 0009 0010 0011  0012 0013 0014 0015  0016 0017 0018 0019 0020 0021  0022 •0023 0024 0025 0026 0027 0028 0029  C C C  READ IN RHS FROM THE F I L E 'DT'  CALL FTNCMD('ASSIGN 90=DT;') DO 5 1=1,36 5 READ(90,800) RHS(I) 800 FORMAT( F14.6) C I N I T I A L I Z E ROWS CALL INIT C C DEFINES THE OBJECTIVE ROW C CALL ADDR0W(1, 0., TOOBIG) C C DEFINES THE CONSTRAINTS ROWS DO 1 0 1 = 1 , 36 CALL ADDROWC-1, R H S ( I ) , TOOBIG) 10 CONTINUE C C ROWS ARE COMPLETED C C SETS THE COEFFICIENTS OF THE CONSTRAINTS C DO 20 1=1,36 VAL(I+1)=1. 20 CONTINUE IR0(1)=1 DO 30 1=5,8 30 NAME(I)=BLANK C C GENERATE THE M VARIABLES C NAME(1)=LABLE(11) . NONZ=11 VAL(1)=10. IN=0 DO 130 1=1,3 DO ' 130 J=1.,8 JW=20-J DO 130 K=1,JW  109  C 0030 0031 0032 0033 0034 0035 0036  0037 0038 0039 0040 0041 0042 0043 0044 0045  0046 0047 0048 0049 0050 0051 0052 0053 0054 0055 0056 0057 0058 0059 0060 0061 0062 0063 0064 0065 0066 0067 0068 0069  c c  SET SUBSCRIPTS OF  IN=IN+1 I 1=IN/100 I2=IN/10-I1*10 I3=IN-I1*100-12*10 NAME(2)=LABLE(I 1 + 1 ) NAME(3)=LABLE(I2+1) NAME(4)=LABLE(I3+1)  C C C C  GET NONZERO COEFFICIENTS FOR CONSTRAINTS  110  120 C C C  M'S  130  THE  IT=I+3 DO 110 L=1 ,IT IR0(L+1)=K+L IL=IT+1 DO 120 L=IL,10 IROCL+1)=L+K+J+7 CONTINUE CALL APPCOL(NAME, NONZ, VAL, IRO, TOOBIG) CONTINUE GENERATE THE N VARIABLES  210  220 230  NAME(1)=LABLE(12) NONZ=12 VAL(1 ) = 1 1 . IN=0 DO 230 1=1,4 DO 230 J= 1 , 7 JW=19-J DO 230 K=1,JW IN=IN+1 11=IN/100 I2=IN/10-I1*10 I3=IN-I1*100-12*10 NAME(2)=LABLE(11+1) NAME(3)=LABLE(I2+1) NAME(4)=LABLE(I3+1) IT=I+3 DO 210 L=1,IT IR0(L+1)=K+L IL=IT+1 DO 220 L=IL,11 IRO(L+1)=L+K+J+7 CONTINUE CALL APPCOL(NAME, NONZ CONTINUE  VAL, IRO, TOOBIG)  no  0070 0071 0072 0073 0074 0075 0076 0077 0078 0079 0080 0081 0082 0083 0084 0085 0086 0087 0088 0089 0090 0091 0092 0093  c c c  NAME(1)=LABLE(13) NONZ=13 VAL(1)=12. IN=0 DO 330 1=1,5 DO 330 J=1,6 JW=18-J  310  320 C  0094 0095 0096 0097 0098 0099 01 00 0101 01 02 0103 01 04 0105 01 06 0107 0108 0109 0110 0111 0112 0113 0114 0115  GENERATE P VARIABLES  330  c p  DO 330 K=1,JW IN=IN+1 I 1=IN/100 I2=IN/10-11*10 I3=IN-I1*100-I2*10 NAME(2)=LABLE(I 1 + 1) NAME(3)=LABLE(I2+1) NAME(4)=LABLE(I3+1) IT=I+3 DO 310 L=1,IT IRO(L+1)=K+L IL=IT+1 DO 320 L=IL,12 IRO(L+1)=L+K+J+7 CONTINUE CALL APPCOL(NAME, NONZ CONTINUE GENERATE Q VARIABLES  410  420  NAME(1)=LABLE(14) NONZ=14 VAL(1 ) = 13 . IN=0 DO 430 1=1,6 DO 430 J=1,5 JW=17-J DO 430 K=1,JW IN=IN+1 I 1=IN/100 I2=IN/10-11*10 I3=IN-I1*100-12*10 NAME(2)=LABLE(I 1 + 1 ) NAME(3)=LABLE(I2+1) NAME(4)=LABLE(I3+1) IT=I+3 DO 410 L=1,IT IRO(L+1)=K+L IL=IT+1 DO 420 L=IL,13 IRO(L+1)=L+K+J+7 CONTINUE  VAL, IRO, TOOBIG)  Ill  0116 0117  430 C C C  0118 0119 0120 0121 0122 0123 0124 0125 0126 0127 0128 0129 0130 0131 0132 0133 0134 0135 0136 0137 0138 0139 0140 0141  GENERATE S  510  520 530 C C C  0142 0143 0144 0145 0146 0147 0148 0149 0150 0151 0152 0153 0154 0155 0156 0157 0158 0159 0160  CALL APPCOL(NAME, CONTINUE  IRO,  TOOBIG)  IRO,  TOOBIG)  VARIABLES  NAME(1)=LABLE(15) N0NZ=15 VAL(1)=14. IN=0 DO 5 3 0 1=1,7 DO 5 3 0 J = 1 , 4 JW=16-J DO 5 3 0 K=1,JW IN=IN+1 I 1=IN/100 I2=IN/10-11*10 I3=IN-I1*100-12*10 NAME(2)=LABLE(11+1) NAME(3)=LABLE(I2+1) NAME(4)=LABLE(I3+1) IT=I+3 DO 5 1 0 L = 1 , I T IR0(L+1)=K+L IL=IT+1 DO 5 2 0 L = I L , 1 4 IRO(L+1)=L+K+J+7 CONTINUE C A L L A P P C O L ( N A M E , NONZ, V A L , CONTINUE GENERATE T  610  NONZ, V A L ,  VARIABLES  NAME(1)=LABLE(16) N0NZ=16 VAL(1)=15. IN=0 DO 6 3 0 1=1,8 DO 6 3 0 J = 1 , 3 JW=15-J DO 6 3 0 K=1,JW IN=IN+1 I 1=IN/100 I2=IN/10-11*10 I3=IN-I1*100-12*10 NAME(2)=LABLE(11+1) NAME(3)=LABLE(I2+1) NAME(4)=LABLE(I3+1) IT=I+3 DO 6 1 0 L = 1 , I T IR0(L+1)=K+L IL=IT+1  112  0161 0162 0163 0164 0165  0166  620 C C C  630  0167 0168  0169 0170 0171 0172 0173 0174 0175 0176 0177 0178 0179 0180 0181 0182 0183 0184 0185 0186 0187 0188 0189  DO 620 L=IL,15 IRO(L+1)=L+K+J+7 CONTINUE CALL APPCOL(NAME, CONTINUE  GENERATE R VARIABLES NAME(1)=LABLE(17)  N0NZ=19 VAL(1)=19.  C  NONZ, VAL, IRO, TOOBIG)  IN=0 DO 730 1=1,3 DO 730 K=1,18 IN=IN+1 I 1=IN/100 I2=IN/10-11*10 I3=IN-I1*100-12*10 NAME(2)=LABLE(11+1) NAME(3)=LABLE(I2+1) NAME(4)=LABLE(I3+1) IT=I+7 DO 710 L=1,IT 710 IRO(L+1)=K+L IL=IT+1 DO 720 L=IL,18 IRO(L+1)=L+K+1 720 CONTINUE CALL APPCOL(NAME, NONZ, VAL, IRO, TOOBIG) 730 CONTINUE RETURN END  113  APPENDIX E  Instructions  f o r running  t h e CONVERT p r o g r a m  To r u n : $R CONVERT S C A R D S = < o l d f i l e > S P R I N T = < n e w f i l e > where < o l d f i l e > i s t h e o u t p u t f i l e o f a LINDO r u n a n d <newfile> i s the c o n v e r t e d f i l e s u i t a b l e f o r input to LINDO  The If  PASCAL this  PROGRAM  i s i n the f i l e  i s t o be r e c o m p i l e d  accidently) $r  source  execute  *PASCAL  CONVERT  CONST max i n d e x  CONVERT.SRC  (e.g. i f convert  i s destroyed  the following:  scards=CONVERT.SRC  (INPUT,  sprint=-out  spunch=CONVERT  OUTPUT);  = 40;  TYPE string vector real_vector vars name number END; var_vector rows VAR variable values, rhs num_of_vars st st s i z e  = ARRAY[1 .. 80] OF c h a r ; = ARRAY[1 .. m a x _ i n d e x ] OF i n t e g e r ; = ARRAY[1 .. m a x _ i n d e x ] OF r e a l ; = RECORD ARRAY[1 . . 5] OF c h a r ; integer = ARRAY[1 = ARRAY[1  m a x _ i n d e x ] OF v a r s ; max i n d e x ] OF v a r vector;  var_vector; real_vector; integer; rows; vector;  114  PROCEDURE I N I T I A L I Z E ( V A R v a r i a b l e : v a r _ v e c t o r ; VAR v a l u e s , r h s : r e a l _ v e c t o r ; VAR s t : r o w s ; VAR s t _ s i z e : v e c t o r ) ; VAR i, j : integer; BEGIN FOR i := 1 TO m a x _ i n d e x DO B E G I N v a l u e s [ i ] := 0; r h s [ i ] := 0; v a r i a b l e f i ] . n a m e := ' '; v a r i a b l e [ i ] . n u m b e r := 0; FOR j := 1 TO m a x _ i n d e x DO s t [ i ] [ j ] . n a m e := ' '; s t _ s i z e [ i ] := 0 END END; (* I N I T I A L I Z E *)  P R O C E D U R E R E A D _ L I NE ( V A R l i n e  string);  VAR i : integer; BEGIN FOR i := 1 TO 8 0 DO l i n e [ i ] := ' '; i := 1 • READ(line[i]); W H I L E NOT e o l n AND NOT e o f DO B E G I N INCRC i ) ; READ(line[i]) END END; (* R E A D L I N E *)  PROCEDURE S K I P _ B L A N K S ( V A R  line  VAR i , j : integer; BEGIN i := 1 ; W H I L E l i n e [ i ] = ' ' AND j := i ; W H I L E i <= 8 0 DO B E G I N l i n e [ j ] := l i n e f i ] ; INCR(i); INCR(j) END END; (* S K I P B L A N K S *)  :  string);  i < 80 DO  i := i + 1;  115  PROCEDURE G E T _ V A R S ( V A R VAR VAR VAR line i :  variable : var_vector; values : real_vector; num_of_vars : integer);  : string; integer;  BEGIN { Get t o the v a r i a b l e READLN; REPEAT READ_LINE(line) ; SKIP_BLANKS(line) UNTIL l i n e [ 1 ] = ' V ;  section  o f LENDO o u t p u t  }  { R e a d v a r i a b l e names a n d v a l u e s } num_of_vars := 1; READ_LINE(line); SKIP_BLANKS(line); W H I L E l i n e [ l ] <> ' ' D O BEGIN FOR i := 1 TO 5 DO v a r i a b l e [ n u m _ o f _ v a r s ] . n a m e [ i ] := l i n e [ i ] ; R E A D S T R ( l i n e , 2, v a r i a b l e [ n u m _ o f _ v a r s ] . n u m b e r , values[num of_vars]); v a l u e s [ n u m _ o f _ v a r s T := v a l u e s [ n u m _ o f _ v a r s ] ~~ TRUNC(values[num_of_vars]); INCR(num_of v a r s ) ; READ_LINE(lTne); SKIP BLANKS(line) END ; DECR(num_of_vars) END; (* G E T V A R S *)  PROCEDURE L I M I T S ( n a m e  : c h a r ; VAR m i n _ w i d t h , m a x _ w i d t h , m i n _ l s , max_1s, min_0s, max_0s, coefficient : integer);  BEGIN C A S E name OF 'M' : B E G I N coefficien min_width max_width m i n _ 1 s := m a x _ 1 s := m i n _ 0 s := m a x _ 0 s := END;  t := 1 0 ; := 1 2 ; := 1 9 ; 4; 10; 8; 15  116  'N'  'P'  'Q'  'S'  'T*  'R'  : BEGIN coefficien min_width max_width m i n _ 1 s := m a x _ 1 s := m i n _ 0 s := m a x _ 0 s := END; : BEGIN coefficien min_width max_width m i n _ 1 s := m a x _ 1 s := m i n _ 0 s := m a x _ 0 s := END; : BEGIN coefficien min_width max_width m i n _ 1 s := m a x _ 1 s := m i n _ 0 s := m a x _ 0 s := END; : BEGIN coefficien min_width max_width m i n _ 1 s := m a x _ 1 s := m i n _ 0 s := m a x _ 0 s := END; : BEGIN coefficien min_width max_width m i n _ 1 s := m a x _ 1 s := m i n _ 0 s := m a x _ 0 s := END; : BEGIN coefficien min_width max_width m i n _ l s := m a x _ 1 s := m i n 0 s :=  t := 1 1 ; := 1 2 ; := 1 8 ; 4; 11; 8; 14  t := 1 2 ; := 1 2 ; := 1 7 ; 4; 12; 8; 13  t := 1 3 ; := 1 2 ; := 1 6 ; 4; 13; 8; 12 t := 1 4 ; := 1 2 ; := 1 5 ; 4; 15; 8; 11 t := 1 5 ; := 1 2 ; := 1 4 ; 4; 15; 8; 10 t := 1 9 ; := 1 8 ; := 1 8 ; 8; 18; 1 ;  117  max_Os END END (* C A S E *) END; (* L I M I T S *)  PROCEDURE  := 1  : var_vector; values : real_vector; num_of_vars : integer; VAR rhs : real_vector; VAR st : rows; VAR st_size : vector);  COLUMNS(variable  VAR  i , j , min_width, max_width, min_1s, max_1s, min_0s, max_0s, width, num_1s, num_0s, coefficient,  first_eqn : integer;  BEGIN WRITE('MIN ' ) ;  FOR i := 1 TO num of_vars DO W I T H variable[iT DO B E G I N  LIMITS(name[1], min_width, max_width, min_1s, max_1s, min_0s, max_0s, c o e f f i c i e n t ) ; W R I T E ( ' ', coefficient:6, ' ', name:4); IF IF  i <> num_of_vars T H E N W R I T E ( ' + ' ) ; (i MOD 4 = 0 ) AND i <> num_of_vars  WRITELN; WRITE(' END;  ')  num_1s := min_ls; num_0s := min_0s;  width := max_width; number > width DO B E G I N number := number - width; I F width > min_width  WHILE  THEN  BEGIN  END ELSE  BEGIN  DECR(width); INCR(num_0s)  width := max_width; INCR(num_1s); num_0s := min_0s  END END;  THEN  BEGIN  118  f i r s t _ e q n := n u m b e r + 1 0 1 ; FOR j := f i r s t _ e q n TO ( f i r s t _ e q n + n u m _ 1 s - 1) DO B E G I N I N C R ( s t _ s i z e [ j - 100]); s t [ ( j - 1 0 0 ) , s t _ s i z e [ j - 1 0 0 ] ] . n a m e := n a m e ; r h s [ j - 1 0 0 ] := r h s [ j - 1 0 0 ] + v a l u e s [ i ] END; FOR  ( f i r s t _ e q n + n u m _ 1 s + n u m _ 0 s ) TO ( f i r s t _ e q n + n u m _ 0 s + m a x _ 1 s - 1) DO B E G I N INCR(st_size[j - 100]); s t [ ( j - 1 0 0 ) , s t _ s i z e [ j - 1 0 0 ] ] . n a m e := n a m e ; r h s [ j - 1 0 0 ] := r h s [ j - 1 0 0 ] + v a l u e s [ i ] END END; (* WITH *) WRITELN END; (* COLUMNS *)  PROCEDURE  j :=  s u b j e c t t o ( s t : rows; s t _ s i z e rhs: r e a l _ v e c t o r ) ;  : vector;  VAR i,  j : integer;  BEGIN { O u t p u t t h e RHS p a r t o f t h e MPS f o r m a t W R I T E L N ( ' S U B J E C T TO' ) ; FOR i := 2 TO 37 DO B E G I N WRITEC ', s t [ i , 1 ] .name: 5) ; FOR j := 2 TO s t s i z e [ i ] DO B E G I N W R I T E C + ' ,stTi , j ] .name: 5) ; I F j MOD 4 = 0 T H E N B E G I N WRITELN; WRITEC ') END END;  WRITELNC  }  >. ' , r h s [ i 1 : 1 0 : 6 )  END; WRITELN('END') END; (* S U B J E C T T O *)  (*  M  A  I  N  P  R  O  G  R  A  M  *)  BEGIN INITIALIZE(variable, values, rhs,s t , st_size); GET_VARS(variable, values, num_of_vars); COLUMNS(variable, values, num_of_vars, r h s , s t , s t _ s i z e ) ; SUBJECTTO(st, st_size, rhs) END. (* C O N V E R T *)  

Cite

Citation Scheme:

        

Citations by CSL (citeproc-js)

Usage Statistics

Share

Embed

Customize your widget with the following options, then copy and paste the code below into the HTML of your page to embed this item in your website.
                        
                            <div id="ubcOpenCollectionsWidgetDisplay">
                            <script id="ubcOpenCollectionsWidget"
                            src="{[{embed.src}]}"
                            data-item="{[{embed.item}]}"
                            data-collection="{[{embed.collection}]}"
                            data-metadata="{[{embed.showMetadata}]}"
                            data-width="{[{embed.width}]}"
                            async >
                            </script>
                            </div>
                        
                    
IIIF logo Our image viewer uses the IIIF 2.0 standard. To load this item in other compatible viewers, use this url:
http://iiif.library.ubc.ca/presentation/dsp.831.1-0096023/manifest

Comment

Related Items