Shifting representation search for hybrid flexible flowline problems

This paper considers the hybrid flexible flowline scheduling problem with a set of additional restrictions and generalizations that are common in practice. These include precedence constraints, sequence dependent setup times, time lags, machine eligibility and release times. There are many potential solution representations for this problem, ranging from simple and compact, to more complex and complete. Typically, when choosing the degree of detail of the solution representation, a tradeoff can be found between efficiency of the algorithm and the size of the search space. Several adaptations of existing methods are introduced (memetic algorithm, iterated local search, iterated greedy), as well as a novel algorithm called shifting representation search (SRS). This new method starts with an iterated greedy algorithm applied to a permutation version of the problem and at a given time, switches to an iterated local search on the full search space. As far as we know, this shift of the solution representation is new in the scheduling literature. Experimental results and statistical tests clearly prove the superiority of SRS compared with classical and existing methods.     

Iterated greedy local search methods for unrelated parallel machine scheduling

This work deals with the parallel machine scheduling problem which consists in the assignment of n jobs on m   parallel machines. The most general variant of this problem is when the processing time depends on the machine to which each job is assigned to. This case is known as the unrelated parallel machine problem. Similarly to most of the literature, this paper deals with the minimization of the maximum completion time of the jobs, commonly referred to as makespan (_Cmax)$(C_{\text{max}})$. Many algorithms and methods have been proposed for this hard combinatorial problem, including several highly sophisticated procedures. By contrast, in this paper we propose a set of simple iterated greedy local search based metaheuristics that produce solutions of very good quality in a very short amount of time. Extensive computational campaigns show that these solutions are, most of the time, better than the current state-of-the-art methodologies by a statistically significant margin.     

Iterated greedy for the maximum diversity problem

The problem of choosing a subset of elements with maximum diversity from a given set is known as the maximum diversity problem. Many algorithms and methods have been proposed for this hard combinatorial problem, including several highly sophisticated procedures. By contrast, in this paper we present a simple iterated greedy metaheuristic that generates a sequence of solutions by iterating over a greedy construction heuristic using destruction and construction phases. Extensive computational experiments reveal that the proposed algorithm is highly effective as compared to the best-so-far metaheuristics for the problem under consideration.     

Multi-coloring and job-scheduling with assignment and incompatibility costs

Consider a scheduling problem (P) which consists of a set of jobs to be performed within a limited number of time periods. For each job, we know its duration as an integer number of time periods, and preemptions are allowed. The goal is to assign the required number of time periods to each job while minimizing the assignment and incompatibility costs. When a job is performed within a time period, an assignment cost is encountered, which depends on the involved job and on the considered time period. In addition, for some pairs of jobs, incompatibility costs are encountered if they are performed within common time periods. (P) can be seen as an extension of the multi-coloring problem. We propose various solution methods for (P) (namely a greedy algorithm, a descent method, a tabu search and a genetic local search), as well as an exact approach. All these methods are compared on different types of instances.     

Parallel hybrid heuristics for the permutation flow shop problem

This paper addresses the Permutation Flowshop Problem with minimization of makespan, which is denoted by Fm|prmu|C _max. In the permutational scenario, the sequence of jobs has to remain the same in all machines. The Flowshop Problem (FSP) is known to be NP-hard when more than three machines are considered. Thus, for medium and large scale instances, high-quality heuristics are needed to find good solutions in reasonable time. We propose and analyse parallel hybrid search methods that fully use the computational power of current multi-core machines. The parallel methods combine a memetic algorithm (MA) and several iterated greedy algorithms (IG) running concurrently. Two test scenarios were included, with short and long CPU times. The tests were conducted on the set of benchmark instances introduced by Taillard (Eur. J. Oper. Res. 64:278?C285, 1993), commonly used to assess the performance of new methods. Results indicate that the use of the MA to manage a pool of solutions is highly effective, allowing the improvement of the best known upper bound for one of the instances.     

A branch and bound to minimize the number of late jobs on a single machine with release time constraints

This paper presents a branch and bound algorithm for the single machine scheduling problem 1|r_i|∑U_i where the objective function is to minimize the number of late jobs. Lower bounds based on a Lagrangian relaxation and no reductions to polynomially solvable cases are proposed. Efficient elimination rules together with strong dominance relations are also used to reduce the search space. A branch and bound exploiting these techniques solves to optimality instances with up to 200 jobs, improving drastically the size of problems that could be solved by exact methods up to now.     

A modified greedy analysis pursuit algorithm for the cosparse analysis model

In the past decade, the sparse representation synthesis model has been deeply researched and widely applied in signal processing. Recently, a cosparse analysis model has been introduced as an interesting alternative to the sparse representation synthesis model. The sparse synthesis model pay attention to non-zero elements in a representation vector x, while the cosparse analysis model focuses on zero elements in the analysis representation vector Ωx. This paper mainly considers the problem of the cosparse analysis model. Based on the greedy analysis pursuit algorithm, by constructing an adaptive weighted matrix W _k?1, we propose a modified greedy analysis pursuit algorithm for the sparse recovery problem when the signal obeys the cosparse model. Using a weighted matrix, we fill the gap between greedy algorithm and relaxation techniques. The standard analysis shows that our algorithm is convergent. We estimate the error bound for solving the cosparse analysis model, and then the presented simulations demonstrate the advantage of the proposed method for the cosparse inverse problem.     

Heuristic Algorithms and Scatter Search for the Cardinality Constrained P||Cmax Problem

We consider the generalization of the classical P||C_max problem (assign n jobs to m identical parallel processors by minimizing the makespan) arising when the number of jobs that can be assigned to each processor cannot exceed a given integer k. The problem is strongly NP-hard for any fixed k > 2. We briefly survey lower and upper bounds from the literature. We introduce greedy heuristics, local search and a scatter search approach. The effectiveness of these approaches is evaluated through extensive computational comparison with a depth-first branch-and-bound algorithm that includes new lower bounds and dominance criteria.     

Module structures and the derived functors of iterated loop functors on unstable modules over the Steenrod algebra

The calculation of the iterated loop functors and their left derived functors on the category of unstable modules over the Steenrod algebra is a non-trivial problem; Singer constructed an explicit and functorial chain complex to calculate these functors. The results of Singer are analysed to give information on the behaviour of these functors with respect to the nilpotent filtration of the category of unstable modules.We show that, if an unstable module M supports an action of an unstable algebra K, then the derived functors of the iterated loop functors applied to M support actions of iterated doubles of K. This allows the finiteness results of Henn on unstable modules which support actions of unstable algebras to be applied to deduce structural results on the derived functors of iterated loops on such modules.     

An exact algorithm for the bi-objective timing problem

The timing problem in the bi-objective just-in-time single-machine job-shop scheduling problem (JiT-JSP) is the task to schedule N jobs whose order is fixed, with each job incurring a linear earliness penalty for finishing ahead of its due date and a linear tardiness penalty for finishing after its due date. The goal is to minimize the earliness and tardiness simultaneously. We propose an exact greedy algorithm that finds the entire Pareto front in \(O(N^2)\) time. This algorithm is asymptotically optimal.     

Analysis of a time-dependent scheduling problem by signatures of deterioration rate sequences

In the paper a single machine time-dependent scheduling problem is considered. The processing time p_j of each job is described by a function of the starting time t of the job, p_j=1+α_jt, where the job deterioration rate α_j?0 for j=0,1,…,n and t?0. Jobs are nonpreemptable and independent, there are no ready times and no deadlines. The criterion of optimality of a schedule is the total completion time.First, the notion of a signature for a given sequence of job deterioration rates is introduced, two types of the signature are defined and their properties are shown. Next, on the basis of these properties a greedy polynomial-time approximation algorithm for the problem is formulated. This algorithm, starting from an initial sequence, iteratively constructs a new sequence concatenating the previous sequence with new elements, according to the sign of one of the signatures of this sequence.Finally, these results are applied to the problem with job deterioration rates which are consecutive natural numbers, α_j=j for j=0,1,…,n. Arguments supporting the conjecture that in this case the greedy algorithm is optimal are presented.     

Using Lagrangian dual information to generate degree constrained spanning trees

In this paper, a Lagrangian-based heuristic is proposed for the degree constrained minimum spanning tree problem. The heuristic uses Lagrangian relaxation information to guide the construction of feasible solutions to the problem. The scheme operates, within a Lagrangian relaxation framework, with calls to a greedy construction heuristic, followed by a heuristic improvement procedure. A look ahead infeasibility prevention mechanism, introduced into the greedy heuristic, allowed us to solve instances of the problem where some of the vertices are restricted to having degrees 1 or 2. Furthermore, in order to cut down on CPU time, a restricted version of the original problem is formulated and used to generate feasible solutions. Extensive computational experiments were conducted and indicate that the proposed heuristic is competitive with the best heuristics and metaheuristics in the literature.     

Scheduling on parallel identical machines to minimize total tardiness

This paper focuses on the problem of scheduling n independent jobs on m identical parallel machines for the objective of minimizing total tardiness of the jobs. We develop dominance properties and lower bounds, and develop a branch and bound algorithm using these properties and lower bounds as well as upper bounds obtained from a heuristic algorithm. Computational experiments are performed on randomly generated test problems and results show that the algorithm solves problems with moderate sizes in a reasonable amount of computation time.     

Mixed integer programming models for dispatching vehicles at a container terminal

This paper presents scheduling models for dispatching vehicles to accomplish a sequence of container jobs at the container terminal, in which the starting times as well as the order of vehicles for carrying out these jobs need to be determined. To deal with this scheduling problem, three mixed 0–1 integer programming models, Model I, Model II and Model III are provided. We present interesting techniques to reformulate the two mixed integer programming models, Model I and Model II, as pure 0–1 integer programming problems with simple constraint sets and present a lower bound for the optimal value of Model I. Model III is a complicated mixed integer programming model because it involves a set of non-smooth constraints, but it can be proved that its solutions may be obtained by the so-called greedy algorithm. We present numerical results showing that Model III is the best among these three models and the greedy algorithm is capable of solving large scale problems.     

A greedy randomised search heuristic for time-constrained vehicle scheduling and the incorporation of a learning strategy

In this paper, a greedy randomised heuristic is applied to a complex vehicle-scheduling problem with tight time windows and additional constraints. Two forms of adaptive search are identified, which are referred to as local and global adaptation. In both cases, the calculation of the greedy function is modified by an amount which measures heuristically the quality of the partial solution that is obtained when a decision is made. One use of global adaptation is an approach which is referred to as a learning strategy since it involves an attempt to learn from previous mistakes by an appropriate updating of the greedy function from one run of the heuristic to the next. Such a learning strategy forms the main focus of this paper. Experimental results show that it is potentially a powerful heuristic device, since it greatly enhanced the effectiveness of those methods that had previously been applied to this problem; that is, a greedy randomized heuristic which also incorporated a look-ahead strategy and a version of the well-known savings method. It is suggested that learning strategies of the general type introduced in this paper have potential for application to other combinatorial optimisation problems.     

Approximability of single machine scheduling with fixed jobs to minimize total completion time

We consider the single machine scheduling problem to minimize total completion time with fixed jobs, precedence constraints and release dates. There are some jobs that are already fixed in the schedule. The remaining jobs are free to be assigned to any free-time intervals on the machine in such a way that they do not overlap with the fixed jobs. Each free job has a release date, and the order of processing the free jobs is restricted by the given precedence constraints. The objective is to minimize the total completion time. This problem is strongly NP-hard. Approximability of this problem is studied in this paper. When the jobs are processed without preemption, we show that the problem has a linear-time n-approximation algorithm, but no pseudopolynomial-time (1 − δ)n-approximation algorithm exists even if all the release dates are zero, for any constant δ > 0, if P ≠ NP, where n is the number of jobs; for the case that the jobs have no precedence constraints and no release dates, we show that the problem has no pseudopolynomial-time (2 − δ)-approximation algorithm, for any constant δ > 0, if P ≠ NP, and for the weighted version, we show that the problem has no polynomial-time 2^q(n)-approximation algorithm and no pseudopolynomial-time q(n)-approximation algorithm, where q(n) is any given polynomial of n. When preemption is allowed, we show that the problem with independent jobs can be solved in O(n log n) time with distinct release dates, but the weighted version is strongly NP-hard even with no release dates; the problems with weighted independent jobs or with jobs under precedence constraints are shown having polynomial-time n-approximation algorithms. We also establish the relationship of the approximability between the fixed job scheduling problem and the bin-packing problem.     

A note on two-agent scheduling on an unbounded parallel-batching machine with makespan and maximum lateness objectives

This paper studies the two-agent scheduling on an unbounded parallel-batching machine. In the problem, there are two agents A and B with each having their own job sets. The jobs of a common agent can be processed in a common batch. Moreover, each agent has an objective function to be minimized. The objective function of agent A is the makespan of his jobs and the objective function of agent B is maximum lateness of his jobs. Yazdani Sabouni and Jolai [M.T. Yazdani Sabouni, F. Jolai, Optimal methods for batch processing problem with makespan and maximum lateness objectives, Appl. Math. Model. 34 (2010) 314–324] presented a polynomial-time algorithm for the problem to minimize a positive combination of the two agents’ objective functions. Unfortunately, their algorithm is incorrect. We then dwell on the problem and present a polynomial-time algorithm for finding all Pareto optimal solutions of this two-agent parallel-batching scheduling problem.     

Rooms with a view: A novel approach to iterated multidimensional wave conversion

Ray tracing in the presence of linear mode conversion leads to a ‘splitting’ of an incoming ray into two outgoing rays. When the rays are confined to a cavity, the rays can re-enter the conversion region many times, leading to iterated conversion. In this paper, we present new methods for the analysis of this problem. These involve a shift from local to global methods of analysis, and a shift in emphasis from the study of ray evolution in the dispersion surface to the study of the iterated dynamics of rays crossing the conversion surface. The analytical methods are quite general and can be applied in phase spaces of arbitrary dimension. In two spatial dimensions, (x, y), i.e. with a four-dimensional ray space, (x, y, k_x, k_y), rays are confined to three-dimensional regions called rooms, with one room for each wave type. In these rooms the rays do not cross, but when they intersect the conversion surface a family of converted rays is produced in the other room. The use of rooms allows a full view of the phase space dynamics of the iterated conversion of ray families. A simple two-dimensional model, inspired by the Budden resonance model, is presented as an example of these ideas.     

An iterated greedy metaheuristic for the blocking job shop scheduling problem

In this paper we consider a job shop scheduling problem with blocking (BJSS) constraints. Blocking constraints model the absence of buffers (zero buffer), whereas in the traditional job shop scheduling model buffers have infinite capacity. There are two known variants of this problem, namely the blocking job shop scheduling with swap allowed (BWS) and the one with no swap allowed (BNS). This scheduling problem is receiving an increasing interest in the recent literature, and we propose an Iterated Greedy (IG) algorithm to solve both variants of the problem. IG is a metaheuristic based on the repetition of a destruction phase, which removes part of the solution, and a construction phase, in which a new solution is obtained by applying an underlying greedy algorithm starting from the partial solution. A comparison with recent published results shows that the iterated greedy algorithm outperforms other state-of-the-art algorithms on benchmark instances. Moreover it is conceptually easy to implement and has a broad applicability to other constrained scheduling problems.     

Local search algorithms for the min-max loop layout problem

In the min-max loop layout problem, machines are to be arranged around a loop of conveyor belt. The ordering of the machines dictates the number of circuits of the conveyor belt required to manufacture each of several products. The goal is to find an ordering of the machines that minimises the maximum number of circuits required for the manufacture of any of the products. Since the problem is strongly NP-hard, the study of heuristic methods is of interest. This paper proposes iterated descent and tabu search algorithms, and a randomised insertion algorithm. Results of extensive computational tests show that all of our algorithms outperform a previously known algorithm that applies a greedy heuristic to the solution of a linear programming relaxation. The best quality solutions are obtained with iterated descent. This adds further evidence to the belief that iterated descent can produce high quality solutions to a variety of combinatorial optimisation problems. Moreover, unlike some other local search algorithms, iterated descent does not require much tuning in order to be competitive.