An integer programming model for hierarchical workforce scheduling problem

In this paper, an integer programming model for the hierarchical workforce problem under the compressed workweeks is developed. The model is based on the integer programming formulation developed by Billionnet [A. Billionnet, Integer programming to schedule a hierarchical workforce with variable demands, European Journal of Operational Research 114 (1999) 105–114] for the hierarchical workforce problem. In our model, workers can be assigned to alternative shifts in a day during the course of a week, whereas all workers are assigned to one shift type in Billionnet’s model. The main idea of this paper is to use compressed workweeks in order to save worker costs. This case is also suitable for the practice. The proposed model is illustrated on the Billionnet’s example problem and the obtained results are compared with the Billionnet’s model results.     

Preventive maintenance scheduling of power generating units

The problem of preventive maintenance planning of electric power generating units can be formulated as a mixed-integer linear optimization problem. An extension of the model is presented to deal with more realistic assumptions about utilization of power resource. We propose a heuristic iterative exchange procedure to solve these problems. We introduce two methods to prevent jamming situations outside the feasible domain or at a local optimum. The first method is a recursive exchange procedure called multiple exchanges method and the second relies on Lagrangian relaxation. Furthermore, we compare these procedures with a tabu search.This research was supported by NSERC (Grant A8312) and FCAR (Grant ER-0289).Michèle Charest had an NSERC Scholarship to work on this project.     

Solving a school bus scheduling problem with integer programming

In many rural areas in Germany pupils on the way to school are a large if not the largest group of customers in public transport. If all schools start more or less at the same time then the bus companies need a high number of vehicles to serve the customer peak in the morning rush hours. In this article, we present an integer programming model for the integrated coordination of the school starting times and the public bus services. We discuss preprocessing techniques, model reformulations, and cutting planes that can be incorporated into a branch-and-cut algorithm. Computational results show that in our test counties a much lower number of buses would be sufficient if the schools start at different times.     

Profit-maximization generation maintenance scheduling through bi-level programming

This paper addresses the generation maintenance scheduling (GMS) dilemma in a deregulated power system. At first, under a centralized cost minimization framework, a GMS is formulated and set as the benchmark (cost-minimization GMS). Then, the cost-minimization is changed into a profit-maximization problem of generation companies (GENCOs) and the GMS is developed as a bi-level optimization. Karush–Kuhn–Tucker conditions are applied to transform the bi-level into a single-level mixed-integer linear problem and subsequently, Nash equilibrium is obtained as the final solution for the GMS under a deregulated market (profit-maximization GMS). Moreover, to incorporate reliability and economic regulatory constraints, two rescheduling signals (incentive and penalty) are considered as coordination processes among GENCOs and independent system operators. These signals are based on energy-not-supplied and operation cost, and ensure that the result of profit-maximization GMS is in the given reliability and social cost limits, respectively. These limits are obtained from the cost-minimization GMS. Lastly, the model is evaluated on a test system. The results demonstrate applicability and challenges in GMS problems.     

Scheduling staff using mixed integer programming

This paper describes the solution of a problem of scheduling a workforce so as to meet demand which varies markedly with the time of day and moderately with the day of week. The main objectives are determining how many staff to employ and the times at which shifts should start. The problem is expressed as a large MIP problem initially presenting computational difficulties. The difficulties vanish when the formulation is modified and a package allowing the use of reduce and (especially) special ordered sets becomes available. The client has commissioned the study primarily to benchmark its existing schedule by comparing it with a theoretical optimum. The optimal schedule and comparison are very sensitive to technical and cost coefficients which are not precisely known.     

A sequential integer programming method for discontinuous labor tour scheduling

General set-covering formulations (GSCFs) of labor tour scheduling problems have recently received substantial attention in the research literature. The most successful heuristic approaches to these problems have used the linear programming (LP) solution to the GSCF as a starting point and subsequently applied heuristic augmentation and improvement procedures to obtain feasible integer solutions. Integer programming (IP) methods eliminate the need for augmentation and improvement procedures, but have generally been considered intractable for large GSCFs. In this paper we present a sequential mixed-integer programming (SMIP) heuristic for discontinuous (< 24 hours/day) tour-scheduling problems which takes advantage of the structure of the GSCF. The new heuristic substantially outperformed two prominent LP-based methods across 432 full-time workforce test problems, yielding optimal solutions for 429 of the problems. For a set of 36 test problems associated with a mixed-workforce scheduling environment that allowed both full-time and part-time employees with varying levels of cost and productivity, the SMIP heuristic yielded solution costs that were significantly better than previously published costs obtained with competitive methods.     

A multi-objective mixed integer linear programming model for thesis defence scheduling

In this paper, we address the thesis defence scheduling problem, a critical academic scheduling management process, which has been overshadowed in the literature by its counterparts, course timetabling and exam scheduling. Specifically, we address the single defence assignment type of thesis defence scheduling problems, where each committee is assigned to a single defence, scheduled for a specific day, hour and room. We formulate a multi-objective mixed-integer linear programming model, which aims to be applicable to a broader set of cases than other single defence assignment models present in the literature, which have a focus on the characteristics of their universities. For such a purpose, we introduce a different decision variable, propose constraint formulations that are not regulation and policy specific, and cover and offer new takes on the more common objectives seen in the literature. We also include new objective functions based on our experience with the problem at our university and by applying knowledge from other academic scheduling problems. We also propose a two-stage solution approach. The first stage is employed to find the number of schedulable defences, enabling the optimisation of instances with unschedulable defences. The second stage is an implementation of the augmented $ϵ$-constraint method, which allows for the search of a set of different and non-dominated solutions while skipping redundant iterations. The methodology is tested for case-studies from our university, significantly outperforming the solutions found by human schedulers. A novel instance generator for thesis scheduling problems is presented. Its main benefit is the generation of the availability of committee members and rooms in availability and unavailability blocks, resembling their real-world counterparts. A set of 96 randomly generated instances of varying sizes is solved and analysed regarding their relative computational performance, the number of schedulable defences and the distribution of the considered types of iterations. The proposed method can find the optimal number of schedulable defences and present non-dominated solutions within the set time limits for every tested instance.     

An integer linear programming approach for bilinear integer programming

We introduce a new Integer Linear Programming (ILP) approach for solving Integer Programming (IP) problems with bilinear objectives and linear constraints. The approach relies on a series of ILP approximations of the bilinear IP. We compare this approach with standard linearization techniques on random instances and a set of real-world product bundling problems.     

Mixed integer programming for scheduling flexible flow lines with limited intermediate buffers

This paper presents new mixed integer programming formulations for scheduling of a flexible flow line with blocking. The flexible flow line consists of several processing stages in series, separated by finite intermediate buffers, where each stage has one or more identical parallel machines. The line produces several different product types and each product must be processed by, at most, one machine in each stage. A product which has completed processing on a machine may remain there and block the machine until a downstream machine becomes available for processing. The objective is to determine a production schedule for all products so as to complete the products in a minimum time. The basic mixed integer programming formulations have been enhanced to model blocking scheduling with alternative processing routes where for each product a set of routes is available for processing. A reentrant flow line where a product visits a set of stages more than once is also considered. Numerical examples are presented to illustrate applications of the various models proposed.     

A mixed integer programming model for scheduling orders in a steel mill

The problem of scheduling orders at each facility of a large integrated steel mill is considered. Orders are received randomly, and delivery dates are established immediately. Each order is filled by converting raw materials into a finished saleable steel product by a fixed sequence of processes. The application of a deterministic mixed integer linear programming model to the order scheduling problem is given. One important criterion permitted by the model is to process the orders in a sequence which minimizes the total tardiness from promised delivery for all orders; alternative criteria are also possible. Most practical constraints which arise in steelmaking can be considered within the formulation. In particular, sequencing and resource availability constraints are handled easily. The order scheduling model given here contains many variables and constraints, resulting in computational difficulties. A decomposition algorithm is devised for solving the model. The algorithm is a special case of Benders partitioning. Computational experience is reported for a large-scale problem involving scheduling 102 orders through ten facilities over a six-week period. The exact solution to the large-scale problem is compared with schedules determined by several heuristic dispatching rules. The dispatching rules took into consideration such things as due date, processing time, and tardiness penalties. None of the dispatching rules found the optimal solution.     

An integer programming approach to short-term production scheduling in a tobacco plant

In this paper, a mathematical model is developed that facilitates daily production scheduling in a tobacco processing plant. The implied objectives are to meet specific horizon production targets (obtained from a master production schedule), to maintain safety stock requirements and to ensure that the demand for labour lies within given limits. The express objective is to minimise the number of machines used in the production process. Additionally, the model incorporates work-in-progress, aspects of the demand for product transportation within the plant and machine capacity (utilisation) reduction effects associated with production sequencing. These aspects are relevant when dealing with time intervals as small as a day but can be averaged out when dealing with monthly time intervals. The developments in this paper represents stage II of the modelling of the tobacco plant, where stage I (already completed) was centred on obtaining a monthly master production schedule for a year ahead and assisting in macro planning activities. This paper also sees the development of a simple user-friendly heuristic which facilitates production sequencing on a daily basis given the master production schedule obtained from Stage I.     

Robust integer programming

We provide a complexity classification of four variants of robust integer programming when the underlying Graver basis is given. We discuss applications to robust multicommodity flows and multiway statistical table problems, and describe an effective parametrization of robust integer programming.     

Improved integer programming bounds using intersections of corner polyhedra

Consider the relaxation of an integer programming (IP) problem in which the feasible region is replaced by the intersection of the linear programming (LP) feasible region and the corner polyhedron for a particular LP basis. Recently a primal-dual ascent algorithm has been given for solving this relaxation. Given an optimal solution of this relaxation, we state criteria for selecting a new LP basis for which the associated relaxation is stronger. These criteria may be successively applied to obtain either an optimal IP solution or a lower bound on the cost of such a solution. Conditions are given for equality of the convex hull of feasible IP solutions and the intersection of all corner polyhedra.