بهینه سازی مبتنی بر سیستم پشتیبانی از تصمیم گیری برای برنامه ریزی خدمه در صنعت کروز

Crew members on cruise ships are hired in a global labor market, and a major cost for cruise lines is moving crew members from their home cities to the cruise ship’s departure port. Complicating the crew scheduling problem is the uncertainty due to no-shows, terminations, and other reasons for crew to terminate their contract prematurely. To address this problem, this paper describes a scheduling system that implements a two-stage planning process that first determines overbooking levels for the number of crew to offer contracts to, and then second, a goal integer programming formulation to minimize the movement cost of assigning crew to ships while maintaining adequate crew levels and a desired crew region composition. We solve actual-sized problems characteristic of the cruise industry in a reasonably short amount of time. Experiments comparing the actual crew movement costs to the system’s projected crew movement costs show that the scheduling system can consistently reduce the movement costs in the range of 9–23%, better maintain desired crew levels, and better maintain desired crew region composition.

As a service industry, cruise lines rely on having a large, well-trained crew to not only operate their ships, but also to provide the high level of guest services for which the cruise line industry is known. A single cruise ship can have between 1000 and 1500 crew members, and the largest cruise ship, operated by Royal Caribbean Cruise Lines, has 2500 crew members. In 2010, Carnival Cruise Lines, the largest cruise line, operated 93 ships with 65,000 crew. Collectively, the US based cruise industry has 167 ships and employs more than 250,000 crew members on board those ships (Anonymous, 2010). The crew are hired internationally with large recruitment centers found in the Philippines, India, Caribbean, and Eastern Europe. In addition to their salary, the cruise line pays to feed and house crew members, as well as all the expenses incurred by crew to sign on the cruise and to sign off the cruise. The latter cost, called the movement cost, is for the crew member to travel from a gateway city near their home to the departure port of the ship they are assigned to. The movement cost includes airfare, exit and entry visas, hotel, meals, and the local travel expenses incurred by the crew member to join the ship and to return home after their tour. Moving crew from their homes to the cruise port of call (and the return) is a significant cost in the cruise industry – one major cruise company makes almost 150,000 crew movements in a year and spends approximately $90 million annually just on crew movement costs. Even small percentage reductions in crew movement costs can result in substantial cost savings. Of the many costs associated with crew, only the crew movement costs are affected by the many operational decisions involved in crew scheduling. The reason is that within a given job category, for the most part, all crew members earn the same salary and are paid the same benefits. The only cost that depends upon the crew schedule is the movement costs. There can be significant differences in airfare costs, visa processing costs, and other travel-related costs depending on where the crew member is recruited from, the port he moves to in order to join the ship, and when he is scheduled to join and depart the ship. In this paper, we describe an optimization-based decision support system called LAPS1 to schedule crew so as to minimize the total cost of crew movements for the entire fleet of ships operated by a cruise line. The decision problem of scheduling crew is complex due to the many inter-related decisions, the size of the problem, and the need to maintain the high levels of service demanded in the cruise industry. The crew schedule must obey many internal business policies, international regulations, and national-level regulations depending on where the cruise ship visits. We first describe the overall system architecture and how the system is partitioned into a demand planning module and a crew scheduling optimization module. The demand planning problem is to determine how many crew members are needed on a ship. It must consider the uncertain behavior of crew members who do not show up for their assignments or who terminate their contracts early. Once demand is estimated, then crew can be scheduled to ships and itineraries. The crew scheduling problem is formulated as a goal and integer programming problem to minimize the movement cost while satisfying each ship’s demand as well as many other constraints. We do a computational analysis and parametric analysis to explain how the system works, as well as analysis of scheduling individual ships versus multiple ships simultaneously. Our results demonstrate the cruise lines can cut crew movement costs significantly while maintaining their desired level of service quality. Our primary contribution is specification of a crew scheduling system that can efficiently obtain optimal solutions for the problem sizes demanded by the cruise line. Moreover, the resulting crew schedules outperform manually generated schedules by reducing overall cost and better maintaining desired crew numbers on-board ships. The problem of crew movements in the cruise industry has not been addressed in the literature, and, in practice, none of the major cruise lines headquartered in Florida utilize any optimization in crew scheduling. This paper demonstrates a system that supports crew scheduling with optimization while maintain flexibility for human schedulers to manage the scheduling process. The paper is organized as follows: Section 1.1 describes the operations of a cruise line and how it recruits and assigns crew to ships. Section 2 reviews the related literature on employee scheduling. Section 3 presents the crew scheduling systems and its underlying models. The system is partitioned into crew demand planning with a stochastic overbooking model and then crew scheduling with an integer programming model. Section 4 presents our computational analysis. Section 5 evaluates the model including comparisons between model performance and actual performance as experienced by the cruise lines. Section 6 summarizes the main contributions of the article and makes conclusions.

Crew scheduling is a difficult task to perform because of the large size of the problem, the complexity that arises from the number of possible combinations for different schedules, the uncertainty in crew arrivals and departures, and the multiple, competing goals. In this paper, we present a decision support system called LAPS that decomposes the crew scheduling problem into two stages. Stage one is a stochastic overbooking model to compensate for unplanned factors of crew no-shows and crew early departures. Stage two is formulated as a goal, integer programming problem to find the lowest cost schedule with the smallest deviation from PAR level and region mix goals. The LAPS system lets the scheduler control the process and makes adjustments to parameters and input data as required for a particular scheduling scenario. A computational analysis using actual data from the cruise line establishes that LAPS can solve actual sized problems in a reasonable computational time. The crew scheduling system was evaluated by performing direct comparisons with the actual schedules generated and used by the cruise line. In all cases, the crew scheduling system was able to find a lower cost schedule that performed better with respect to PAR and region mix than what was generated by the human schedulers. Cost savings ranged from a low of 9% to a high of 23%, which is a significant savings on the annual cost of crew movements that is approximately $90–$150 M for the larger cruise lines. Analysis was also done on whether policy changes to pool the crew from multiple ships together would lead to benefits. The pooling analysis shows only small cost reductions are possible, and these cost reductions may not be significant enough to justify a policy change when most crew like to be reassigned to the same ship each tour. The paper contributes to operations management with the formulation of the crew scheduling problem and its decompositions into two stages to handle both unplanned and planned crew movements. The paper considers current cruise line operations that involve scheduling crew by job code and by ship individually. The job codes are organized into a promotion hierarchy such that new crew usually enter entry-level job codes such as assistant waiter and then with experience are promoted to other job codes. Future work will investigate combining job codes in the promotion hierarchy and scheduling them simultaneously. Such expansion of the problem size will probably require investigation of more efficient algorithms to solve the problem. Additionally, the crew scheduling system is being adapted to determine the optimal nationality mix to have on ships to minimize total movement cost and maximize aggregate guest satisfaction.