Sequence of decisions on discrete event systems modeled by Petri nets with structural alternative configurations

The management of certain systems, such as manufacturing facilities, supply chains, or communication networks implies assessing the consequences of decisions, aimed for the most efficient operation. This kind of systems usually shows complex behaviors where subsystems present parallel evolutions and synchronizations. Furthermore, the existence of global objectives for the operation of the systems and the changes that experience the systems or their environment during their evolution imply a more or less strong dependence between decisions made at different time points of the life cycle. This paper addresses a complex problem that is scarcely present in the scientific literature: the sequences of decisions aimed for achieving several objectives simultaneously and with strong influence from one decision to the rest of them. In this case, the formal statement of the decision problem should take into account the whole decision sequence, making impractical the solving paradigm of “divide and conquer”. Only an integrated methodology may afford a realistic solution of such a type of decision problem. In this paper, an approach based on the formalism of the Petri nets is described, several considerations related to this problem are presented, a solving methodology based on the previous work of the authors, as well as a case-study to illustrate the main concepts.     

Flow shop scheduling with heterogeneous workers

We propose an extension to the flow shop scheduling problem named Heterogeneous Flow Shop Scheduling Problem (Het-FSSP), where two simultaneous issues have to be resolved: finding the best worker assignment to the workstations, and solving the corresponding scheduling problem. This problem is motivated by Sheltered Work centers for Disabled, whose main objective is the labor integration of persons with disabilities, an important aim not only for these centers but for any company desiring to overcome the traditional standardized vision of the workforce. In such a scenario the goal is to maintain high productivity levels by minimizing the maximum completion time, while respecting the diverse capabilities and paces of the heterogeneous workers, which increases the complexity of finding an optimal schedule. We present a mathematical model that extends a flow shop model to admit a heterogeneous worker assignment, and propose a heuristic based on scatter search and path relinking to solve the problem. Computational results show that this approach finds good solutions within a short time, providing the production managers with practical approaches for this combined assignment and scheduling problem.     

A global MILP model for FMS scheduling

Flexible manufacturing systems (FMS) require intelligent scheduling strategies to achieve their principal benefit — combining high flexibility with high productivity. A mixed-integer linear programming model (MILP) is presented here for FMS scheduling. The model takes a global view of the problem and specifically takes into account constraints on storage and transportation. Both of these constrained resources are critical for practical FMS scheduling problems and are difficult to model. The MILP model is explained and justified and its complexity is discussed. Two heuristic procedures are developed, based on an analysis of the global MILP model. Computational results are presented comparing the performance of the different solution strategies. The development of iterative global heuristics based on mathematical programming formulations is advocated for a wide class of FMS scheduling problems.     

Discrete and continuous time representations and mathematical models for large production scheduling problems: A case study from the pharmaceutical industry

The underlying time framework used is one of the major differences in the basic structure of mathematical programming formulations used for production scheduling problems. The models are either based on continuous or discrete time representations. In the literature there is no general agreement on which is better or more suitable for different types of production or business environments. In this paper we study a large real-world scheduling problem from a pharmaceutical company. The problem is at least NP-hard and cannot be solved with standard solution methods. We therefore decompose the problem into two parts and compare discrete and continuous time representations for solving the individual parts. Our results show pros and cons of each model. The continuous formulation can be used to solve larger test cases and it is also more accurate for the problem under consideration.     

Parallel machine scheduling with additional resources: Notation,classification, models and solution methods

Majority of parallel machine scheduling studies consider machine as the only resource. However, in most real-life manufacturing environments, jobs may require additional resources, such as automated guided vehicles, machine operators, tools, pallets, dies, and industrial robots, for their handling and processing. This paper presents a review and discussion of studies on the parallel machine scheduling problems with additional resources. Papers are surveyed in five main categories: machine environment, additional resource, objective functions, complexity results and solution methods, and other important issues. The strengths and weaknesses of the literature together with open areas for future studies are also emphasized. Finally, extensions of integer programming models for two main classes of related problems are given and conclusions are drawn based on computational studies.     

Non-block scheduling with priority for radiotherapy treatments

In this paper, a quite challenging operational problem within health care delivery has been considered: the optimal management of patients waiting for radiotherapy treatments. Long waiting times for radiotherapy treatments of several cancers are largely documented all over the world. This problem is mainly due to an imbalance between supply and demand of radiotherapy services, which negatively affects the effectiveness and the efficiency of the health care delivered. Within this context, the paper presents an innovative solution approach for effectively scheduling a set of patients waiting to start the radiotherapy plan. The proposed approach is based on a well tailored integer linear optimization program, modelling a non-block scheduling strategy, with the aim to minimize the mean waiting time or maximize the number of new scheduled patients. The model has been tested and evaluated by carrying out some numerical experiments on suitable use-case scenarios, and the obtained results demonstrate the effectiveness and reliability of the proposed approach.     

Time-indexed formulations for scheduling chains on a single machine: An application to airborne radars

Airborne radars are widely used to perform a large variety of tasks in an aircraft (searching, tracking, identifying targets, etc.) Such tasks play a crucial role for the aircraft and they are repeated in a “more or less” cyclic fashion. This defines a scheduling problem that impacts a lot on the quality of the radar output and on the overall safety of the aircraft.     

An integer linear programming-based heuristic for scheduling heterogeneous,part-time service employees

Scheduling of heterogeneous, part-time, service employees with limited availability is especially challenging because employees have different availability and skills, and work different total work hours in a planning period, e.g., a week. The constraints typically are to meet employee requirements during each hour in a planning period with shifts which have a minimum & maximum length, and do not exceed 5 work days per week for each employee. The objectives typically are to minimize over staffing and to meet the target total work hours for each employee during the planning period. We decompose this problem into (a) determining good shifts and then (b) assigning the good shifts to employees, and use a set of small integer linear programs to solve each part. We apply this method to the data given in a reference paper and compare our results. Also, several random problems are generated and solved to verify the robustness of our solution method.     

A branch-and-price approach for integrating nurse and surgery scheduling

A common problem at hospitals is the extreme variation in daily (even hourly) workload pressure for nurses. The operating room is considered to be the main engine and hence the main generator of variance in the hospital. The purpose of this paper is threefold. First of all, we present a concrete model that integrates both the nurse and the operating room scheduling process. Second, we show how the column generation technique approach, one of the most employed exact methods for solving nurse scheduling problems, can easily cope with this model extension. Third, by means of a large number of computational experiments we provide an idea of the cost saving opportunities and required solution times.     

Stability Analysis of Two Linear Distributed Parameter Bioprocess Models

This paper proposes to extend the dynamical analysis results on chemical tubular reactors presented in [5] to two linear distributed parameter models. These are in particular the linearized tangent models of two typical bioprocess models: a basic tubular bioreactor model, and a denitrifying biofilter model. The tools used for the analysis are those of the infinite dimensional system theory (e.g., [2]). In the paper we show the existence of solutions for the studied models, and emphasize stability conditions.     

Finding improving directions in Lagrangian relaxation by fictitious play: A NASA scheduling application

An improving direction for Lagrangian dual prices can be found by solving (or solving approximately) a two person zero-sum game. While this method is impractical in many situations, its practical use is illustrated in a scheduling application. In this implementation, the game is solved approximately by fictitious play.     

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.     

The one-dimensional cutting stock problem with due dates

The one-dimensional cutting stock problem is the problem of cutting stock material into shorter lengths, in order to meet demand for these shorter lengths while minimizing waste. In industrial cutting operations, it may also be necessary to fill the orders for these shorter lengths before a given due date. We propose new optimization models and solution procedures which solve the cutting stock problem when orders have due dates. We evaluate our approach using data from a large manufacturer of reinforcement steel and show that we are able to solve industrial-size problems, while also addressing common cutting considerations such as aggregation of orders, multiple stock lengths and cutting different types of material on the same machine. In addition, we evaluate operational performance in terms of resulting waste and tardiness of orders using our model in a rolling horizon framework.     

Economic lot scheduling with uncontrolled co-production

The aim of this paper is to analyze the effects of uncontrolled co-production on the production planning and lot scheduling of multiple products. Co-production occurs when a proportion of a certain production comes out as another product. This is typical in the process industry where quality and process specifications can lead to diversified products. We assume that there is no demand substitution and each product has its own market. Furthermore, we assume that co-production cannot be controlled due to technical and/or cost considerations. We introduce two models that extend the common cycle economic lot scheduling (ELSP) setting to include uncontrolled co-production. In the first model we do not allow for shortages and derive the optimal cycle time expression. In the second model, we allow for planned backorders and characterize the optimal solution in closed form. We provide a numerical study to gain insight about co-production. It seems that the cycle time increases with co-production rate and utilization of the system. The effect of co-production on long-term average cost does not exhibit a certain characteristic.     

Integer programming approach to reactive scheduling in make-to-order manufacturing

New algorithms based on mixed integer programming formulations are proposed for reactive scheduling in a dynamic, make-to-order manufacturing environment. The problem objective is to update a long-term production schedule subject to service level and inventory constraints, whenever the customer orders are modified or new orders arrive. Different rescheduling policies are proposed, from a total reschedule of all remaining and unmodified customer orders to a non-reschedule of all such orders. In addition, a medium restrictive policy is considered for rescheduling only a subset of remaining customer orders awaiting material supplies. Numerical examples modeled after a real-world scheduling/rescheduling of customer orders in the electronics industry are presented and some results of computational experiments are reported.     

Column generation approaches to ship scheduling with flexible cargo sizes

We present a Dantzig–Wolfe procedure for the ship scheduling problem with flexible cargo sizes. This problem is similar to the well-known pickup and delivery problem with time windows, but the cargo sizes are defined by intervals instead of by fixed values. The flexible cargo sizes have consequences for the times used in the ports because both the loading and unloading times depend on the cargo sizes. We found it computationally hard to find exact solutions to the subproblems, so our method does not guarantee to find the optimum over all solutions. To be able to say something about how good our solution is, we generate a bound on the difference between the true optimal objective and the objective in our solution. We have compared our method with an a priori column generation approach, and our computational experiments on real world cases show that our Dantzig–Wolfe approach is faster than the a priori generation of columns, and we are able to deal with larger or more loosely constrained instances. By using the techniques introduced in this paper, a more extensive set of real world cases can be solved either to optimality or within a small deviation from optimality.     

Integer programming models for hierarchical workforce scheduling problems including excess off-days and idle labour times

The decision problem considered in this paper is a hierarchical workforce scheduling problem in which a higher qualified worker can substitute for a lower qualified one, but not vice versa, labour requirements may vary, and each worker must receive n off-days a week. Within this context, five mathematical models are discussed. The first two of these five models are previously published. Both of them are for the case where the work is indivisible. The remaining three models are developed by the authors of this paper. One of these new models is for the case where the work is indivisible and the other two are for the case where the work is divisible. The three new models are proposed with the purpose of removing the shortcomings of the previously published two models. All of the five models are applied on the same illustrative example. Additionally, a total of 108 test problems are solved within the context of two computational experiments.     

Distributionally robust scheduling on parallel machines under moment uncertainty

This paper investigates a distributionally robust scheduling problem on identical parallel machines, where job processing times are stochastic without any exact distributional form. Based on a distributional set specified by the support and estimated moments information, we present a min-max distributionally robust model, which minimizes the worst-case expected total flow time out of all probability distributions in this set. Our model doesn’t require exact probability distributions which are the basis for many stochastic programming models, and utilizes more information compared to the interval-based robust optimization models. Although this problem originates from the manufacturing environment, it can be applied to many other fields when the machines and jobs are endowed with different meanings. By optimizing the inner maximization subproblem, the min-max formulation is reduced to an integer second-order cone program. We propose an exact algorithm to solve this problem via exploring all the solutions that satisfy the necessary optimality conditions. Computational experiments demonstrate the high efficiency of this algorithm since problem instances with 100 jobs are optimized in a few seconds. In addition, simulation results convincingly show that the proposed distributionally robust model can hedge against the bias of estimated moments and enhance the robustness of production systems.     

A lexicographic approach to bi-objective scheduling of single-period orders in make-to-order manufacturing

This paper presents a lexicographic approach and integer programming formulations for a dual-objective, long-term production scheduling in make-to-order manufacturing environment. The problem objective is to assign single-period customer orders for various product types to planning periods to complete all the orders with minimum number of tardy orders as a primary criterion and to level the aggregate production or the total capacity utilization over a planning horizon as a secondary criterion. Each order must be completed during one planning period. The basic integer programming formulation has been strengthened by the addition of some cutting constraints derived by relating the demand on required capacity to available capacity for each subset of orders with the same due date. The approach has been applied to optimize production schedules in a flexible flowshop made up of several processing stages in series, with identical, parallel machines, and an output buffer of limited capacity for holding completed products before delivery to the customers. Numerical examples modeled after a real-world make-to-order flexible assembly line in the electronics industry are provided and some computational results are reported.