Equivalent Alternate Solutions for the Tour Scheduling Problem*

Achieving minimum staffing costs, maximum employee satisfaction with their assigned schedules, and acceptable levels of service are important but potentially conflicting objectives when scheduling service employees. Existing employee scheduling models, such as tour scheduling or general employee scheduling, address at most two of these criteria. This paper describes a heuristic to improve tour scheduling solutions provided by other procedures, and generate a set of equivalent cost feasible alternatives. These alternatives allow managers to identify solutions with attractive secondary characteristics, such as overall employee satisfaction with their assigned tours or consistent employee workloads and customer response times. Tests with both full-time and mixed work force problems reveal the method improves most nonoptimal initial heuristic solutions. Many of the alternatives generated had more even distributions of surplus staff than the initial solutions, yielding more consistent customer response times and employee workloads. The likelihood of satisfying employee scheduling preferences may also be increased since each alternative provides a different deployment of employees among the available schedules.     

Labor Utilization Effects of Labor Scheduling Flexibility Alternatives in a Tour Scheduling Environment

This study used a factorial experimental design and a new modeling methodology to investigate the impact of a number of labor scheduling flexibility alternatives and labor requirements characteristics on labor utilization within a tour scheduling environment. Break-placement flexibility and shift-length flexibility were found to be extremely effective in improving labor utilization for all labor requirement distributions used. Flexibility with respect to the number of days included in a tour schedule resulted in substantial improvement in labor utilization for all labor requirements distributions exhibiting daily and/or weekly variation. Surprisingly, virtually no improvement in labor utilization was achieved for any labor requirement distribution by the removal of requirements for consecutive days off. In addition, almost no improvement was found by allowing the shift start time to vary across the working days included in tours. High labor requirement amplitude was found to have a strong adverse effect on labor utilization while longer operational days were associated with improved labor utilization for all labor requirement distributions. We discuss the implications of these results for service operations management and provide suggestions for future research.     

Tour Scheduling and Task Assignment of a Heterogeneous Work Force: A Heuristic Approach

The dual problem of work tour scheduling and task assignment involving workers who differ in their times of availability and task qualifications is examined in this paper. The problem is presented in the context of a fast food restaurant, but applies equally well to a diverse set of service operations. Developing a week-long labor schedule is a nontrivial problem, in terms of complexity and importance, which a manager spends as much as a full workday solving. The primary scheduling objective (the manager's concern) is the minimization of overstaffing in the face of significant hourly and daily fluctuations in minimum staffing requirements. The secondary objective (the workers’ concern) is the minimization of the sum of the squared differences between the number of work hours scheduled and the number targeted for each employee. Contributing to scheduling complexity are constraints on the structure of work tours, including minimum and maximum shift lengths and a maximum number of workdays. A goal programming formulation of a representative problem is shown to be too large, for all practical purposes, to be solved optimally. Existing heuristic procedures related to this research possess inherent limitations which render them inadequate for our purposes. Subsequently, we propose and demonstrate a computerized heuristic procedure capable of producing a labor schedule requiring at most minor refinement by a manager.     

A New Multiperiod Multiple Traveling Salesman Problem with Heuristic and Application to a Scheduling Problem

A new multiperiod variation of the M-traveling salesman problem is introduced. The problem arises in efficient scheduling of optimal interviews among tour brokers and vendors at conventions of the tourism and travel industry. In classical traveling salesman problem vocabulary, a salesman is a tour broker at the convention and a city is a vendor's booth. In this problem, more than one salesman may be required to visit a city, but at most one salesman per time period can visit each city. The heuristic solution method presented is polynomial and is guaranteed to produce a nonconflicting set of salesmen's tours. The results of an implementation of the method for a recent convention are also reported.     

Practical scheduling for call center operations

A practical spreadsheet-based scheduling method is developed to determine the optimal allocation of service agents to candidate tour types and start times in an inbound call center. A stationary Markovian queueing model with customer abandonment is employed to determine required staffing levels for a sequence of time intervals with varying call volumes, handling times, and relative agent availabilities. These staffing requirements populate a quadratic programming model for determining the distribution of agent tours that will maximize the fraction of offered calls beginning service within a target response time, subject to side constraints on tour type quantities. The optimal distribution is scaled to reflect the total number of scheduled agents, and a near-optimal integer solution is derived using rounding thresholds found by successive one-dimensional searches. This novel approach has been successfully implemented in large service centers at Qwest Communications and could easily be adapted to other operational environments.     

不确定条件下不同交货期窗口的Job Shop 调度

研究了具有不同交货期窗口的Job Shop 的提前/ 拖期调度问题,并考虑了处理时间的不确定 性,采用三角模糊数表示处理时间的不确定性,提出了基于遗传算法的求解算法. 仿真实验验证了 算法的有效性.     

Specifying Critical Inputs in a Genetic Algorithm-driven Decision Support System: An Automated Facility*

We present a simple scheme for the automated, iterative specification of the genetic mutation, crossover, and reproduction (usage) probabilities during run time for a specific genetic algorithm-driven tool. The tool is intended for supporting static scheduling decisions in flexible manufacturing systems. Using a randomly generated (base) test problem instance, we first assess the method by using it to determine the appropriate levels for specific types of mutation and crossover operators. The level for the third operator, reproduction, may then be inferred. We next report on its ability to choose one or more appropriate crossovers from a set of many such operators. Finally, we compare the method's performance with that of approaches suggested in prior research for the base problem and a number of other test problems. Our experimental findings within the specific scheduling domain studied suggest that the simple method could potentially be a valuable addition to any genetic algorithmbased decision support tool. It is, therefore, worthy of additional investigations.     

Single process plan scheduling with genetic algorithms

AIn this paper, a genetic algorithm model for scheduling manufacturing resources is developed for the case when there is only one process plan available per job, hence there is no routeing flexibility. The scheduling objectives considered are minimizing the makespan and mean flow time. Genetic algorithms design issues are discussed and the working of the employed genetic operators is explained in detail. Parameters for the genetic algorithms used for single process plan scheduling SPPS problems are set through extensive experimentation. Finally, the genetic algorithms approach is compared with several other approaches in terms of optimality of solution and computAuthors: ing time. It was observed that in most cases the genetic algorithms approach performed better than other approaches both in terms of finding an optimal or near optimal solution as well as computing time.     

Single-machine multitasking scheduling with job efficiency promotion

Motivated by behavioural and psychological phenomena that occur in human operators, we study single-machine multitasking scheduling with job efficiency promotion. In traditional multitasking scheduling, the primary task is assumed to be interrupted by every waiting task. In this paper we take into account job efficiency promotion that helps reduce the actual interruption time. We propose two functions to model job efficiency promotion based on the job positions in a given schedule. The objective is to minimize the makespan, total completion time, and total absolute difference in completion times. We show that the problem is polynomially solvable for each objective. We also provide efficient solutions for some special cases.

     

Mixed-fleet single-terminal bus scheduling problem: Modelling,solution scheme and potential applications

Reducing pollutant emissions and promoting sustainable mobility solutions, including Public Transport (PT), are increasingly becoming key objectives for policymakers worldwide. In this work we develop an optimal vehicle scheduling approach for next generation PT systems, considering the instance of mixed electric / hybrid fleet. Our objective is that of investigating to what extent electrification, coupled with optimal fleet management, can yield operational cost savings for PT operators. We propose a Mixed Integer Linear Program (MILP) to address the problem of optimal scheduling of a mixed fleet of electric and hybrid / non-electric buses, coupled with an ad-hoc decomposition scheme aimed at enhancing the scalability of the proposed MILP. Two case studies arising from the PT network of the city of Luxembourg are employed in order to validate the model; sensitivity analysis to fleet design parameters is performed, specifically in terms of fleet size and fleet composition. Conclusions point to the fact that careful modelling and handling of mixed-fleet conditions are necessary to achieve operational savings, and that marginal savings gradually reduce as more conventional buses are replaced by their electric counterparts. We believe the methodology proposed may be a key part of advanced decision support systems for policymakers and operators that are dealing with the on-going transition from conventional bus fleets towards greener transport solutions.     

Priority Rules for Multi‐Task Due‐Date Scheduling under Varying Processing Costs

We study the scheduling of multiple tasks under varying processing costs and derive a priority rule for optimal scheduling policies. Each task has a due date, and a non‐completion penalty cost is incurred if the task is not completely processed before its due date. We assume that the task arrival process is stochastic and the processing rate is capacitated. Our work is motivated by both traditional and emerging application domains, such as construction industry and freelance consulting industry. We establish the optimality of Shorter Slack time and Longer remaining Processing time (SSLP) principle that determines the priority among active tasks. Based on the derived structural properties, we also propose an effective cost‐balancing heuristic policy and demonstrate the efficacy of the proposed policy through extensive numerical experiments. We believe our results provide operators/managers valuable insights on how to devise effective service scheduling policies under varying costs.     

A Comparison between Basic Cyclic Scheduling and Variable Cyclic Scheduling in a Two‐stage Hybrid Flow Shop

In this paper the impacts of two types of repetitive scheduling systems on the makespan in a two‐stage hybrid flow shop, which consists of one machine in the first stage and multiple process lines in the second stage, are compared. First, we analyzed, through a simulation, how the makespan is affected by the setup frequency and sequencing rules for products under two types of scheduling systems: One is repetitive scheduling with only one batch per product family per scheduling cycle (basic cyclic scheduling system). The other is repetitive cyclic scheduling with various batches per product family per scheduling cycle (variable cyclic scheduling system). Second, we compared which scheduling system is superior under various manufacturing situations. The following points were noted. (1) The superior scheduling system can be shown by a two‐dimensional diagram of the setup frequency and the imbalance in workload for processing among process lines in the second stage. (2) Variable cyclic scheduling is superior in comparison with basic cyclic scheduling when there is a large imbalance in the workload to be processed among process lines in the second stage, or the workload in the second stage is larger than that in the first stage. The result of this research provides guidelines for selecting which scheduling system should be adopted.     

Implementation of holonic scheduling and control in flow-line manufacturing systems: die-casting case study

The success of a flow-line manufacturing system depends on effective production scheduling and control. However, it has been found that current flow-line manufacturing scheduling and control algorithms lack the flexibility to handle interruptions or resource breakdowns; hence, system performance drops automatically and rapidly when interruptions occur. The objective of this research is to investigate if the performance of a flow-line manufacturing system can be improved by integrating agent-based, holonic scheduling and production control. A holonic manufacturing scheduling model has been developed and implemented into a die-casting manufacturing flow line throughout a simulation model. The analysis takes into account the comparisons of overall performances of the system models with the holonic scheduling and conventional scheduling approaches. Simulation results indicate that the holonic manufacturing scheduling and control can significantly increase the uptime efficiency and the production rate of the flow-line manufacturing system.     

Time aggregation in production control and scheduling: towards efficient decision-support systems

A software system is developed for efficient optimal scheduling and production control in process industries modelled by production departments separated by buffers in serial or recycled paths. The new concept of time aggregation presented is easily implementable allowing a very fast solution of the optimal control of buffer levels. This optimal control problem is a large scale singular one (due to the chosen cost function) conveniently solved by a special technique of hierarchical calculus:'the iterative solution of a sequence of nonsin-gular problems converging to the singular one. Numerical results applied to a pulp and paper mill show that the new algorithm is substantially faster than the one previously used. This fact allowed the development of a complete software platform, presented in the paper, composed of several modules: modelling of industrial complex, (re)configuration, simulation, optimization, user interface—aiming at the realization of a decision support system for interactive use by daily operators and in instruction activities.     

Simple policies in the economic lot scheduling problem with zero setup costs

The economic lot scheduling problem is analysed for the case when the cost of setups, but not their duration, is assumed to be zero. This would be the case when setups are performed by the machine operators, or when management's goal is holding-cost reduction. Theoretical results are presented describing when the common cycle solution of producing one lot of every item every cycle is optimal or near optimal. Computational results using simulated data are then presented which show that the common cycle solution is nearly optimal in a wide range of practical situations.     

Scheduling with flexible process plans

When a process planning module is embedded into the scheduling paradigm, the solution space of the scheduling problem is expanded due to possible generation and use of alternative process plans, i.e. the combined system of process planning and scheduling is equivalent to scheduling with flexible process plans. This flexibility provides a potential for obtaining improved schedules, but it increases the complexity of the structure of the scheduling problem. This paper describes a solution approach for the integrated system and analyses the performance of a new algorithm under various simulated scenarios.     

Knowledge-based system for selection of an AGV and a workcentre for transport of a part in on-line scheduling of FMS

The operational level of flexible manufacturing systems FMS is concerned with the detailed decision making required for real-time operation. The real-time control of FMS is extremely complex. On-line scheduling is referred to as real-time control of FMS. On-line scheduling of an FMS requires decision making in various scheduling problems such as selection of an AGV and a workcentre from a set of workcentres simultaneously requesting the service for transport of a part, selection of a new part type to be released into the system, etc. This paper describes a prototype knowledge-based system for selection of an AGV and a workcentre from a set of workcentres simultaneously requesting the service for transport of a part in on-line scheduling of FMS. The knowledge-based system is evaluated by the empirical approach. On-line scheduling of FMS gives potential advantages such as productivity and low throughput time.     

A two-stage approach for surgery scheduling

A scheduling theory model is applied to study surgery scheduling in hospitals. If a surgical patient is regarded as a job waiting to be processed, and the related surgeons, anesthesiologists, nurses and surgical equipment as machines that are simultaneously needed for the processing of job, then the surgery scheduling can be described as a parallel machines scheduling problem in which a job is processed by multiple machines simultaneously. We adopt the two-stage approach to solve this scheduling problem and develop a computerized surgery scheduling system to handle such a task. This system was implemented in the Shanghai First People’s Hospital and increased the quantity of average monthly finished operations by 10.33 %, the utilization rate of expensive equipment by 9.66 % and the patient satisfaction degree by 1.12 %, and decreased the average length of time that patients wait for surgery by 0.46 day.     

Computational results for very large air crew scheduling problems

The airline crew scheduling problem is typically formulated as a set covering problem. The Federal Express Corporation has recently implemented a heuristic crew scheduling system based on this model. The system has been implemented on an IBM 3033 computer. Computational results are presented for crew scheduling problems with up to 3000 rows and 15,000 columns. Results of operational quality are obtained in less than one hour of computer time. This model provides a prototype for a wide variety of large scale crew scheduling applications.     

基于混合流水作业组织的集装箱码头装卸作业集成调度优化

集装箱码头集疏运资源调度的对象是由岸桥、集卡、场桥所构成的多阶段一体化的集装箱装、卸、运操作系统,将该系统的调度优化基于多阶段混合流水线调度问题建立混合整数规划模型,同时考虑集装箱码头现实作业中预定义顺序、避免岸桥交叉作业、以及取决于作业顺序的切换时间等现实约束,针对问题自身的特点设计了两阶段启发式算法,得出各阶段设备的指派结果及作业顺序。通过与基于现行调度规则的调度方案以及与目标函数理论下界值的对比实验,显示了所提出的集成调度模型及求解算法能够有效降低船舶在港时间并实现集卡资源的共享,为集装箱码头集疏运资源的集成调度提供了新的思路。