Search

This article presents a realized application of a model and algorithm to optimize the formation and use of a machine and tractor fleet of an agricultural enterprise in crop farming. The concepts and indicators characterizing the processes of agricultural operations of the machine fleet in the agrarian business are considered. A classification of approaches for optimizing the implementation of a complex of mechanized agro-technical operations is given. We systemize different views on the problems under study and possible solutions. The advantages of the proposed model and algorithm, as well as the problematic aspects of their information and instrumental support are discussed. The problem of choosing the optimality criterion when setting the formal problem of optimizing agricultural operations by a fleet of machines in the agricultural field is considered. A modification of the economic and mathematical model for optimizing the structure and production schedules of the machine and tractor fleet is developed. The model is applied in a numerical experiment using real data of a specific agricultural enterprise, and the economic interpretation of the results is discussed. We apply an approach for determining the economic effect of the use of the developed model and algorithm. The possibilities for practical application of the obtained results of the study are substantiated.

The problem of scheduling optimally a given set of jobs on a single machine is studied. The lower and upper bounds on the admissible duration of each job are known. The optimality criterion of the schedule is the minimum total completion time of a given set of jobs. Some properties of the optimality region for a job permutation are investigated. Polynomial algorithms for constructing the optimality region for a job permutation and also for calculating the volume of this region are developed. The existence conditions of an empty optimality region for a job permutation are determined. A criterion for the existence of a job permutation with the maximum possible volume of the optimality region is established.

A set of jobs has to be processed on parallel machines. For each job, there are given a release time and a due date and the job must be processed no later than its due date. If the job will be comp ...

A set of jobs has to be processed on a single machine without preemptions of a job. The exact value of the job processing time (duration) is unknown until the completion of the job. Lower and upper bounds on the job duration are known before scheduling. The problem is to minimize total completion time of the given jobs. We apply a stability approach to this scheduling problem and introduce an optimality region for a job permutation as an optimality measure of the schedule. We investigate properties of the optimality region and derive O(n) algorithms for calculating the relative perimeter of the optimality region (the sum of the relative optimality sets of the n jobs) for a fixed job permutation. We present computational results for a comparison of the relative perimeters of the optimality regions for the mid-point permutations, the lower-bound permutations, the upper-bound permutations and the permutations having the largest optimality box.

This study addresses a two-machine job-shop scheduling problem with fixed lower and upper bounds on the job processing times. An exact value of the job duration remains unknown until completing the job. The objective is to minimize a schedule length (makespan). It is investigated how to best execute a schedule, if the job processing time may be equal to any real number from the given (closed) interval. Scheduling decisions consist of the off-line phase and the on-line phase of scheduling. Using the fixed lower and upper bounds on the job processing times available at the off-line phase, a scheduler may determine a minimal dominant set of schedules (minimal DS), which is based on the proven sufficient conditions for a schedule dominance. The DS optimally covers all possible realizations of the uncertain (interval) processing times, i.e., for each feasible scenario, there exists at least one optimal schedule in the minimal DS. The DS enables a scheduler to make the on-line scheduling decision, if a local information on completing some jobs becomes known. The stability approach enables a scheduler to choose optimal schedules for most feasible scenarios. The on-line scheduling algorithms have been developed with the asymptotic complexity O(n2) for n given jobs. The computational experiment shows the effectiveness of these algorithms.

We address a generalization of the classical job-shop problem which is called a hybrid job-shop problem. The criteria under consideration are the minimization of the makespan and mean flow time. In the hybrid job-shop, machines of type [Formula: see text] are available for processing the specific subset [Formula: see text] of the given operations. Each set [Formula: see text] may be partitioned into subsets for their processing on the machines of type [Formula: see text]. Solving the hybrid job-shop problem implies the solution of two subproblems: an assignment of all operations from the set [Formula: see text] to the machines of type [Formula: see text] and finding optimal sequences of the operations for their processing on each machine. In this paper, a genetic algorithm is developed to solve these two subproblems simultaneously. For solving the subproblems, a special chromosome is used in the genetic algorithm based on a mixed graph model. We compare our genetic algorithms with a branch-and-bound algorithm and three other recent heuristic algorithms from the literature. Computational results for benchmark instances with 10 jobs and up to 50 machines show that the proposed genetic algorithm is rather efficient for both criteria. Compared with the other heuristics, the new algorithm gives most often an optimal solution and the average percentage deviation from the optimal function value is about 4%.

We study two-machine shop-scheduling problems provided that lower and upper bounds on durations of n jobs are given before scheduling. An exact value of the job duration remains unknown until completing the job. The objective is to minimize the makespan (schedule length). We address the issue of how to best execute a schedule if the job duration may take any real value from the given segment. Scheduling decisions may consist of two phases: an off-line phase and an on-line phase. Using information on the lower and upper bounds for each job duration available at the off-line phase, a scheduler can determine a minimal dominant set of schedules (DS) based on sufficient conditions for schedule domination. The DS optimally covers all possible realizations (scenarios) of the uncertain job durations in the sense that, for each possible scenario, there exists at least one schedule in the DS which is optimal. The DS enables a scheduler to quickly make an on-line scheduling decision whenever additional information on completing jobs is available. A scheduler can choose a schedule which is optimal for the most possible scenarios. We developed algorithms for testing a set of conditions for a schedule dominance. These algorithms are polynomial in the number of jobs. Their time complexity does not exceed O ( n 2 ) . Computational experiments have shown the effectiveness of the developed algorithms. If there were no more than 600 jobs, then all 1000 instances in each tested series were solved in one second at most. An instance with 10,000 jobs was solved in 0.4 s on average. The most instances from nine tested classes were optimally solved. If the maximum relative error of the job duration was not greater than 20 % , then more than 80 % of the tested instances were optimally solved. If the maximum relative error was equal to 50 % , then 45 % of the tested instances from the nine classes were optimally solved.

An uncertain single-machine scheduling problem is considered, where the processing time of a job can take any real value from a given segment. The criterion is to minimise the total weighted completion time of the n jobs, a weight being associated with each given job. We use the optimality box as a stability measure of the optimal schedule and derive an O(n)-algorithm for calculating the optimality box for a fixed permutation of the given jobs. We investigate properties of the optimality box using blocks of the jobs. If each job belongs to a single block, then the largest optimality box may be constructed in time. For the general case, we apply dynamic programming for constructing a job permutation with the largest optimality box. The computational results for finding a permutation with the largest optimality box show that such a permutation is close to an optimal one, which can be determined after completing the jobs when their processing times became known.

Simple assembly line balancing problems are studied.Stability of line balances with respect to variations of processing times is investigated.Algorithms for constructing feasible and stable optimal line balances are proposed.Computational results for benchmark instances are discussed.Complexity analysis has also been developed. For a simple assembly line, it is necessary to minimize a number of the workstations for processing a partially ordered set of the tasks V = { 1 , 2 , ? , n } within a fixed cycle time (such a problem is denoted as SALBP-1). A dual assembly line balancing problem denoted as SALBP-2 is to minimize a cycle time provided that a number of the workstations is fixed. An initial vector t = ( t 1 , t 2 , ? , t n ) of the processing times of the tasks V is given for both problems SALBP-1 and SALBP-2. For a subset V ~ ? V of the manual tasks j ? V ~ , the processing times t j may vary since operators may have different skills, levels of fatigue, experience, and motivation. For any automated task i ? V ? V ~ , the processing time t i cannot vary. We investigate a stability of an optimal line balance for the assembly line with respect to variations of the processing times of the manual tasks (a line balance is stable, if it is optimal for any sufficiently small variation of the processing times). We developed the enumerative algorithms for constructing feasible and stable optimal line balances for the problem SALBP-1 and those for the problem SALBP-2. Computational results for the stability of the assembly line balances showed that there are a lot of unstable optimal line balances for the tested benchmark assembly lines. The simulation for the benchmark assembly line showed that the stable optimal line balance considerably outperforms the unstable ones. The complexity analysis of the assembly line balancing problems with different partial orders given on the task set V has been developed.

This edited book presents new results in the area of algorithm development for different types of scheduling problems. In eleven chapters, algorithms for single machine problems, flow-shop and job-shop scheduling problems (including their hybrid (flexible) variants), the resource-constrained project scheduling problem, scheduling problems in complex manufacturing systems and supply chains, and workflow scheduling problems are given. The chapters address such subjects as insertion heuristics for energy-efficient scheduling, the re-scheduling of train traffic in real time, control algorithms for short-term scheduling in manufacturing systems, bi-objective optimization of tortilla production, scheduling problems with uncertain (interval) processing times, workflow scheduling for digital signal processor (DSP) clusters, and many more.

This special issue of Algorithms is devoted to the development of scheduling algorithms based on innovative approaches for solving hard scheduling problems either exactly or approximately. Submissions were welcome both for traditional scheduling problems as well as for new practical applications. The main topics include sequencing and scheduling with additional constraints (setup times or costs, precedence constraints, resource constraints, and batch production environment) and production planning and scheduling problems arising in real-world applications.

We consider a single machine scheduling problem with uncertain durations of the given jobs. The objective function is minimizing the sum of the job completion times. We apply the stability approach to the considered uncertain scheduling problem using a relative perimeter of the optimality box as a stability measure of the optimal job permutation. We investigated properties of the optimality box and developed algorithms for constructing job permutations that have the largest relative perimeters of the optimality box. Computational results for constructing such permutations showed that they provided the average error less than 0 . 74 % for the solved uncertain problems.

Heuristic algorithms are developed to solve the parallel-machine job-shop problems , where the criterion is the minimisation of the makespan, , or the sum of completion times, . The developed algorithms include sequencing and assigning stages. At the sequencing stage, the job-shop problem is solved, where job is available for processing from time . The problem is modelled by a mixed graph , where the vertices are the operations to be processed. The precedence constraints on the set are determined by the arc set . The resource constraints are determined by the edge set . In order to resolve a conflict arising between two operations processed on the same machine, the algorithm should substitute a conflict edge from the set by an arc incident to the same vertices from the set . The resulting digraph determines a heuristic solution to the problem , where all machines are different. The digraph determines a semi-active schedule for the problem . A mixed graph model is used for solving the problem , which allow...

We study a single-machine scheduling problem to minimize the total completion time of the given set of jobs, which have to be processed without job preemptions. The lower and upper bounds on the job duration is the only information that is available before scheduling. Exact values of the job durations remain unknown until the completion of the jobs. We use the optimality region for the job permutation as an optimality measure of the optimal schedule. We investigate properties of the optimality region and derive O ( n ) -algorithm for calculating a quasi-perimeter of the optimality set (i.e., the sum of lengths of the optimality segments for n given jobs). We develop a fast algorithm for finding a job permutation having the largest quasi-perimeter of the optimality set. The computational results in constructing such permutations show that they are close to the optimal ones, which can be constructed for the factual durations of all given jobs.

We consider a multistage processing system, which includes both identical (parallel) machines that can process the same set of operations and different machines that can process only different operation sets. A release time r i is given for each job J i to be processed. For such a processing system, we minimize the makespan, i.e., problem $IJ|r_i|C_{\max }$ is considered. The problem $IJ|r_i|C_{\max }$ is an extension of the classical job-shop problem $J|r_i|C_{\max }$ for the case when parallel (or identical) machines are also given. Both problems $J|r_i|C_{\max }$ and $IJ|r_i|C_{\max }$ are strongly NP-hard. A mixed graph model used for solving the problem $J|r_i|C_{\max }$ is generalized for the problem $IJ|r_i|C_{\max }$ . Using the mixed graph model, we developed a fast heuristic algorithm for solving the problem $IJ|r_i|C_{\max }$ . Computational experiments were conducted to evaluate the performance of the algorithm on the 22 benchmark instances and on the 40 new randomly generated instances of the problem $IJ||C_{\max }$ . For the small and moderate instances, the exact values of the objective function were compared with those calculated by the proposed heuristic algorithm. The average relative error was not greater than $2.4~\%$ for all instances with available optimal schedules. Computational results showed that the developed algorithm runs faster than some other heuristics being tested, and the schedules constructed by the developed algorithm have smaller makespans.

A learning stage of scheduling tends to produce knowledge about a benchmark of priority dispatching rules which allows a scheduler to improve the solution quality for a set of similar job-shop problems. Once trained on the sample job-shop problems (usually with small sizes), the adaptive algorithm solves a similar job-shop problem (with a moderate size or a large size) better than heuristics used as a benchmark at the learning stage of scheduling. Our adaptive algorithm does not guarantee to perform as an exact algorithm or better than a more sophisticated heuristic algorithm (like e.g. the shifting bottleneck one) which need a large running time. For an adaptive algorithm with a learning stage, the job-shop scheduling problem is modeled via a weighted mixed (disjunctive) graph with the conflict resolution strategy used for finding an appropriate schedule.

The paper deals with scheduling under uncertainty of the job processing times. The actual value of the processing time of a job becomes known only when the schedule is executed and may be equal to any value from the given interval. We propose an approach which consists of calculating measures of problem uncertainty to choose an appropriate method for solving an uncertain scheduling problem. These measures are based on the concept of a minimal dominant set containing at least one optimal schedule for each realization of the job processing times. For minimizing the sum of weighted completion times of the $$n$$ jobs to be processed on a single machine, it is shown that a minimal dominant set may be uniquely determined. We demonstrate how to use an uncertainty measure for selecting a method for finding an effective heuristic solution of the uncertain scheduling problem. The efficiency of the heuristic $$O(n\log n)$$ -algorithms is demonstrated on a set of randomly generated instances with $$100 \le n \le 5{,}000.$$ A similar uncertainty measure may be applied to many other scheduling problems with interval processing times.

Personal financial planning is the preparation of a series of ongoing target-oriented decisions concerning personal assets, incomes and expenses. An important task of personal financial planning is the generation of a financial schedule defining suitable times for realization of the expenses and incomes at a given point of time. We describe an integer programming model and algorithms for scheduling personal finances via the examination of a linear combination of the weighted objectives to be maximized. Solving the integer programming problem provides an optimal financial schedule which reflects an individual’s goals and preferences. We describe a worst-case scenario for a personal financial schedule with respect to possible variation of credit and interest rates. Computational results demonstrate the largest problems that are solvable via the algorithm based on schedule enumeration which is needed for a stability analysis.

A problem of train timetabling for a single-track railway is studied using a disjunctive graph model for the corresponding job-shop. The objective is to minimize the total weighted tardiness of the given trains. A shifting bottleneck algorithm is developed and tested to get a close to optimal schedule to the job-shop problem. At each iteration, this algorithm tries to minimize the total weighted tardiness of jobs (trains) with the given release times (departure times of the trains), the due dates, and the processing times on a single machine (single-track section between two stations). Since the latter problem is unary NP-hard, a heuristic procedure is used at each iteration of the shifting bottleneck algorithm. Computational results demonstrate the dependence of the CPU-time on the number of trains and single-track sections.

Train timetabling is a complex and time-consuming problem, which must be solved accurately to gain maximum performance on using the resources of a railway company (railways, trains, staff, etc.). An appropriate time bill (a timetable) must have a low latency, suitable train routes and a minimum time for traveling passenger trains and freight trains. In this paper, a genetic algorithm for routing and scheduling trains is developed to achieve efficient and robust train routes and a timetable. The algorithm may change the start times of the trains with the aim to find better times for the trains to start their moving and to have less number and a smaller total time of possible train delays. The algorithm changes some parts of the train paths to the destination to have a less mutual exclusion to use railways if it is allowable for a train (e.g., freight trains and express passenger trains are not allowed to stop at some middle stations of their routes). Simulations on a computer show that the developed genetic algorithm can reduce the tardiness of the trains to go from a source station to a destination.

For an assembly line, it is necessary to minimize the cycle time for processing a partially ordered set of operations V = {1, …, n} on a set of m linearly ordered working stations. The number m of stations and the initial processing times t = (t1, …, tn) of the operations V are given. However, for a subset V ⊆ V of the manual operations j ∈ V, it is impossible to fix the processing times tj for the whole life cycle of the assembly line. On the other hand, for each automated operation i ∈ V \ V, the processing time ti is fixed. We investigate the stability of an optimal line balance b0 of the assembly line with respect to variations of the processing times tj, j ∈ V. It is shown how to calculate the stability radius ρb0 (t) of an optimal line balance b0, i.e., the maximal value of simultaneous independent variations of the processing times of the manual operations with keeping the optimality of the line balance b0. We survey known results on the stability radius of an optimal line balance for a dual problem which is to minimize the number m of the working stations for the given cycle time.

The flow-shop minimum-length scheduling problem with n jobs processed on two machines is addressed where processing times are uncertain: only lower and upper bounds of the random processing times are given before scheduling, but their probability distributions are unknown. For such a problem, there may not exist a dominant schedule that remains optimal for all possible realizations of the processing times and so we look for a minimal set of schedules that are dominant. We obtain necessary and sufficient conditions for the case when it is possible to fix the order of two jobs in a minimal set of dominant schedules. The necessary and sufficient conditions are proven for the case when one schedule dominates all the others. We characterize also the case where there does not exist non-trivial schedule domination. All the conditions proven may be tested in polynomial time of n.

The flow-shop minimum-length scheduling problem with n jobs processed on two machines is addressed where processing times are uncertain (only lower and upper bounds for the random processing time are given, while the probability distribution between these bounds is unknown). For such a problem, there often does not exist a dominant schedule that remains optimal for all possible realizations of the job processing times, and so we look for a minimal dominant set of schedules, which may be represented by a partial job order. We investigate properties of this partial job order and show how to construct this order in polynomial time. The approach based on a set of dominant schedules allows us to find special cases of the problem when it is possible to find an optimal schedule in spite of the uncertainty of the numerical data.

The flow-shop minimum-length scheduling problem with n jobs processed on two machines is addressed where processing times are uncertain: only lower and upper bounds of the random processing times are given before scheduling, but their probability distributions are unknown. For such a problem, there may not exist a dominant schedule that remains optimal for all possible realizations of the processing times and so we look for a minimal set of schedules that are dominant. We obtain necessary and sufficient conditions for the case when it is possible to fix the order of two jobs in a minimal set of dominant schedules. The necessary and sufficient conditions are proven for the case when one schedule dominates all the others. We characterize also the case where there does not exist non-trivial schedule domination. All the conditions proven may be tested in polynomial time of n.

The paper surveys the complexity results for job shop, flow shop, open shop and mixed shop scheduling problems when the number n of jobs is fixed while the number r of operations per job is not restricted. In such cases, the asymptotical complexity of scheduling algorithms depends on the number m of machines for a flow shop and an open shop problem, and on the numbers m and r for a job shop problem. It is shown that almost all shop-scheduling problems with two jobs can be solved in polynomial time for any regular criterion, while those with three jobs are NP-hard. The only exceptions are the two-job, m-machine mixed shop problem without operation preemptions (which is NP-hard for any non-trivial regular criterion) and the n-job, m-machine open shop problem with allowed operation preemptions (which is polynomially solvable for minimizing makespan).

The problem of scheduling a set of jobs with unit operation times in a job shop to minimize total completion time is addressed. It is shown that this problem can be modeled as finding the optimal coloring of a special mixed graph. Subgraph of such a mixed graph without edges represents union of paths, and subgraph without arcs represents union of cliques. Finding the optimal coloring of the mixed graph with the criterion of minimizing the sum of maximal colors (used for the paths) is shown to determine a schedule for minimizing total completion time for processing jobs in a job shop. Since the problem is NP-hard, we develop a branch and bound algorithm for obtaining the optimal coloring of such a mixed graph. We develop a color-based branching scheme, dominance of the vertices in the solution tree, and three lower bounds of the objective function. The computational experiments indicate that the branch and bound algorithm performs well for randomly generated mixed graphs of order up to 200, if all the paths in the directed subgraph (job routes) have the same length, and of order up to 750 otherwise. Since in the considered job shop problem, machine repetition and absence of some machines in the job route are allowed, the developed methodology can be used to minimize total completion time in the job shop with arbitrary integer operation durations.

This article deals with the scheduling problem of minimizing the makespan in a two-machine job-shop with given w intervals of machine non-availability. It is known that this problem is binary (unary) NP-hard if there is at least one non-availability interval (if the number of non-availability intervals may be arbitrarily large), and all the jobs have the same machine route. We find sufficient conditions when Jackson's pair of permutations remains optimal for the two-machine job-shop problem with w1 non-availability intervals. Extensive computational studies show the effectiveness (in the number of problems solved) and efficiency (in computational time) of these conditions for the randomly generated instances with up to 10,000 jobs and w5000 non-availability intervals.

This article addresses the job-shop scheduling problem of minimizing the length of a schedule (makespan) for processing n jobs by one or two machines with sequence-dependent setup times and clean-up times. The processing of each job includes at most two operations that have to be non-preemptive. Machine routes may differ from job to job. If all setup and clean-up times are equal to zero, this problem is polynomially solvable via Jackson's pair of job permutations, otherwise it is NP-hard even if each of n jobs consists of one operation on the same machine. We present sufficient conditions when Jackson's pair of job permutations may be used for solving the two-machine job-shop scheduling problem with sequence-dependent setup times and clean-up times. For the general case of the latter problem, the results obtained provide polynomial lower and upper bounds for the objective function which may be used in an implicit enumeration technique, e.g., in a branch-and-bound algorithm.

We consider a job shop scheduling problem under uncertain processing times and fixed precedence and capacity constraints. Each of the random processing times can take any real value between given lower and upper bounds. The goal is to find a set of schedules which contains at least one optimal schedule (with mean flow time criterion) for any admissible realization of the random processing times. In order to compute such a set of schedules efficiently and keep it as small as possible, we develop several exact and heuristic algorithms and report computational experience based on randomly generated instances.