Search

A recent Journal of Scheduling paper by Chen and Zhang (J Sched, 2020. https://doi.org/10.1007/s10951-020-00668-1) proves that the problem of scheduling coupled tasks to minimize total completion time is NP-hard in the strong sense even for the case with all tasks having the same, though not necessarily unit, processing times. This note shows a simpler proof of that result, and strengthens it by proving that the problem is NP-hard in the strong sense even if all tasks are unit-time. [ABSTRACT FROM AUTHOR]

This paper addresses the problem of open shop scheduling on two machines with resources constraints. In the context of our study, in order to be executed, a job requires first, for its preparation for a given period of time, a number of resources which cannot exceed a given resource capacity. Then, it goes onto its execution while the resources allocated to it become available again. We seek a schedule that minimizes the makespan. We first prove the $\mathcal{N}\mathcal{P}$ -hardness of several versions of this problem. Then, we present a well solvable case, lower bounds, and heuristic algorithms along with an experimental study. [ABSTRACT FROM AUTHOR]

This paper addresses a generalization of the coupled-operations scheduling problem in the context of a flow shop environment. We consider the two-machine scheduling problem with the objective of minimizing the makespan. Each job consists of a coupled-operation to be processed first on the first machine and a single operation to be then processed on the second machine. A coupled-operation contains two operations separated by an exact time delay. The single operation can start on the second machine only when the coupled-operation on the first machine is completed. We prove the NP-completeness of two restricted versions of the general problem, whereas we also exhibit several other well solvable cases. [ABSTRACT FROM AUTHOR]

Robust multi-stage linear optimization is hard computationally and only small problems can be solved exactly. Hence, robust multi-stage linear problems are typically addressed heuristically through decision rules, which provide upper bounds for the optimal solution costs of the problems. We investigate in this paper lower bounds inspired by the perfect information relaxation used in stochastic programming. Specifically, we study the uncapacitated robust lot-sizing problem, showing that different versions of the problem become tractable whenever the non-anticipativity constraints are relaxed. Hence, we can solve the resulting problem efficiently, obtaining a lower bound for the optimal solution cost of the original problem. We compare numerically the solution time and the quality of the new lower bound with the dual affine decision rules that have been proposed by Kuhn et al. (Math Program 130:177-209, 2011). [ABSTRACT FROM AUTHOR]

In this paper a class of combinatorial optimization problems is discussed. It is assumed that a feasible solution can be constructed in two stages. In the first stage the objective function costs are known while in the second stage they are uncertain and belong to an interval uncertainty set. In order to choose a solution, the minmax regret criterion is used. Some general properties of the problem are established and results for two particular problems, namely the shortest path and the selection problem, are shown. [ABSTRACT FROM AUTHOR]

This paper considers, in the single-machine scheduling context, the reactive and proactive problems arising when, due to unpredictable events between the time a baseline scheduled has been planned and the time the schedule must be implemented, the job durations may have increased so that the baseline schedule is no longer feasible. In the reactive case, the baseline schedule is known, the real job durations are known and we search for a schedule of the real instance that maximizes the number of jobs started at the same date in both schedules, this maximum being called the reactive gain. We show that, in the non-preemptive case, the corresponding decision problem is NP-complete in the strong sense while in the discrete preemptive case, it can be polynomially solved. In the proactive case, the real job durations are only known to belong to an uncertainty domain and we search for a baseline schedule that maximizes the worst reactive gain over the uncertainty domain. We show that the corresponding decision problem is NP-complete in the non-preemptive case while it is quite easy in the discrete preemptive case. [ABSTRACT FROM AUTHOR]

We consider the scheduling problems arising when several agents, each owning a set of nonpreemptive jobs, compete to perform their respective jobs on one shared processing resource. Each agent wants to minimize a certain cost function, which depends on the completion times of its jobs only. The cost functions we consider in this paper are maximum of regular functions (associated with each job), number of late jobs and total weighted completion time. The different combinations of the cost functions of each agent lead to various problems, whose computational complexity is analysed in this paper. In particular, we investigate the problem of finding schedules whose cost for each agent does not exceed a given bound for each agent. [ABSTRACT FROM AUTHOR]

This paper aims to analyze the main contributions of Marco Tucci, with whom we had the great pleasure of guest-editing this special issue of the Annals of Operations Research. Unfortunately, Marco passed away in December 2023. Therefore, this special issue is dedicated to Marco, and this note summarizes his main contributions. [ABSTRACT FROM AUTHOR]

In this paper, we study the single-item and the multi-item capacitated lot sizing problem in presence of inventory bounds (CLSP-IB). That is, in any period, both the quantity produced and the stock on hand are limited. For the single-item CLSP-IB with a stationary production capacity, time-dependent inventory bounds and concave costs, we show that the problem can be solved in time $$O(T^4)$$ by adapting a well-known algorithm in the literature. Restricting to non-speculative costs, we propose an $$O(T^3)$$ time dynamic programming algorithm. For the multi-item CLSP-IB, we consider the lot-sizing problem with item dedicated machines and a common capacitated storage space shared by all the items. We show that this problem is $$\text{ NP }$$ -hard in the strong sense even if all the cost parameters and capacities of the instance are stationary and identical for each item. [ABSTRACT FROM AUTHOR]

This paper addresses the problem of scheduling jobs on flow shops subject to constraints given by an undirected graph, in which each edge joins a pair of conflicting jobs that cannot be processed simultaneously on different machines. We first show that the problem of minimizing the maximum completion time (makespan) is NP-hard for several versions. Then, we present polynomial-time solvable cases. On the other hand, we propose heuristic approaches and lower bounds alongside with an experimental study. [ABSTRACT FROM AUTHOR]

This paper characterizes and enumerates the possible solution structures in nonlinear pricing problem when the number of buyer types is given. It is shown that the single-crossing property, which is a standard assumption in the literature, reduces the complexity of solving the problem dramatically. The number of possible solution structures is important when the pricing problem is solved under limited information. [ABSTRACT FROM AUTHOR]

In this paper we tackle an important point of combinatorial optimisation: that of complexity theory when dealing with the counting or enumeration of optimal solutions. Complexity theory has been initially designed for decision problems and evolved over the years, for instance, to tackle particular features in optimisation problems. It has also evolved, more or less recently, towards the complexity of counting and enumeration problems and several complexity classes, which we review in this paper, have emerged in the literature. This kind of problems makes sense, notably, in the case of multicriteria optimisation where the aim is often to enumerate the set of the so-called Pareto optima. In the second part of this paper we review the complexity of multicriteria scheduling problems in the light of the previous complexity results. [ABSTRACT FROM AUTHOR]

The research in evacuation planning has been very much motivated due to the rapidly increased number of disasters world-wide. It is the process of shifting maximum number of evacuees from the disastrous areas to the safe destinations as quickly and efficiently as possible. The contraflow model allows the arc reversals that increase the outbound road capacities. In continuous time setting, the dynamic contraflow sends the maximum flow as a flow rate from the sources to the sinks in every moment of time unit. In this paper, we elaborate the mathematical model for the continuous dynamic contraflow problem. Moreover, we present computationally efficient algorithms to solve the different dynamic contraflow problems in continuous time model, for example, maximum dynamic, earliest arrival, lex-maximum dynamic, earliest arrival transshipment and quickest transshipment contraflows on particulars networks. Here, we study the theoretical development of continuous contraflow approach for evacuation planning issues. The proposed newly presented algorithms with continuous contraflow reconfiguration approach increase the flow value for given time horizon and also decrease the evacuation time needed to transship the given flow value. Here most of the newly proposed methods make use of temporally repeated flows. [ABSTRACT FROM AUTHOR]

Given a finite set X and a collection Π=( R, R,..., R) of v binary relations defined on X and given a remoteness ρ, a relation R is said to be a central relation of Π with respect to ρ if it minimizes the remoteness ρ( Π, R) from Π. The remoteness ρ is based on the symmetric difference distance δ( R, R) between R and the binary relations R of Π (1≤ i≤ v), which measures the number of disagreements between R and R. Usually, the considered remoteness between Π and a relation R is the remoteness ρ( Π, R) given by the sum of the distances δ( R, R) over i, and thus measures the total number of disagreements between Π and R or, divided by v, provides the (arithmetical) mean number of disagreements between Π and R. The computation of a central relation with respect to ρ is often an NP-hard problem when the central relation is required to fulfill structural properties like transitivity. In this paper, we investigate other types of remoteness ρ, for instance the sum of the pth power of the δ( R, R)'s for any integer p, the maximum of the δ( R, R)'s, the minimum of the δ( R, R)'s, and different kinds of means of the δ( R, R)'s, or their weighted versions. We show that for many definitions of the remoteness, including the previous ones, the computation of a central relation with respect to ρ remains an NP-hard problem, even when the number v of relations is given, for any value of v greater than or equal to 1. [ABSTRACT FROM AUTHOR]

In this paper, we consider some scheduling problems on a single machine, where weighted or unweighted total tardiness has to be maximized in contrast to usual minimization problems. These problems are theoretically important and have also practical interpretations. For the total weighted tardiness maximization problem, we present an NP-hardness proof and a pseudo-polynomial solution algorithm. For the unweighted total tardiness maximization problem with release dates, NP-hardness is proven. Complexity results for some other classical objective functions (e.g., the number of tardy jobs, total completion time) and various additional constraints (e.g., deadlines, weights and/or release dates of jobs may be given) are presented as well. [ABSTRACT FROM AUTHOR]

In this paper, we survey some results, conjectures and open problems dealing with the combinatorial and algorithmic aspects of the linear ordering problem. This problem consists in finding a linear order which is at minimum distance from a (weighted or not) tournament. We show how it can be used to model an aggregation problem consisting of going from individual preferences defined on a set of candidates to a collective ranking of these candidates. [ABSTRACT FROM AUTHOR]

This paper is devoted to some selected topics relating Combinatorial Optimization and Hierarchical Classification. It is oriented toward extensions of the standard classification schemes (the hierarchies): pyramids, quasi-hierarchies, circular clustering, rigid clustering and others. Bijection theorems between these models and dissimilarity models allow to state some clustering problems as optimization problems. Within the galaxy of optimization we have especially discussed the following: NP-completeness results and search for polynomial instances; problems solved in a polynomial time (e.g. subdominant theory); design, analysis and applications of algorithms. In contrast with the orientation to “new” clustering problems, the last part discusses some standard algorithmic approaches. [ABSTRACT FROM AUTHOR]

Consider a set of n fixed length intervals and a set of n (larger) windows, in one-to-one correspondence with the intervals, and assume that each interval can be placed in any position within its window. If the position of each interval has been fixed, the intersection graph of such set of intervals is an interval graph. By varying the position of each interval in all possible ways, we get a family of interval graphs. In the paper we define some optimization problems related to the clique, stability, chromatic, clique cover numbers and cardinality of the minimum dominating set of the interval graphs in the family, mainly focussing on complexity aspects, bounds and solution algorithms. Some problems are proved to be NP-hard, others are solved in polynomial time on some particular classes of instances. Many practical applications can be reduced to these kind of problems, suggesting the use of Shiftable Intervals as a new interesting modeling framework. [ABSTRACT FROM AUTHOR]

The Modified Barrier Functions (MBF) have elements of both Classical Lagrangians (CL) and Classical Barrier Functions (CBF). The MBF methods find an unconstrained minimizer of some smooth barrier function in primal space and then update the Lagrange multipliers, while the barrier parameter either remains fixed or can be updated at each step. The numerical realization of the MBF method leads to the Newton MBF method, where the primal minimizer is found by using Newton's method. This minimizer is then used to update the Lagrange multipliers. In this paper, we examine the Newton MBF method for the Quadratic Programming (QP) problem. It will be shown that under standard second-order optimality conditions, there is a ball around the primal solution and a cut cone in the dual space such that for a set of Lagrange multipliers in this cut cone, the method converges quadratically to the primal minimizer from any point in the aforementioned ball, and continues to do so after each Lagrange multiplier update. The Lagrange multipliers remain within the cut cone and converge linearly to their optimal values. Any point in this ball will be called a "hot start". Starting at such a "hot start", at most O(ln ε-1) Newton steps are sufficient to perform the primal minimization which is necessary for the Lagrange multiplier update. Here, ε > 0 is the desired accuracy. Because of the linear convergence of the Lagrange multipliers, this means that only O(ln ε-1)O(ln ε-1) Newton steps are required to reach an ε-approximation to the solution from any "hot start". In order to reach the "hot start", one has to perform O(√m ln C) Newton steps, where m characterizes the size of the problem and C > 0 is the condition number of the QP problem. This condition number will be characterized explicitly in terms of key parameters of the QP problem, which in turn depend on the input data and the size of the problem. [ABSTRACT FROM AUTHOR]

We consider the problem of minimizing the makespan in open shop scheduling. The decision problem whether a given sequence in open shop scheduling is irreducible has already been considered, however, has not been solved yet. A sequence is an acyclic orientation of the Hamming graph K× K. Irreducible sequences in open shop are the local optimal elements. We present two variants of algorithms based on the specific properties of the H-comparability graph. The first is polynomial whereas the second is exponential. The irreducibility is co- NP. The stated properties argue whether it belongs to P. The complexity status of the considered decision problem is updated. [ABSTRACT FROM AUTHOR]

Given a collection Π of individual preferences defined on a same finite set of candidates, we consider the problem of aggregating them into a collective preference minimizing the number of disagreements with respect to Π and verifying some structural properties. We study the complexity of this problem when the individual preferences belong to any set containing linear orders and when the collective preference must verify different properties, for instance transitivity. We show that the considered aggregation problems are NP-hard for different types of collective preferences (including linear orders, acyclic relations, complete preorders, interval orders, semiorders, quasi-orders or weak orders), if the number of individual preferences is sufficiently large. [ABSTRACT FROM AUTHOR]

In this work, we consider a public facility allocation problem decided through a voting process under the majority rule. A location of the public facility is a majority rule winner if there is no other location in the network where more than half of the voters would have been closer to than the majority rule winner. We develop fast algorithms for interesting cases with nice combinatorial structures. We show that the computing problem and the decision problem in the general case, where the number of public facilities is more than one and is considered part of the input size, are all NP-hard. Finally, we discuss majority rule decision making for related models. [ABSTRACT FROM AUTHOR]

We consider the problem of scheduling n multi-operation jobs on a single machine. Each job comprises up to F operations that belong to different families. Changeovers of production from one family to another have associated set-up times. A job completes when all of its operations have been processed. This type of problem arises in the manufacture of food products. It combines the batching aspect of the well-known family scheduling models with an assembly element (where the job's operations are assembled to make the final product). Our analysis covers three classic optimality criteria: the maximum lateness, the weighted number of late jobs, and the sum of job completion times. We show that the problem of minimizing the maximum lateness is equivalent to its counterpart without assembly. This enables us to derive extensions of known complexity results and to indicate appropriate algorithms. The number of late jobs problem is shown to be binary NP-hard when there are two families, and unary NP-hard when there are an arbitrary number of families, even when all set-up times are identical. For a fixed number of families, we give a dynamic programming algorithm to minimize the weighted number of late jobs, which requires pseudo-polynomial running time. A similar algorithm solves the sum of completion times problem in polynomial time, under the additional assumption that the processing times of operations between families are agreeable. [ABSTRACT FROM AUTHOR]

Various sum of weighted completion time problems are compared. The constraints considered include release date, deadline, and continuous machine processing. Relations between the problems are developed by examining the computational complexity of transforming one problem class into another. These results give indications of the relative computational effort required to solve different problem classes. [ABSTRACT FROM AUTHOR]