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 *)
- Library Home /
- Search Collections /
- Open Collections /
- Browse Collections /
- UBC Theses and Dissertations /
- The operator scheduling for Singapore mass transit...
Open Collections
UBC Theses and Dissertations
Featured Collection
UBC Theses and Dissertations
The operator scheduling for Singapore mass transit system Goh, Lek-Oon 1984
pdf
Page Metadata
Item Metadata
Title | The operator scheduling for Singapore mass transit system |
Creator |
Goh, Lek-Oon |
Publisher | University of British Columbia |
Date Issued | 1984 |
Description | 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 asset-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. |
Genre |
Thesis/Dissertation |
Type |
Text |
Language | eng |
Date Available | 2010-05-08 |
Provider | Vancouver : University of British Columbia Library |
Rights | For non-commercial purposes only, such as research, private study and education. Additional conditions apply, see Terms of Use https://open.library.ubc.ca/terms_of_use. |
DOI | 10.14288/1.0096023 |
URI | http://hdl.handle.net/2429/24499 |
Degree |
Master of Science - MSc |
Program |
Business Administration |
Affiliation |
Business, Sauder School of |
Degree Grantor | University of British Columbia |
Campus |
UBCV |
Scholarly Level | Graduate |
Aggregated Source Repository | DSpace |
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
Cite
Citation Scheme:
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>
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