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.     

Isomorphic scheduling problems

We consider general properties of isomorphic scheduling problems that constitute a new class of pairs of mutually related scheduling problems. Any such a pair is composed of a scheduling problem with fixed job processing times and its time-dependent counterpart with processing times that are proportional-linear functions of the job starting times. In order to introduce the class formally, first we formulate a generic scheduling problem with fixed job processing times and define isomorphic problems by a one-to-one transformation of instances of the generic problem into instances of time-dependent scheduling problems with proportional-linear job processing times. Next, we prove basic properties of isomorphic scheduling problems and show how to convert polynomial algorithms for scheduling problems with fixed job processing times into polynomial algorithms for proportional-linear counterparts of the original problems. Finally, we show how are related approximation algorithms for isomorphic problems. Applying the results, we establish new worst-case results for time-dependent parallel-machine scheduling problems and prove that many single- and dedicated-machine time-dependent scheduling problems with proportional-linear job processing times are polynomially solvable.     

Sustainable workforce scheduling in construction program management

The multimode resource-constrained project scheduling problem (MRCPSP) deals with the scheduling of a set of projects with alternative requirements of renewable and non-renewable resources. Solutions to the MRCPSP usually consider objectives in terms of cost and time. However, social objectives related with the workforce may impact the performance of projects and affect program sustainability goals. To account for this new social input, this paper extends the MRCPSP and proposes a new multiobjective mixed-integer programming model. The proposed solution method uses an a priori lexicographic ordering of the objectives, followed by an ?-constraints approach. The model is illustrated with a case study of a construction program.     

Games,Critical Paths and Assignment Problems in Permutation Flow Shops and Cyclic Scheduling Flow Line Environments

In this paper we address the non-pre-emptive flow shop scheduling problem for makespan minimization in a new modelling framework. A lower bound generation scheme is developed by using appropriately defined linear assignment problems and, based on this new approach, a special class of permutation flow shop problems is identified. We present a game theoretic interpretation of our modelling approach which leads to an integer programming formulation of the scheduling problem. A new branch and bound scheme is developed based on these results. The major advantage of our modelling framework and branch-and- bound approach is that it can be easily extended to address a general class of cyclic scheduling problems for production flow lines with blocking. After a discussion of this extension, we report on computational experience that indicates the very satisfactory performance of the new optimal solution procedure for cyclic scheduling problems with finite capacity buffers.     

New directions in scheduling theory

This is an assessment of new developments in the theory of sequencing and scheduling. After a review of recent results and open questions within the traditional class of scheduling problems, we focus on the probabilistic analysis of scheduling algorithms and next discuss some extensions of the traditional problem class that seem to be of particular interest.     

Rollout Algorithms for Stochastic Scheduling Problems

Stochastic scheduling problems are difficult stochastic control problems with combinatorial decision spaces. In this paper we focus on a class of stochastic scheduling problems, the quiz problem and its variations. We discuss the use of heuristics for their solution, and we propose rollout algorithms based on these heuristics which approximate the stochastic dynamic programming algorithm. We show how the rollout algorithms can be implemented efficiently, with considerable savings in computation over optimal algorithms. We delineate circumstances under which the rollout algorithms are guaranteed to perform better than the heuristics on which they are based. We also show computational results which suggest that the performance of the rollout policies is near-optimal, and is substantially better than the performance of their underlying heuristics.     

Linear Time Algorithms for Parallel Machine Scheduling

This paper addresses linear time algorithms for parallel machine scheduling problems. We introduce a kind of threshold algorithms and discuss their main features. Three linear time threshold algorithm classes DT, PT and DTm are studied thoroughly. For all classes, we study their best possible algorithms among each class. We also present their application to several scheduling problems, The new algorithms are better than classical algorithms in time complexity and/or worst-case ratio. Computer-aided proof technique is used in the proof of main results, which greatly simplifies the proof and decreases case by case analysis.     

Global convergence in infeasible-interior-point algorithms

This paper presents a wide class of globally convergent interior-point algorithms for the nonlinear complementarity problem with a continuously differentiable monotone mapping in terms of a unified global convergence theory given by Polak in 1971 for general nonlinear programs. The class of algorithms is characterized as: Move in a Newton direction for approximating a point on the path of centers of the complementarity problem at each iteration. Starting from a strictly positive but infeasible initial point, each algorithm in the class either generates an approximate solution with a given accuracy or provides us with information that the complementarity problem has no solution in a given bounded set. We present three typical examples of our interior-point algorithms, a horn neighborhood model, a constrained potential reduction model with the use of the standard potential function, and a pure potential reduction model with the use of a new potential function.Research supported in part by Grant-in-Aids for Co-Operative Research (03832017) of the Japan Ministry of Education, Science and Culture.Corresponding author.     

Multi-depot vehicle scheduling problems with time windows and waiting costs

The multi-depot vehicle scheduling problem with time windows (MDVSPTW) consists of scheduling a fleet of vehicles to cover a set of tasks at minimum cost. Each task is restricted to begin within a prescribed time interval and vehicles are supplied by different depots. The problem is formulated as an integer nonlinear multi-commodity network flow model with time variables and is solved using a column generation approach embedded in a branch-and-bound framework. This paper breaks new ground by considering costs on exact waiting times between two consecutive tasks instead of minimal waiting times. This new and more realistic cost structure gives rise to a nonlinear objective function in the model. Optimal and heuristic versions of the algorithm have been extensively tested on randomly generated urban bus scheduling problem (UBSP) and freight transport scheduling problem (FTSP). The results show that such a general solution methodology outperforms specialized algorithms when minimal waiting costs are used, and can efficiently treat the case with exact waiting costs.     

Scheduling tasks on moving executors to minimise the maximum lateness

The problem of scheduling tasks on moving executors in complex operation systems with application to discrete manufacturing systems is considered. The minimisation of maximum lateness for unrelated executors and nonpreemptive, independent tasks is investigated in detail. It is assumed that tasks are performed at the stationary workstations by moving executors. This leads to a new optimisation problem, which is solved using the method based on the decomposition of the problem. The approximate solution method using known solution algorithms for the scheduling tasks and travelling salesman problems is presented. The considerations are completed with a numerical example which illustrates the main topics of the considerations.     

Scheduling non-professional table-tennis leagues

In this paper we consider a sports league scheduling problem which occurs in planning non-professional table-tennis leagues. The problem consists in finding a schedule for a time-relaxed double round robin tournament where different hard and soft constraints have to be taken into account. We model the problem as an integer linear program and a multi-mode resource-constrained project scheduling problem, respectively. Based on the second model a heuristic solution algorithm is proposed, which proceeds in two stages using local search and genetic algorithms. Computational results show the efficiency of the approaches.     

Hybrid Rollout Approaches for the Job Shop Scheduling Problem

In this paper, we focus on heuristic approaches for solving the deterministic job shop scheduling problem. More specifically, a new priority dispatch rule and hybrid rollout algorithms are developed for approaching the problem under consideration. The proposed solution algorithms are tested on a set of instances taken from the literature and compared with other methods. The computational results validate the effectiveness of the developed solution approaches and show that the proposed rollout algorithms are competitive with respect to several state-of-art heuristics for solving the job shop scheduling problem. The author thanks Dr. Marco Mancini and Dr. Alessandro Tarasio for valuable suggestions about computational issues.     

A Simulated Annealing Approach to the Solution of Flexible Labour Scheduling Problems

This paper presents a new solution approach to the discontinuous labour tour scheduling problem where the objective is to minimize the number of full-time employees required to satisfy forecast demand. Previous heuristic approaches have often limited the number of allowable tours by restricting labour scheduling flexibility in terms of shift length, shift start-times, days-off, meal-break placement, and other factors. These restrictions were essential to the tractability of the heuristic approaches but often resulted in solutions that contained a substantial amount of excess labour. In this study, we relaxed many of the restrictions on scheduling flexibility assumed in previous studies. The resulting problem environment contained more than two billion allowable tours, precluding the use of previous heuristic methods. Consequently, we developed a simulated annealing heuristic for solving the problem. An important facet of this new approach is an ‘intelligent’ improvement routine which eliminates the need for long run-times typically associated with simulated annealing algorithms. The simulated annealing framework does not rely on a special problem structure and our implementation rapidly converged to near-optimal solutions for all problems in the test environment.     

PROGRESS: Optimally solving the generalized resource-constrained project scheduling problem

This paper deals with the generalized resource-constrained project scheduling problem (GRCPSP) which extends the well-known resource-constrained project scheduling problem (RCPSP) by considering job specific release and due dates, non-negative minimum start-to-start time lags as well as time-varying resource availabilities. The structure of the project is represented by an acyclic network diagram. Though the extensions are of high practical importance, only a few exact solution procedures have been presented in the literature so far. Therefore, a new exact procedure PROGRESS is developed which includes new dominance rules as well as enhancements of existing ones. For evaluating the efficiency experimentally, new GRCPSP instances with 30 and 60 jobs are considered which extend the standard benchmark sets for the RCPSP generated by ProGen. PROGRESS shows superior performance when applied to the GRCPSP and is also very competitive in comparison to approaches proposed for the RCPSP.     

On the combinatorial structure of chromatic scheduling polytopes

Chromatic scheduling polytopes arise as solution sets of the bandwidth allocation problem in certain radio access networks, supplying wireless access to voice/data communication networks for customers with individual communication demands. To maintain the links, only frequencies from a certain spectrum can be used, which typically causes capacity problems. Hence it is necessary to reuse frequencies but no interference must be caused by this reuse. This leads to the bandwidth allocation problem, a special case of so-called chromatic scheduling problems. Both problems are NP-hard, and there do not even exist polynomial time algorithms with a fixed quality guarantee.As algorithms based on cutting planes have shown to be successful for many other combinatorial optimization problems, the goal is to apply such methods to the bandwidth allocation problem. For that, knowledge on the associated polytopes is required. The present paper contributes to this issue, exploring the combinatorial structure of chromatic scheduling polytopes for increasing frequency spans. We observe that the polytopes pass through various stages—emptyness, non-emptyness but low-dimensionality, full-dimensionality but combinatorial instability, and combinatorial stability—as the frequency span increases. We discuss the thresholds for this increasing “quantity” giving rise to a new combinatorial “quality” of the polytopes, and we prove bounds on these thresholds. In particular, we prove combinatorial equivalence of chromatic scheduling polytopes for large frequency spans and we establish relations to the linear ordering polytope.     

Some aspects of scatter search in the flow-shop problem

The flow-shop scheduling problem with the makespan criterion is a certain strongly NP-hard case from the domain of OR. This problem, having simple formulation contrasting with its troublesome, complex and time-consuming solution methods, is ideal for testing the quality of advanced combinatorial optimization algorithms. Although many excellent approximate algorithms for the flow-shop problem have been provided, up till now, in the literature, some theoretical and experimental problems associated with an algorithm’s activity still remain unexamined. In this paper, we provide a new view on the solution space and the search process. Relying upon it, we are proposing the new approximate algorithm, which applies some properties of neighborhoods, refers to the big valley phenomenon, uses some elements of the scatter search as well as the path relinking technique. This algorithm shows up to now unprecedented accuracy, obtainable within a short time on a PC, which has been confirmed in a wide variety of computer tests. Good properties of the algorithm remain scalable if the size of instances increases.     

A fast ant-colony algorithm for single-machine scheduling to minimize the sum of weighted tardiness of jobs

The problem of scheduling on a single machine is considered in this paper with the objective of minimizing the sum of weighted tardiness of jobs. A new ant-colony optimization (ACO) algorithm, called fast ACO (FACO), is proposed and analysed for solving the single-machine scheduling problem. By considering the benchmark problems available in the literature for analysing the performance of algorithms for scheduling on a single machine with the consideration of weighted tardiness of jobs, we validate the appropriateness of the proposed local-search schemes and parameter settings used in the FACO. We also present a comparison of the requirements of CPU time for solving the single-machine total-weighted tardiness problem by the FACO and the existing algorithms.     

A Gradient Flow Approach to Optimal Model Reduction of Discrete-Time Periodic Systems

This paper is concerned with the optimal model reduction for linear discrete periodic time-varying systems and digital filters. Specifically, for a given stable periodic time-varying model, we shall seek a lower order periodic time-varying model to approximate the original model in an optimal H ₂ norm sense. By orthogonal projections of the original model, we convert the optimal periodic model reduction problem into an unconstrained optimization problem. Two effective algorithms are then developed to solve the optimization problem. The algorithms ensure that the H ₂ cost decreases monotonically and converges to an optimal (local) solution. Numerical examples are given to demonstrate the computational efficiency of the proposed method. The present paper extends the optimal model reduction for linear time invariant systems to linear periodic discrete time-varying systems.     

Permutation-induced acyclic networks for the job shop scheduling problem

In the literature of the combinatorial optimization problems, it is a commonplace to find more than one mathematical model for the same problem. The significance of a model may be measured in terms of the efficiency of the solution algorithms that can be built upon it. The purpose of this article is to present a new network model for the well known combinatorial optimization problem – the job shop scheduling problem. The new network model has similar structure as the disjunctive graph model except that it uses permutations of jobs as decision variables instead of the binary decision variables associated with the disjunctive arcs. To assess the significance of the new model, the performances of exact branch-and-bound algorithmic implementations that are based on both the new model and the disjunctive graph model are compared.