Scheduling jobs on identical machines with agreement graph

We consider the following problem of scheduling with agreements: a set of jobs must be scheduled non-preemptively on identical machines subject to constraints that only some specific jobs can be scheduled concurrently on different machines. These constraints are represented by an agreement graph and the aim is to minimize the makespan. This problem is NP-hard. We study the complexity of the problem for two machines and arbitrary bipartite agreement graphs, in particular we prove the NP-hardness of the open problem proposed in the literature which is the case of two machines with processing times at most 3. We propose list algorithms with empirical results for the problem in the general case.     

Block models for scheduling jobs on two parallel machines with a single server

We consider the problem of scheduling a set of non-preemptable jobs on two identical parallel machines such that the makespan is minimized. Before processing, each job must be loaded on a machine, which takes a given setup time. All these setups have to be done by a single server which can handle at most one job at a time. For this problem, we propose a mixed integer linear programming formulation based on the idea of decomposing a schedule into a set of blocks. We compare the results obtained by the model suggested with known heuristics from the literature.     

Modeling realistic hybrid flexible flowshop scheduling problems

This paper aims to contribute to the recent research efforts to bridge the gap between the theory and the practice of scheduling by modelizing a realistic manufacturing environment and analyzing the effect of the inclusion of several characteristics in the problem formulation. There are several constraints and characteristics that affect the scheduling operations at companies. While these constraints are many times tackled in the literature, they are seldom considered together inside the same problem formulation. We propose a formulation along with a mixed integer modelization and some heuristics for the problem of scheduling n jobs on m stages where at each stage we have a known number of unrelated machines. The jobs might skip stages and, therefore, we have what we call a hybrid flexible flowshop problem. We also consider per machine sequence-dependent setup times which can be anticipatory and non-anticipatory along with machine lags, release dates for machines, machine eligibility and precedence relationships among jobs. Manufacturing environments like this appear in sectors like food processing, ceramic tile manufacturing and several others. The optimization criterion considered is the minimization of the makespan. The MIP model and the heuristics proposed are tested against a comprehensive benchmark and the results evaluated by advanced statistical tools that make use of decision trees and experimental designs. The results allow us to identify the constraints that increase the difficulty.     

A new Lagrangian relaxation algorithm for hybrid flowshop scheduling to minimize total weighted completion time

We investigate the problem of scheduling n jobs in s-stage hybrid flowshops with parallel identical machines at each stage. The objective is to find a schedule that minimizes the sum of weighted completion times of the jobs. This problem has been proven to be NP-hard. In this paper, an integer programming formulation is constructed for the problem. A new Lagrangian relaxation algorithm is presented in which precedence constraints are relaxed to the objective function by introducing Lagrangian multipliers, unlike the commonly used method of relaxing capacity constraints. In this way the relaxed problem can be decomposed into machine type subproblems, each of which corresponds to a specific stage. A dynamic programming algorithm is designed for solving parallel identical machine subproblems where jobs may have negative weights. The multipliers are then iteratively updated along a subgradient direction. The new algorithm is computationally compared with the commonly used Lagrangian relaxation algorithms which, after capacity constraints are relaxed, decompose the relaxed problem into job level subproblems and solve the subproblems by using the regular and speed-up dynamic programming algorithms, respectively. Numerical results show that the new Lagrangian relaxation method produces better schedules in much shorter computation time, especially for large-scale problems.     

Two-machine flowshop scheduling with flexible operations and controllable processing times

We consider a two-machine flowshop scheduling problem with identical jobs. Each of these jobs has three operations, where the first operation must be performed on the first machine, the second operation must be performed on the second machine, and the third operation (named as flexible operation) can be performed on either machine but cannot be preempted. Highly flexible CNC machines are capable of performing different operations. Furthermore, the processing times on these machines can be changed easily in albeit of higher manufacturing cost by adjusting the machining parameters like the speed and/or feed rate of the machine. The overall problem is to determine the assignment of the flexible operations to the machines and processing times for each operation to minimize the total manufacturing cost and makespan simultaneously. For such a bicriteria problem, there is no unique optimum but a set of nondominated solutions. Using ?-constraint$?\mathrm{-}\mathrm{constraint}$ approach, the problem could be transformed to be minimizing total manufacturing cost for a given upper limit on the makespan. The resulting single criterion problem can be reformulated as a mixed integer nonlinear problem with a set of linear constraints. We use this formulation to optimally solve small instances of the problem while a heuristic procedure is constructed to solve larger instances in a reasonable time.     

Scheduling of manufacturing systems using the Lagrangian relaxationtechnique

The practical solutions for three manufacturing scheduling problems are examined. As each problem is formulated, constraints are added or modified to reflect increasing real world complexity. The first problem considers scheduling single-operation jobs on identical machines. The second problem is concerned with scheduling multiple-operation jobs with simple fork/join precedence constraints on identical machines. The third problem is the job shop problem in which multiple-operation jobs with general precedence constraints are scheduled on multiple machine types Langrangian relaxation is used to decompose each of the scheduling problems into job- or operation-level subproblems. The subproblems are easier to solve than the original problem and have intuitive appeal. This technique results in algorithms which generate near-optimal schedules efficiently, while giving a lower bound on the optimal cost. In resolving the scheduling problem from one time instant to the next, the Lagrange multipliers from the last schedule can be used to initialize the multipliers, further reducing the computation time     

Symmetry Breaking Constraints for Value Symmetries in Constraint Satisfaction

Constraint satisfaction problems (CSPs) sometimes contain both variable symmetries and value symmetries, causing adverse effects on CSP solvers based on tree search. As a remedy, symmetry breaking constraints are commonly used. While variable symmetry breaking constraints can be expressed easily and propagated efficiently using lexicographic ordering, value symmetry breaking constraints are often difficult to formulate. In this paper, we propose two methods of using symmetry breaking constraints to tackle value symmetries. First, we show theoretically when value symmetries in one CSP correspond to variable symmetries in another CSP of the same problem. We also show when variable symmetry breaking constraints in the two CSPs, combined using channeling constraints, are consistent. Such results allow us to tackle value symmetries efficiently using additional CSP variables and channeling constraints. Second, we introduce value precedence, a notion which can be used to break a common class of value symmetries, namely symmetries of indistinguishable values. While value precedence can be expressed using inefficient if-then constraints in existing CSP solvers, we propose efficient propagation algorithms for implementing global value precedence constraints. We also characterize several theoretical properties of the value precedence constraints. Extensive experiments are conducted to verify the feasibility and efficiency of the two proposals.     

Scheduling two-stage hybrid flow shops with parallel batch, release time, and machine eligibility constraints

This paper investigates a difficult scheduling problem on a specialized two-stage hybrid flow shop with multiple processors that appears in semiconductor manufacturing industry, where the first and second stages process serial jobs and parallel batches, respectively. The objective is to seek job-machine, job-batch, and batch-machine assignments such that makespan is minimized, while considering parallel batch, release time, and machine eligibility constraints. We first propose a mixed integer programming (MIP) formulation for this problem, then gives a heuristic approach for solving larger problems. In order to handle real world large-scale scheduling problems, we propose an efficient dispatching rule called BFIFO that assigns jobs or batches to machines based on first-in-first-out principle, and then give several reoptimization techniques using MIP and local search heuristics involving interchange, translocation and transposition among assigned jobs. Computational experiments indicate our proposed re-optimization techniques are efficient. In particular, our approaches can produce good solutions for scheduling up to 160 jobs on 40 machines at both stages within 10?min.     

Minimizing weighted earliness–tardiness on parallel machines using hybrid metaheuristics

We consider the problem of scheduling a set of jobs on a set of identical parallel machines where the objective is to minimize the total weighted earliness and tardiness penalties with respect to a common due date. We propose a hybrid heuristic algorithm for constructing good solutions, combining priority rules for assigning jobs to machines and a local search with exact procedures for solving the one-machine subproblems. These solutions are then used in two metaheuristic frameworks, Path Relinking and Scatter Search, to obtain high quality solutions for the problem.The algorithms are tested on a large number of test instances to assess the efficiency of the proposed strategies.The results show that our algorithms consistently outperform the best reported results for this problem.     

Minimizing total weighted flowtime subject to minimum makespan on two identical parallel machines

We study the problem of scheduling n jobs on two identical parallel processors or machines where an optimal schedule is defined as one with the shortest total weighted flowtime (i.e., the sum of the weighted completion time of all jobs), among the set of schedules with minimum makespan (i.e., the completion time of the last job finished). We present a two phase non-linear Integer Programming formulation for its solution, admittedly not to be practical or useful in most cases, but theoretically interesting since it models the problem. Thus, as an alternative, we propose an optimization algorithm, for small problems, and a heuristic, for large problems, to find optimal or near optimal solutions. Furthermore, we perform a computational study to evaluate and compare the effectiveness of the two proposed methods.     

A fluid approach to large volume job shop scheduling

We consider large volume job shop scheduling problems, in which there is a fixed number of machines, a bounded number of activities per job, and a large number of jobs. In large volume job shops it makes sense to solve a fluid problem and to schedule the jobs in such a way as to track the fluid solution. There have been several papers which used this idea to propose approximate solutions which are asymptotically optimal as the volume increases. We survey some of these results here. In most of these papers it is assumed that the problem consists of many identical copies of a fixed set of jobs. Our contribution in this paper is to extend the results to the far more general situation in which the many jobs are all different. We propose a very simple heuristic which can schedule such problems. We discuss asymptotic optimality of this heuristic, under a wide range of previously unexplored situations. We provide a software package to explore the performance of our policy, and present extensive computational evidence for its effectiveness.     

Approaches to modeling train scheduling problems as job-shop problems with blocking constraints

The problem of scheduling a set of trains traveling through a given railway network consisting of single tracks, sidings and stations is considered. For every train a fixed route and travel times, an earliest departure time at the origin and a desired arrival time at the destination are given. A feasible schedule has to be determined which minimizes total tardiness of all trains at their destinations. This train scheduling problem is modeled as a job-shop scheduling problem with blocking constraints, where jobs represent trains and machines constitute tracks or track sections. Four MIP formulations without time-indexed variables are developed based on two different transformation approaches of parallel tracks and two different types of decision variables leading to job-shop scheduling problems with or without routing flexibility. A computational study is made on hard instances with up to 20 jobs and 11 machines to compare the MIP models in terms of total tardiness values, formulation size and computation time.     

Approximation schemes for the Min-Max Starting Time Problem

We consider the off-line scheduling problem of minimizing the maximal starting time. The input to this problem is a sequence of n jobs and m identical machines. The goal is to assign the jobs to the machines so that the first time at which all jobs have already started running is minimized, under the restriction that the processing of the jobs on any given machine must respect their original order. Our main result is a polynomial time approximation scheme (PTAS) for this problem in the case where m is considered as part of the input. As the input to this problem is a sequence of jobs, rather than a set of jobs where the order is insignificant, we present techniques that are designed to handle order constraints imposed by the sequence. Those techniques are combined with common techniques of assignment problems in order to yield a PTAS for this problem. We also show that when m is a constant, the problem admits a fully polynomial time approximation scheme. Finally, we show that the makespan problem in the linear hierarchical model may be reduced to the min-max starting time problem, thus concluding that the former problem also admits a PTAS.Received: 26 May 2003, Published online: 5 August 2004A preliminary version of this paper appeared in Proc. of 28th Mathematical Foundations of Computer Science (2003)...... Research supported in part by the Israel Science Foundation, (grant no. 250/01)     

Minimizing makespan subject to minimum flowtime on two identical parallel machines

We consider the problem of scheduling jobs on two parallel identical machines where an optimal schedule is defined as one that gives the smallest makespan (the completion time of the last job) among the set of schedules with optimal total flowtime (the sum of the completion times of all jobs). We propose an algorithm to determine optimal schedules for the problem, and describe a modified multifit algorithm to find an approximate solution to the problem in polynomial computational time. Results of a computational study to compare the performance of the proposed algorithms with a known heuristic shows that the proposed heuristic and optimization algorithms are quite effective and efficient in solving the problem.Scope and purposeMultiple objective optimization problems are quite common in practice. However, while solving scheduling problems, optimization algorithms often consider only a single objective function. Consideration of multiple objectives makes even the simplest multi-machine scheduling problems NP-hard. Therefore, enumerative optimization techniques and heuristic solution procedures are required to solve multi-objective scheduling problems. This paper illustrates the development of an optimization algorithm and polynomially bounded heuristic solution procedures for the scheduling jobs on two identical parallel machines to hierarchically minimize the makespan subject to the optimality of the total flowtime.     

Static and dynamic structural symmetry breaking

We reconsider the idea of structural symmetry breaking for constraint satisfaction problems (CSPs). We show that the dynamic dominance checks used in symmetry breaking by dominance-detection search for CSPs with piecewise variable and value symmetries have a static counterpart: there exists a set of constraints that can be posted at the root node and that breaks all the compositions of these (unconditional) symmetries. The amount of these symmetry-breaking constraints is linear in the size of the problem, and yet they are able to remove a super-exponential number of symmetries on both values and variables. Moreover, we compare the search trees under static and dynamic structural symmetry breaking when using fixed variable and value orderings. These results are then generalised to wreath-symmetric CSPs with both variable and value symmetries. We show that there also exists a polynomial-time dominance-detection algorithm for this class of CSPs, as well as a linear-sized set of constraints that breaks these symmetries statically.     

Series production in a basic re-entrant shop to minimize makespan or total flow time

This paper addresses a real life shop scheduling problem in a manufacturing company. In this problem, a set of n identical jobs are to be processed on two machines. Every job visits one of the machines more than once. This is therefore a re-entrant shop. Due to the fact that the jobs are identical, the decision version of this problem is even not in the class NP. We give an optimal schedule to minimize the makespan. Since the total flow time depends on the relations between the processing times, we decompose this problem into sub-problems according to the relations between the processing times. We prove various properties of optimal solutions and, based on these properties, we provide an optimal solution for all the sub-problems except one of them. For the sole remaining sub-problem, we prove a dominance property which allows to consider a part of schedules to find an optimal one.     

On the identical parallel-machine rescheduling with job rework disruption

This paper investigates an issue of rescheduling on identical parallel machines where the original jobs have already been scheduled to minimize the total completion time, when a single set of jobs to be reworked re-arrives and creates a job rework disruption. Two conflicting rescheduling criteria are considered: the total completion time, as the measure of scheduling cost (efficiency); and the number of jobs assigned to different machines in the original schedule and newly generated schedule, as the measure of disruption cost (stability). Further, the rescheduling problem is defined as a bi-criteria scheduling problem. Two polynomial time algorithms are proposed to lexicographically optimize the two criteria. Besides, the set of all efficient schedules with respect to the two criteria can be also generated in polynomial time.     

On-line hierarchical job scheduling on grids with admissible allocation

In this paper, we address non-preemptive online scheduling of parallel jobs on a Grid. Our Grid consists of a large number of identical processors that are divided into several machines. We consider a Grid scheduling model with two stages. At the first stage, jobs are allocated to a suitable machine, while at the second stage, local scheduling is independently applied to each machine. We discuss strategies based on various combinations of allocation strategies and local scheduling algorithms. Finally, we propose and analyze a scheme named adaptive admissible allocation. This includes a competitive analysis for different parameters and constraints. We show that the algorithm is beneficial under certain conditions and allows for an efficient implementation in real systems. Furthermore, a dynamic and adaptive approach is presented which can cope with different workloads and Grid properties.     

Parallel machine problems with equal processing times: a survey

The basic scheduling problem we are dealing with is the following. There are n jobs, each requiring an identical execution time. All jobs have to be processed on a set of parallel machines. Preemptions can be either allowed or forbidden. The aim is to construct a feasible schedule such that a given criterion is minimized. In this paper, we survey existing approaches for the problem class considered.