A solution approach for optimizing long- and short-term production scheduling at LKAB’s Kiruna mine

We present a mixed-integer program to schedule long- and short-term production at LKAB’s Kiruna mine, an underground sublevel caving mine located in northern Sweden. The model minimizes deviations from monthly preplanned production quantities while adhering to operational constraints. Because of the mathematical structure of the model and its moderately large size, instances spanning a time horizon of more than a year or two tend to be intractable. We develop an optimization-based decomposition heuristic that, on average, obtains better solutions faster than solving the model directly. We show that for realistic data sets, we can generate solutions with deviations that comprise about 3-6% of total demand in about a third of an hour.     

MineLib: a library of open pit mining problems

Similar to the mixed-integer programming library (MIPLIB), we present a library of publicly available test problem instances for three classical types of open pit mining problems: the ultimate pit limit problem and two variants of open pit production scheduling problems. The ultimate pit limit problem determines a set of notional three-dimensional blocks containing ore and/or waste material to extract to maximize value subject to geospatial precedence constraints. Open pit production scheduling problems seek to determine when, if ever, a block is extracted from an open pit mine. A typical objective is to maximize the net present value of the extracted ore; constraints include precedence and upper bounds on operational resource usage. Extensions of this problem can include (i) lower bounds on operational resource usage, (ii) the determination of whether a block is sent to a waste dump, i.e., discarded, or to a processing plant, i.e., to a facility that derives salable mineral from the block, (iii) average grade constraints at the processing plant, and (iv) inventories of extracted but unprocessed material. Although open pit mining problems have appeared in academic literature dating back to the 1960s, no standard representations exist, and there are no commonly available corresponding data sets. We describe some representative open pit mining problems, briefly mention related literature, and provide a library consisting of mathematical models and sets of instances, available on the Internet. We conclude with directions for use of this newly established mining library. The library serves not only as a suggestion of standard expressions of and available data for open pit mining problems, but also as encouragement for the development of increasingly sophisticated algorithms.     

Time complexity of single- and identical parallel-machine scheduling with GERT network precedence constraints

In this paper we deal with the time complexity of single- and identical parallel-machine scheduling problems in which the durations and precedence constraints of the activities are stochastic. The stochastic precedence constraints are given by GERT networks. First, we sketch the basic concepts of GERT networks and machine scheduling with GERT network precedence constraints. Second, we discuss the time complexity of some open single-machine scheduling problems with GERT network precedence constraints. Third, we investigate the time complexity of identical parallel-machine scheduling problems with GERT network precedence constraints. Finally, we present an efficient reduction algorithm for the problem of computing the expected makespan for the latter type of scheduling problem.     

The new Fundamental Tree Algorithm for production scheduling of open pit mines

The problem of annual production scheduling in surface mining consists of determining an optimal sequence of extracting the mineralized material from the ground. The main objective of the optimization process is usually to maximize the total Net Present Value of the operation. Production scheduling is typically a mixed integer programming (MIP) type problem. However, the large number of integer variables required in formulating the problem makes it impossible to solve. To overcome this obstacle, a new algorithm termed “Fundamental Tree Algorithm” is developed based on linear programming to aggregate blocks of material and decrease the number of integer variables and the number of constraints required within the MIP formulation. This paper proposes the new Fundamental Tree Algorithm in optimizing production scheduling in surface mining. A case study on a large copper deposit summarized in the paper shows substantial economic benefit of the proposed algorithm compared to existing methods.     

Maximization Problems in Single Machine Scheduling

Problems of scheduling n jobs on a single machine to maximize regular objective functions are studied. Precedence constraints may be given on the set of jobs and the jobs may have different release times. Schedules of interest are only those for which the jobs cannot be shifted to start earlier without changing job sequence or violating release times or precedence constraints. Solutions to the maximization problems provide an information about how poorly such schedules can perform. The most general problem of maximizing maximum cost is shown to be reducible to n similar problems of scheduling n?1 jobs available at the same time. It is solved in O(mn+n ²) time, where m is the number of arcs in the precedence graph. When all release times are equal to zero, the problem of maximizing the total weighted completion time or the weighted number of late jobs is equivalent to its minimization counterpart with precedence constraints reversed with respect to the original ones. If there are no precedence constraints, the problem of maximizing arbitrary regular function reduces to n similar problems of scheduling n?1 jobs available at the same time.     

Scheduling UET task systems with concurrency on two parallel identical processors

Problems with unit execution time tasks and two identical parallel processors have received a great deal of attention in scheduling theory. In contrast to the conventional models, where each task requires only one processor, we consider a situation when a task may require both processors simultaneously. For problems without precedence constraints we present several polynomial time algorithms which complement recent results of Lee and Cai. We also show that the introduction of precedence constraints leads to NP-hardness results for maximum lateness and mean flow time objective functions. For the maximum lateness problem, a family of algorithms, based upon the idea of modified due dates, is considered. The worst case behaviour of these algorithms is analysed, and it is shown that the same upper bound is tight for each algorithm of this family.     

Simple assembly line balancing—Heuristic approaches

In this paper heuristics for Type 1 and Type 2 of the Simple Assembly Line Balancing Problem (SALBP) are described. Type 1 of SALBP (SALBP-1) consists of assigning tasks to work stations such that the number of stations is minimized for a given production rate whereas Type 2 (SALBP-2) is to maximize the production rate, or equivalently, to minimize the sum of idle times for a given number of stations. In both problem types, precedence constraints between the tasks have to be considered.We describe bidirectional and dynamic extensions to heuristic priority rules widely used for SALBP-1. For the solution of SALBP-2 we present search methods which involve the repetitive application of procedures for SALBP-1. Furthermore, improvement procedures for SALBP-2 are developed and combined with tabu search, a recent strategy to overcome local optimality. Several optional elements of tabu search are discussed. Finally, the application of a nontraditional tabu search approach to solve SALBP-1 is investigated. Computational experiments validate the effectiveness of our new approaches.     

Scheduling project networks with resource constraints and time windows

Project networks with time windows are generalizations of the well-known CPM and MPM networks that allow for the introduction of arbitrary minimal and maximal time lags between the starting and completion times of any pair of activities.We consider the problem to schedule such networks subject to arbitrary (even time dependent) resource constraints in order to minimize an arbitrary regular performance measure (i.e. a non-decreasing function of the vector of completion times). This problem arises in many standard industrial construction or production processes and is therefore particularly suited as a background model in general purpose decision support systems.The treatment is done by a structural approach that involves a generalization of both the disjunctive graph method in job shop scheduling [1] and the order theoretic methods for precedence constrained scheduling [18,23,24]. Besides theoretical insights into the problem structure, this approach also leads to rather powerful branch-and-bound algorithms. Computational experience with this algorithm is reported.     

A survey of variants and extensions of the resource-constrained project scheduling problem

The resource-constrained project scheduling problem (RCPSP) consists of activities that must be scheduled subject to precedence and resource constraints such that the makespan is minimized. It has become a well-known standard problem in the context of project scheduling which has attracted numerous researchers who developed both exact and heuristic scheduling procedures. However, it is a rather basic model with assumptions that are too restrictive for many practical applications. Consequently, various extensions of the basic RCPSP have been developed. This paper gives an overview over these extensions. The extensions are classified according to the structure of the RCPSP. We summarize generalizations of the activity concept, of the precedence relations and of the resource constraints. Alternative objectives and approaches for scheduling multiple projects are discussed as well. In addition to popular variants and extensions such as multiple modes, minimal and maximal time lags, and net present value-based objectives, the paper also provides a survey of many less known concepts.     

Dual decomposition of a single-machine scheduling problem

We design a fast ascent direction algorithm for the Lagrangian dual problem of the single-machine scheduling problem of minimizing total weighted completion time subject to precedence constraints. We show that designing such an algorithm is relatively simple if a scheduling problem is formulated in terms of the job completion times rather than as an 0–1 linear program. Also, we show that upon termination of such an ascent direction algorithm we get a dual decomposition of the original problem, which can be exploited to develop approximative and enumerative approaches for it. Computational results exhibit that in our application the ascent direction leads to good Lagrangian lower and upper bounds.     

Using aggregation to optimize long-term production planning at an underground mine

Motivated by an underground mining operation at Kiruna, Sweden, we formulate a mixed integer program to schedule iron ore production over multiple time periods. Our optimization model determines an operationally feasible ore extraction sequence that minimizes deviations from planned production quantities. The number of binary decision variables in our model is large enough that directly solving the full, detailed problem for a three year time horizon requires hours, or even days. We therefore design a heuristic based on solving a smaller, more tractable, model in which we aggregate time periods, and then solving the original model using information gained from the aggregated model. We compute a bound on the worst case performance of this heuristic and demonstrate empirically that this procedure produces good quality solutions while substantially reducing computation time for problem instances from the Kiruna mine.     

Multi-mode resource-constrained project scheduling using RCPSP and SAT solvers

This paper reports on a new solution approach for the well-known multi-mode resource-constrained project scheduling problem (MRCPSP). This problem type aims at the selection of a single activity mode from a set of available modes in order to construct a precedence and a (renewable and non-renewable) resource feasible project schedule with a minimal makespan. The problem type is known to be NP-hard and has been solved using various exact as well as (meta-)heuristic procedures.The new algorithm splits the problem type into a mode assignment and a single mode project scheduling step. The mode assignment step is solved by a satisfiability (SAT) problem solver and returns a feasible mode selection to the project scheduling step. The project scheduling step is solved using an efficient meta-heuristic procedure from literature to solve the resource-constrained project scheduling problem (RCPSP). However, unlike many traditional meta-heuristic methods in literature to solve the MRCPSP, the new approach executes these two steps in one run, relying on a single priority list. Straightforward adaptations to the pure SAT solver by using pseudo boolean non-renewable resource constraints has led to a high quality solution approach in a reasonable computational time. Computational results show that the procedure can report similar or sometimes even better solutions than found by other procedures in literature, although it often requires a higher CPU time.     

Proactive policies for the stochastic resource-constrained project scheduling problem

The resource-constrained project scheduling problem involves the determination of a schedule of the project activities, satisfying the precedence and resource constraints while minimizing the project duration. In practice, activity durations may be subject to variability. We propose a stochastic methodology for the determination of a project execution policy and a vector of predictive activity starting times with the objective of minimizing a cost function that consists of the weighted expected activity starting time deviations and the penalties or bonuses associated with late or early project completion. In a computational experiment, we show that our procedure greatly outperforms existing algorithms described in the literature.     

Lower Bounds for Scheduling a Single Robot in a Job-Shop Environment

We consider a single-machine scheduling problem which arises as a subproblem in a job-shop environment where the jobs have to be transported between the machines by a single transport robot. The robot scheduling problem may be regarded as a generalization of the traveling salesman problem with time windows, where additionally generalized precedence constraints (minimal time-lags) have to be respected. The objective is to determine a sequence of all nodes and corresponding starting times in the given time windows in such a way that all generalized precedence relations are respected and the sum of all traveling and waiting times is minimized.We calculate lower bounds for this problem using constraint propagation techniques and a linear programming formulation which is solved by a column generation procedure. Computational results are presented for test data arising from job-shop instances with a single transport robot and some modified traveling salesman instances.     

A mathematical programming model and solution for scheduling production orders in Shanghai Baoshan Iron and Steel Complex

In this paper, we investigate the production order scheduling problem derived from the production of steel sheets in Shanghai Baoshan Iron and Steel Complex (Baosteel). A deterministic mixed integer programming (MIP) model for scheduling production orders on some critical and bottleneck operations in Baosteel is presented in which practical technological constraints have been considered. The objective is to determine the starting and ending times of production orders on corresponding operations under capacity constraints for minimizing the sum of weighted completion times of all orders. Due to large numbers of variables and constraints in the model, a decomposition solution methodology based on a synergistic combination of Lagrangian relaxation, linear programming and heuristics is developed. Unlike the commonly used method of relaxing capacity constraints, this methodology alternatively relaxes constraints coupling integer variables with continuous variables which are introduced to the objective function by Lagrangian multipliers. The Lagrangian relaxed problem can be decomposed into two sub-problems by separating continuous variables from integer ones. The sub-problem that relates to continuous variables is a linear programming problem which can be solved using standard software package OSL, while the other sub-problem is an integer programming problem which can be solved optimally by further decomposition. The subgradient optimization method is used to update Lagrangian multipliers. A production order scheduling simulation system for Baosteel is developed by embedding the above Lagrangian heuristics. Computational results for problems with up to 100 orders show that the proposed Lagrangian relaxation method is stable and can find good solutions within a reasonable time.     

链式先后关系下的单机分批排序问题

在本文,我们证明链式先后关系下的单机分批排序问题是强NP困难的,解决了Albers和Brucker（1993）提出的待解决问题．关于此问题,Albers和Brucker（1993）也曾试图给出NP困难性证明,我们阐明了其证明中存在的缺陷．     

A priority-rule method for project scheduling with work-content constraints

The activities of a project are in general characterized by a work content in terms of resource–time units, e.g. person-days. Even though most project scheduling models assume a time-invariant resource usage, normally it is possible to vary the resource usage during the execution of an activity. Typically, a lower and an upper bound on this resource usage and a minimum time lag between consecutive changes of this resource usage are prescribed. The project scheduling problem studied in this paper consists in determining a feasible resource-usage profile for each activity such that the project duration is minimized subject to precedence and resource-capacity constraints. While the known solution methods interpret the prescribed work content as a lower bound, we assume that each activity’s work content must be processed exactly.     

带重入的单台机排序问题

本文考虑带重入的单台机排序问题,重入是指每个工件在机器上加工不止一次.通过把重入模型转化为带平行链约束的排序问题,我们成功地获得了单机重入问题的两个目标函数的多项式时间最优算法,一个是总带权完工时间∑ωjCj,另一个是最大费用函数hmax.