Scheduling plays a crucial role in many manufacturing and service applications. Although the traditional scheduling methods take a lot of time and energy, they cannot provide optimal schedules that satisfy all business rules and constraints. Therefore, in the past decade, optimization techniques have been widely applied to different scheduling problems to obtain optimal schedules quickly. In what follows, we will introduce the most critical use cases of scheduling in manufacturing and services.
1. Scheduling in Healthcare
There is a wide variety of scheduling problems in health care. They range from surgery scheduling in operating theatres of hospitals to appointment scheduling in clinics and radiation treatment centers.
1.1 Operating Room Scheduling
The most expensive resources in a hospital are typically the operating room(s), the surgeons, and the anesthesiologists. An hour of operating room time is costly, and so is an hour of a surgeon’s time. The operating rooms in a hospital can be regarded as the hospital’s engine. More than 60% of hospital admissions are surgical operations, which stimulates the hospital managers to make much effort on the operating room management to improve the planning and scheduling of surgical resources. The surgeries drive the demand for many of the hospital’s divisions, such as the Intensive Care Units and other postoperative care units (including beds, nurses, etc.).
Common objectives in an operating theatre are minimizing the idle times of the operating rooms and minimizing the times surgeons have to wait for an operating room to become available. The decisions of operating room planning and scheduling can be roughly divided into three levels. At the strategic level, the problems involve medium and long-term demand forecasting and the operating room time allocated to medical specialties/surgeons, i.e., capacity planning problem, capacity allocation problem, and case-mix problem. Capacity planning can be described as the process of determining the number of resources necessary to meet demands cost-effectively. Capacity allocation refers to the allocation of specialties to operating-room days in the operating room management. Case-mix planning assigns the operating room time blocks among the surgical specialties in a long-term time horizon. This problem involves the number and type of surgical cases that are performed in the operating rooms. The problem is related to cyclic operating room schedules at the tactical level, i.e., the master surgical scheduling problem. At the operational level, the problem is usually the surgery scheduling problem, to determine the scheduled date, time, and specific required resources allocated to certain surgical cases, including advance scheduling, allocation scheduling, and integration of these two steps. The operational level involves short-term decision making, namely surgery scheduling problems or patient scheduling problems.
1.2 Radiotherapy Treatment Scheduling
In oncology departments, the scheduling of radiotherapy for patients plays a crucial role in ensuring the delivery of the right treatment at the right time. It is well known that a large amount of radiation can be delivered safely to a tumor if it is spread out over several weeks. This procedure saves healthy tissue from unnecessary damage and gives it time to recover. A patient has to visit the treatment center several times a week for a given number of weeks, dependent upon the treatment plan.
The scheduling of the treatment plans deals with the allocation of the patients to treatments over time, subject to all the possible constraints. The objective of outpatient scheduling is to find an appointment system for which a particular performance measure is optimized in a clinical environment. For example, an optimization model can maximize the number of patients to be scheduled, taking into account the following conditions: 1. the priority level assigned to the patient (which may depend on the “severity” of the patient’s illness), 2. the number of treatment sessions for each patient in a week, 3. the treatment sessions for each patient have to be done on consecutive, 4. each patient has to undergo the treatment for a given number of consecutive weeks.
1.3 Multi-appointment Scheduling
In multi-appointment scheduling problems in hospitals, patients need to sequentially visit multiple resource types in a hospital setting so they can receive treatment or be diagnosed. Therefore, each patient is assigned a specific path over a subset of the considered resources, and each step needs to be scheduled. The main aim of these problems is to let each patient visit the resources in his or her subset within the allotted time to receive timely care. This is important because a delayed diagnosis or treatment may result in adverse health effects. Additionally, with multi-appointment scheduling, hospitals can augment patient satisfaction, allowing the patient to visit the hospital less frequently.
Multi-appointment scheduling can be applied in several hospital departments, and the scheduling problems that arise in each of these departments are significantly different. In rehabilitation departments, patients recover from physical injuries or drug addictions. Treating patients usually require multiple specialists and devices from several departments. A visit to each of these resources must be carefully planned, which is often a complicated task that involves many human actors. The second application occurs when patients need to be scheduled for diagnostic tests. These tests usually do not take a long time so that patients can undergo multiple tests in a single day. Doing so allows doctors to diagnose patients faster. As such, most of this subset of manuscripts aims to minimize the completion time of all steps in the care chain. A third application can be found in the oncology department. Although the main research focus in these departments is on scheduling patients on the chemotherapy chairs or linear accelerators (used for radiotherapy), some research has also been dedicated to the scheduling process for the entire care pathway, including consultations with oncologists and pre-treatment stages.
1.4 Physician Scheduling
Physicians represent one of the most valuable and expensive resources in hospitals. They are considered a bottleneck in the care-providing process. Having undergone extensive training, they are qualified and specialized employees that are usually difficult to replace. As a result, physicians typically have collective labor contracts and individually negotiated agreements with their employers. These aspects lead to a partial transfer of power from management to physicians, increasing the importance for the employer to adhere to the employees’ schedule preferences and contractual agreements and provide physicians with high autonomy for task performance and sequencing. Overall, this relative balance of power between the scheduler and the employees adds exciting implications to the physician scheduling problem. As a result, modeling preferences and fairness issues is of great importance in physician scheduling. Main objectives in physician scheduling can either be financial or non-financial in nature. Financial goals are expressed in monetary units and derive from the hospital’s economic incentives. In contrast, non-financial objectives may focus on individual aspects of physicians and patients and require more sophisticated measures. For example, staff-related measures include working conditions such as the reduction of overtime hours as well as different fairness aspects such as equal distribution of workload, unpopular shift types, or weekends off.
1.5 Nurse Scheduling
Nurse scheduling is one of the highest budget expenses, not because of the number of nurses, but the excessive overtime labor and the stress associated, which results in increased costs. In addition, manual scheduling can be time-consuming and cause shortages of the workforce and unfair scheduling. Therefore, optimization can provide optimal nurse schedules within a short time that minimizes the cost and satisfies the constraints.
1.6 Home Healthcare Routing and Scheduling
In home healthcare operations, nurses are scheduled and routed to perform various services at clients’ homes. As this often requires a combination of vehicle routing and scheduling approaches, resulting optimization problems are complex and, hence, of high interest to stakeholders such as practitioners and policy-makers. Home health care planners assign nurses to clients and schedule working times. Additionally, the travel routes and arrival times of nurses to each client have to be planned. Nevertheless, although these tasks are highly complex, routing and scheduling of home health care services are often done manually, resulting in high organizational efforts and potentially sub-optimal solutions. For instance, driving time accounts for between 18% and 26% of working time, of which 22% of the driving routes were underestimated. This indicates the high potential of optimization in routing and scheduling to improve operations and lower expenses. Home health care planners face complex and challenging optimization problems on different decision levels, such as shift scheduling, staff assignment, and staff routing decisions. In most cases, heterogeneous nurses have to be assigned to heterogeneous clients, who are spread over the operational area. Therefore, various requirements potentially have to be considered, such as matching nurses’ skills and clients’ requirements, respecting preferences, various regulations, and additional real-world complications of home health care planners’ services such as continuity of care or workload balance measurements. Additionally, home health care planners’ services are often time-sensitive, e.g., insulin injections have to be administered within certain time frames, which further complicates operations. Decision-makers can consider different objectives for this type of problem, including minimizing access time, minimizing the idle time of resources, maximizing satisfaction, minimizing the time to complete all tasks, and maximizing the number of patients scheduled (with and without patient priority), etc.
2. Scheduling in Transportation
Airlines, railroads, and shipping industries need scheduling. Each mode of transportation has its own set of characteristics. Indeed, the equipment and resources involved, i.e., ships and ports, planes and airports, and trains, tracks, and railway stations, have different cost characteristics, different levels of flexibility, and different planning horizons.
2.1 Aircraft Routing and Scheduling
A significant problem faced by every airline is constructing a daily schedule for a heterogeneous aircraft fleet. A plane schedule consists of a sequence of flight legs that have to be flown by plane with the exact times at which the legs must start and finish at the respective airports. The first part of the problem (determining the sequence of flight legs) is basically a routing problem. In contrast, the second part of the problem (determining the exact times) is a scheduling problem. The fleet schedule is important since the airline’s total revenue can be estimated if the demand function of each leg is known. Moreover, the fleet schedule also determines the total cost incurred by the airline, including the fuel cost and the crews’ salaries. Given a heterogeneous aircraft fleet, a collection of flight legs that have to be flown in one day with departure time windows, durations, and cost/revenues corresponding to the aircraft type for each leg, a fleet schedule has to be generated that maximizes the airline’s profits (possibly subject to certain additional constraints).
2.2 Airport Runway Scheduling
Airport runway optimization is an ongoing challenge for air traffic controllers. Since demand for air transportation is predicted to increase, there is a need to realize additional take-off and landing slots through better runway scheduling. One of the main factors that determines the runway throughput at an airport is the required minimum separation between aircraft during landing and take-off. The dependency of separation on the leading and trailing aircraft type makes the sequencing and scheduling of landings and take-offs an important and non-trivial problem. Careful sequencing and scheduling can reduce the number of long separation times thereby opening up opportunities for new landing or take-off slots. The Aircraft Landing Problem and the Aircraft Take-off Problem seek to determine the sequence of aircraft landing on, or taking off from, the available runways at airports in order to optimize given objectives, subject to a variety of operational constraints. Scheduling of the landing and take-off of aircraft can be divided into three stages: creating an initial schedule, modifying the schedule, and freezing the schedule.
2.3 Tanker Scheduling
A cargo that has to be transported is characterized by its type (e.g., type of crude), quantity, load port, delivery port, time window constraints on the load and delivery times, and the load and unload times. A schedule for a ship defines a complete itinerary, listing in sequence the ports visited within the time horizon, the time of entry at each port, and the cargoes loaded or delivered at each port. The objective typically is to minimize the total cost of transporting all cargoes. Each ship has a specific capacity, a given draught, a range of possible speeds and fuel consumptions, and a given location and time at which the ship is ready to start a new trip. Each port also has its own characteristics. Port restrictions take the form of limits on the deadweight, draught, length, beam, and other physical characteristics of the ships. There may be some additional government rules in effect; for example, all tankers must be loaded to more than 90% of capacity before sailing.
2.4 The Train Pathing and Timetabling
In a railroad system, train pathing is concerned with the assignment of trains to links and tracks, and train timetabling allocates time slots to trains. The train timetabling problem involves determining the values of various sets of variables, namely the times of arrival and departure of a train at all stations. When a timetable is put together, there are usually some predetermined arrival and departure times for certain trains at specific stations and some preferred arrival and departure times for other trains. There is a cost (or revenue loss) associated with deviating from these preferred arrival and departure times. These important tasks were traditionally done manually, but there is an increasing move toward automated software based on mathematical models and algorithms.
2.5 Railway Crew Scheduling
The railway crew scheduling problem consists of finding the most efficient duty combination for railway crews to cover all trains and related activities for a defined period of time. Decisions on railway crew members can be classified into different planning levels. At a strategic and tactical level with a time horizon longer than one year, crew planning deals with the long-term availability and capabilities of crew members as well as the location and the capacities of crew depots (crew management). For reliable long-term operations, it is crucial to anticipate the future need of different crew types and to realize a balanced crew composition regarding age and skills. This includes decisions on hiring, training, or moving crews from one depot to another. Besides, the choice of crew depot locations including opening or closing decisions play an important role at this stage. At the operational level, crew planning is the task of building work schedules for crew members to operate a planned timetable.
2.6 Cross-Dock Scheduling
The primary purpose of a cross-dock is to enable the consolidation of differently sized shipments with the same destination to full truckloads so that economies in transportation costs can be realized. At cross-docking terminals, incoming deliveries of inbound trucks are unloaded, sorted, moved across the dock, and finally loaded onto outbound trucks, which immediately leave the terminal towards their next destination in the distribution chain. Accordingly, a cross-dock is a consolidation point in a distribution network. Multiple smaller shipments can be merged into full truckloads to realize economies in transportation. In this context, the truck scheduling problem, which decides on the succession of truck processing at the dock doors, is especially important to ensure a rapid turnover and on-time deliveries. The decision problems to be solved during the life cycle of a cross-docking terminal ordered from strategic to operational are as follows: 1. Location of the cross-docking terminal(s), 2. The layout of the terminal, 3. Assignment of destinations to dock doors, 4. Vehicle routing, 5. Truck Scheduling, 6. Resource scheduling inside the terminal, 7. (Un-)Packing loads into (from) trucks. In the special case of truck scheduling, the process of transshipment can be subdivided into the tasks of unloading inbound trucks and loading outbound trucks, which are typically separated by a time lag for material handling inside the terminal, i.e., for scanning, sorting, and moving shipments across the dock. These two tasks are to be processed by the resources ‘‘dock doors’’, which can process one truck at a time and are assumed to be sufficiently equipped with loading equipment (e.g., hand stackers or forklifts) and workers. To conclude, a dispatcher of a cross-docking terminal who seeks to solve a truck scheduling problem faces two interrelated decisions bound to some (time-related) objective function: where and when the trucks should be processed at the dock doors of the terminal.
2.7 Charge Scheduling of Electric Vehicles in Smart Grid
The number of Electric vehicles is expected to grow rapidly in the coming years. However, the uncoordinated charging of these vehicles can put severe stress on the power grid. The problem of charge scheduling of Electric vehicles is an important and challenging problem. The electric vehicle charge scheduling problem takes as input a set of electric vehicles and different grid, user, and aggregator-side parameters and outputs a charging schedule (starting and ending times of charging of each electric vehicle in the set). It is an optimization problem that optimizes some grid, user, or aggregator-side parameters (or a mix of them) subject to the different grid, user, and aggregator-side constraints. The parameters, constraints, and objective functions considered span a very wide range, giving rise to different forms of optimization problems. Different objective functions have been used in the problem formulations depending on the goals of scheduling. Some works have tried to optimize grid-side benefits such as minimizing the financial cost of power supply, minimizing grid operation cost, including the cost of wind and hydropower and availability cost for providing spinning reserves, minimizing distribution system load variance, minimizing loss in the distribution system, and maximizing the profits of thermal and wind plants while minimizing energy trading risks. Some other works have focused on optimizing electric vehicle-side benefits such as minimizing charging cost, minimizing both CO2 emission and charging cost, and maximizing user convenience. However, another class of works has focused on optimizing aggregator-side benefits, such as maximizing aggregator profits and reducing the imbalances arising out of the energy purchased by the aggregator from the day ahead.
2.8 Vessel Scheduling in Liner Shipping
Liner shipping plays a major role in freight transportation and international seaborne trade. One of the most challenging decision problems, tackled by liner shipping companies, is the design of vessel schedules. At the vessel scheduling stage, the liner shipping company aims to determine vessel sailing speeds at voyage legs of a given liner shipping route, port times, vessel handling rates at ports, the minimum number of vessels required in order to provide the agreed service frequency at ports, and other factors. Considering the existing pollution levels, the environmental impacts of liner shipping have to be captured in the vessel scheduling models as well.
Liner shipping companies deal with three levels of decision problems. The strategic-level decisions consist of long-term decisions, which are generally made with a frequency, varying from 6 months to several years, such as vessel fleet size and mix, alliance strategies, and network design. Based on changing shipment demand, tactical-level decisions are made every 3–6 months. These decisions include determination of the frequency of liner shipping services, deployment of vessels on the respective port rotations, determination of vessel sailing speeds, and design of vessel schedules. The operational-level decision problems include cargo booking, cargo routing, and vessel rescheduling due to disruptions, such as congestion at ports, adverse weather, malfunctioning of vessel engines, and others.
3. Scheduling in Entertainment
3.1 Tournament Scheduling
A key aspect of sporting events is generating schedules that optimize logistic issues and are seen as fair to all those who have an interest. Teams and leagues want to optimize their investments by playing a good schedule that seeks to meet various criteria. Good fixtures are important in order to maximize revenues, ensure the attractiveness of the games, and keep the interest of both the media and the fans. Good schedules can have significant financial implications and interfere (for the bad and the good) with the performance of every team participating in a tournament. Finding the best schedule of games is a difficult task with multiple decision-makers, constraints, and objectives (involving logistics, organizational, economic, and fairness issues).
The general problem of scheduling the games of a tournament is certainly the most studied area of sports scheduling. It consists of determining the date and the venue in which each game will be played. Applications to real-life problems in sports scheduling such as football, baseball, basketball, cricket, hockey, and others are common in the literature. However, there are also other relevant scheduling problems in sports. One of them is that of assigning referees to games, which also involve multiple objectives. One can consider different objectives for a tournament scheduling problem, including breaks optimization (A lot of league organizers restrict themselves to schedules having a minimum number of breaks), cost minimization (to find a feasible tournament schedule satisfying several constraints with minimum total costs), and avoiding that a team plays against extremely weak or extremely strong teams in consecutive rounds.
3.2 Broadcast Television Scheduling
In the scheduling of network television programs, the scheduling horizon is typically one week, and the week consists of a fixed number of time slots. A number of shows are available for broadcasting and these shows have to be assigned to different time slots in such a way that a certain objective function is optimized. Moreover, the assignment of shows to slots is subject to a variety of conditions and constraints. For example, assigning a show to one slot may affect the contribution to the objective function of another show in a different slot. Major television networks typically have a number of shows available for broadcasting. Some of these belong to a series of half-hour shows, whereas others belong to a series of one-hour shows. There are shows of other lengths as well. There are a fixed number of 30-minute time slots, implying that some shows require one-time slots, whereas others need two consecutive time slots. If a particular show is assigned to a given time slot, then a certain rating can be expected. The forecasted ratings may be based on past experience with the show and the time slot; it may be based on lead-in effects due to the shows immediately preceding it, and it may also be based on shows that competing networks assign to that same slot. The profits of the network depend very much on the ratings. So, one of the main objectives of the network is to maximize its average ratings.
4. Scheduling in Education
4.1 Exam, Course, Class, and Teacher Timetabling
Timetabling is a typical real-world scheduling activity that arises at least once a year at every educational institution. Building a weekly timetable for an institution is a tedious process that administrators usually undertake after spending several person-hours. In this effort, schedulers follow several rules, some of which are so important that they may never be violated (hard constraints) and others that are not as important and usually are obeyed only if all hard constraints are satisfied and there is still room for better solutions under some objectives for improved quality (soft constraints).
The three most common educational timetabling problem categories are examination timetabling, course timetabling, and class/teacher timetabling. The basic distinction occurs in terms of the elements to be scheduled, that is, exams, course options, or regular lessons. The examination timetabling problem consists of scheduling the exams for a set of courses over a limited time period while avoiding the overlapping of exams for each student. In course timetabling problems, for each student, a set of lectures is previously defined. Then all lectures included within the institutions’ set of courses must be scheduled in such a way that the overlapping of lectures for courses with students in common is minimized. This problem arises in universities or other educational institutions with flexible curricula.
5. Scheduling in Manufacturing
5.1 Operations scheduling for waste minimization
Sustainable production is defined as “the creation of goods and services using processes and systems that are non-polluting; conserving of energy and natural resources; economically viable; safe and healthful for workers, communities, and consumers; and socially and creatively rewarding for all working people”. Sustainable production concerns the manufacturing industry as a whole and covers many aspects such as waste management, process planning, logistics, and clean technologies. As a key factor in production efficiency, operations scheduling is one of several levers that can be used in order to address the aforementioned environmental issues, and without the need for high investment since no new machines are required. Thus, by implementing more environmentally aware scheduling, it becomes easier to enable the 3R policy (Reduce, Reuse and Recycle).
Scheduling “deals with the allocation of resources to tasks over given time periods and its goal is to optimize one or more objectives”. Those objectives typically feature economic indicators such as the makespan and production costs. In the case of sustainable manufacturing, an environmental aspect is also included, such as the environmental impact of production and the quantity of waste generated. Improvements in scheduling affect resource efficiency, and thus reduce the resource consumption and waste generation of the production process. Due to the nature of the processes and materials used, large quantities of wastewater are generated during the production and equipment cleaning steps. The two biggest types of problems encountered are the batch scheduling problem (e.g., for the production of chemicals or food products) and the hoist scheduling problem (e.g., for surface treatment). Batch scheduling, which is related to process manufacturing, occurs when several jobs can be processed simultaneously on a single machine. Its fundamental characteristic is that the batch processing time is equal to the longest processing time of the jobs included in the batch. Thus, determining the composition of a batch becomes an important factor for the overall makespan and production costs. The hoist scheduling problem deals with the scheduling of handling devices, also called hoists, mostly in electroplating lines. This includes the determination of the soaking times, the use of several tanks, and the coordination of multiple hoists on possibly conflicting routes with possible improvements regarding wastewater generation. Seminal works on sustainable operations scheduling are mostly focused on reducing the waste outputs, mainly wastewater originating from equipment cleaning.
5.2 Maintenance Scheduling in the Electricity Industry
The reliability of the power plants and transmission lines in the electricity industry is crucial for meeting demand. Consequently, timely maintenance plays a major role in reducing breakdowns and avoiding expensive production shutdowns. One of the most successful contributions of operations research to improve decision-making in equipment maintenance management is the application of optimization techniques to solve maintenance planning and scheduling problems.
Just to cite a few examples, equipment maintenance management in electric power systems is concerned with decisions such as: when to stop a generating unit for maintenance, when to restart it again, and how many resources (e.g., technicians) are to be assigned to the maintenance of a given unit during a given period. These decisions are taken under complex environments and constraints such as resource availability, demand satisfaction, and reliability thresholds. Additional constraints include but are not limited to 1. Maintenance tasks: maintenance window (possible time for maintenance), sequence, incompatibility, spacing, and overlapping of tasks. 2. Generating units: highest/lowest production levels, ramp-rate. 3. Manpower: availability for each period, requirements by maintenance tasks. 4. Resources: availability for each period, requirements, consumption by maintenance tasks. 5. Network: transmission-line capacity, voltage. 6. Demand: fully satisfied or not, meeting of demand. 7. Reliability: minimum reserve required by period, risk levels.
5.3 Production Systems with Automated Material Handling
In production systems with automated material handling, a material handling or conveyor system controls the movement of the jobs as well as the timing of their processing on the various machines. Examples of such environments are flexible manufacturing systems, flexible assembly systems, and paced assembly lines. The objective is typically to maximize throughput. Such settings are prevalent in the automotive industry and in the consumer electronics industry.
5.4 Lot Scheduling
In practice, there are many applications of economic lot scheduling. In the process industries (e.g., the chemical, paper, pharmaceutical, aluminum, and steel industries) setup costs and inventory holding costs are significant. When minimizing the total costs, a scheduling problem often reduces to an economic lot scheduling problem. There are applications of lot scheduling in the service industries as well. In the retail industry (e.g., Sears, Wal-Mart) the procurement of each item has to be controlled carefully. Placing an order for additional supplies entails an ordering cost and keeping a supply in inventory entails a holding cost. The retailer has to determine the trade-off between the inventory holding costs and the ordering costs. The lot scheduling models are used for medium and long-term production planning. In these problems, there are a variety of different products. When a machine switches from one product to another, a changeover cost is incurred. The goal is usually to minimize total inventory and changeover costs. These models are important in the process industries, such as oil refineries and paper mills.
6. Scheduling in Large Projects
Project planning and scheduling are important whenever a large project, that consists of many stages, has to be carried out. Examples of such projects are real estate developments such as the construction of a skyscraper, construction of power generation centers, software developments, launchings of spacecraft, and projects in the defense industry, such as the design, development, and construction of aircraft carriers. A project typically consists of a number of activities or jobs that may be subject to precedence constraints. The objective is to minimize the completion time of the last job, commonly referred to as the makespan. It is also important to find the set of jobs that determines the makespan, as these jobs are critical and cannot be delayed without delaying the completion of the entire project. Project scheduling models are also important in the planning and scheduling of services. Consider, for example, the planning and scheduling of a large consulting project.
6.1 Construction Scheduling
Construction scheduling is concerned with optimally sequencing activities over time and allocating resources accordingly. The duration criterion is a critical factor taken into account by a client when evaluating and selecting bids with the project deadline normally being prespecified. Contractors always strive to minimize the project duration so as to obtain an advantage during a bid’s evaluation. For example, they may ‘crash’ a project’s duration (i.e., the shortest possible time for which an activity can be scheduled) by allocating more resources (if sufficient resources are available) to expedite construction activities. However, crashing a project’s duration invariably increases the cost, as additional resources are required. Project scheduling should therefore consider time and cost simultaneously as a ‘trade-off’ exists. Thus, the original single objective optimization problem (i.e., optimal time or cost) is shifted to a bi-objective optimization problem (i.e., optimal time–cost). Another ‘trade-off’ from ‘crash’ duration is its influence on project quality. Thus, the time–cost bi-objective optimization problem could be expanded into a time–cost–quality multi-objective optimization problem, that is, minimizing the construction time and cost while maximizing the quality.
7. Scheduling in Other Services
7.1 Operator Scheduling in a Call Center
In every large organization that has a helpline or a toll-free number, there is a concern with regard to the quality of service. This is measured by the time it takes a caller to get an operator on the line, or, in the case of a conversant system that responds to digital input, by the time it takes the caller to get an appropriate person on the line. The objective is to determine a set of shifts and assignment of tasks within the shifts so that the requirement curves are matched as closely as possible by the availability of operators. The shift configurations that are allowed have a certain structure. These structures are often referred to as tour templates and are characterized by their start times, finish times, and the number, length, and timing of non-work periods.
7.2 Order Acceptance and Scheduling
The problem of order acceptance and scheduling is defined as the joint decision of which orders to accept for processing and how to schedule them. The decision-maker is faced with a collection or stream of orders whose combined processing requirements would exceed available capacity, and has the option of rejecting some of those orders. In a firm that strives to align its functions so that profit is maximized, the coordination of capacity with demand may require that business sometimes be turned away. In particular, there is a trade-off between the revenue brought in by a particular order, and all of its associated costs of processing, which may include delay costs for other orders, as well as any penalties incurred if this order is delivered after its agreed-upon due date. When the cost of capacity and per-order revenue must be reconciled, there are a number of ways that firms respond. They may expand capacity by permanent or temporary means, the latter including running extra shifts, diverting production resources, or subcontracting. Negotiation or renegotiation of delivery dates and pricing are other options.
7.3 Maintenance Scheduling
In an equipment maintenance problem, each customer that comes in requires a number of different services (e.g., repairs), that can be done concurrently and independently by the various resources. A customer can depart only after all requested services have been completed. Each customer is given in advance a time when all his services are expected to be completed; this time serves as a due date. One objective is to minimize the total weighted tardiness.
7.4 Reservation Systems and Timetabling
Reservation systems are ubiquitous. Consider, for example, a system in which customers attempt to reserve hotel rooms for specific time periods. The hotel has to decide which reservations to confirm and which ones not. This problem occurs in many other settings as well. For example, in a manufacturing setting a customer may want to reserve one or more machines for specific time periods. The exam scheduling and car rental problems are other examples of this type of problems.