Complexity of minimizing the total flow time with interval data and minmax regret criterion

We consider the minmax regret (robust) version of the problem of scheduling n jobs on a machine to minimize the total flow time, where the processing times of the jobs are uncertain and can take on any values from the corresponding intervals of uncertainty. We prove that the problem in NP-hard. For the case where all intervals of uncertainty have the same center, we show that the problem can be solved in O(nlogn) time if the number of jobs is even, and is NP-hard if the number of jobs is odd. We study structural properties of the problem and discuss some polynomially solvable cases.     

Complexity results for the linear time–cost tradeoff problem with multiple milestones and completely ordered jobs

We consider two linear project time–cost tradeoff problems with multiple milestones. Unless a milestone is completed on time, penalty costs for tardiness may be imposed. However, these penalty costs can be avoided by compressing the processing times of certain jobs that require additional resources or costs. Our model describes these penalty costs as the total weighted number of tardy milestone. The first problem tries to minimize the total weighted number of tardy milestones within the budget for total compression costs, while the second problem tries to minimize the total weighted number of tardy milestones plus total compression costs. We develop a linear programming formulation for the case with a fixed number of milestones. For the case with an arbitrary number of milestones, we show that under completely ordered jobs, the first problem is NP-hard in the ordinary sense while the second problem is polynomially solvable.     

The Proportional Colouring Problem: Optimizing Buffers in Wireless Mesh Networks

In this paper, we consider a new edge colouring problem motivated by wireless mesh networks optimization: the proportional edge colouring problem. Given a graph G with positive weights associated to its edges, we want to find a proper edge colouring which assigns to each edge at least a proportion (given by its weight) of all the colours. If such colouring exists, we want to find one using the minimum number of colours. We proved that deciding if a weighted graph admits a proportional edge colouring is polynomial while determining its proportional edge chromatic number is NP-hard. We also give a lower and an upper bound that can be polynomially computed. We finally characterize some graphs and weighted graphs for which we can determine the proportional edge chromatic number.     

Parallel machine scheduling problems with a single server

In this paper, we consider the problem of scheduling jobs on parallel machines with setup times. The setup has to be performed by a single server. The objective is to minimize the schedule length (makespan), as well as the forced idle time. The makespan problem is known to be NP-hard even for the case of two identical parallel machines. This paper presents a pseudopolynomial algorithm for the case of two machines when all setup times are equal to one. We also show that the more general problem with an arbitrary number of machines is unary NP-hard and analyze some list scheduling heuristics for this problem. The problem of minimizing the forced idle time is known to be unary NP-hard for the case of two machines and arbitrary setup and processing times. We prove unary NP-hardness of this problem even for the case of constant setup times. Moreover, some polynomially solvable cases are given.     

Stable rank boundary principle

Let K denote a compact subset of the complex plane . We present correct proof that the stable rank of A(K) is one. Hereby, A (K) is the algebra of all continuous functions on K which are analytic in the interior of K.

Let G denote a plane domain whose boundary consists of finitely many closed, nonintersecting Jordan curves. We show that for a fixed function of gεC( ), g≠0, the following assertions are equivalent:

Every unimodular element (f, g) is reducible to the principal component exp(C( )).

The zero set Z_g is polynomially convex, i.e., its complement Z_g is connected.

A due-date assignment problem with learning effect and deteriorating jobs

In this paper we consider a single-machine scheduling problem with the effects of learning and deterioration. In this model, job processing times are defined by functions of their starting times and positions in the sequence. The problem is to determine an optimal combination of the due-date and schedule so as to minimize the sum of earliness, tardiness and due-date. We show that the problem remains polynomially solvable under the proposed model.     

Single-machine scheduling with deteriorating functions for job processing times

In many realistic scheduling settings a job processed later consumes more time than when it is processed earlier – this phenomenon is known as scheduling with deteriorating jobs. In the literature on deteriorating job scheduling problems, majority of the research assumed that the actual job processing time of a job is a function of its starting time. In this paper we consider a new deterioration model where the actual job processing time of a job is a function of the processing times of the jobs already processed. We show that the single-machine scheduling problems to minimize the makespan and total completion time remain polynomially solvable under the proposed model. In addition, we prove that the problems to minimize the total weighted completion time, maximum lateness, and maximum tardiness are polynomially solvable under certain agreeable conditions.     

A 2-approximation algorithm for interval data minmax regret sequencing problems with the total flow time criterion

In this paper we discuss a minmax regret version of the single-machine scheduling problem with the total flow time criterion. Uncertain processing times are modeled by closed intervals. We show that if the deterministic problem is polynomially solvable, then its minmax regret version is approximable within 2.     

Single machine scheduling problem with controllable processing times and resource dependent release times

We consider two single machine scheduling problems with resource dependent release times and processing times, in which the release times and processing times are linearly decreasing functions of the amount of resources consumed. The objective is to minimize the total cost of makespan and resource consumption function that is composed of release time reduction and processing time reduction. In the first problem, the cost of reducing a unit release time for each job is common. We show that the problem can be solved in polynomial time. The second problem assumes different reduction costs of job release times. We show that the problem can be reduced polynomially from the partition problem and thus, is NP-complete.     

Sharp adaptation for inverse problems with random noise

 We consider a heteroscedastic sequence space setup with polynomially increasing variances of observations that allows to treat a number of inverse problems, in particular multivariate ones. We propose an adaptive estimator that attains simultaneously exact asymptotic minimax constants on every ellipsoid of functions within a wide scale (that includes ellipoids with polynomially and exponentially decreasing axes) and, at the same time, satisfies asymptotically exact oracle inequalities within any class of linear estimates having monotone non-increasing weights. The construction of the estimator is based on a properly penalized blockwise Stein's rule, with weakly geometically increasing blocks. As an application, we construct sharp adaptive estimators in the problems of deconvolution and tomography. Received: 19 January 2000 / Revised version: 30 April 2001 / Published online: 14 June 2002     

Single-machine scheduling with linear decreasing deterioration to minimize earliness penalties

We consider a single-machine scheduling problem with linear decreasing deterioration in which the due dates are determined by the equal slack (SLK) method. By the linear decreasing deterioration, we mean that the job’s processing time is a decreasing function of its starting time. The objective is to minimize the total weighted earliness penalty subject to no tardy jobs. We prove that two special cases of the problem remain polynomially solvable. The first case is the problem with equally weighted monotonous penalty objective function and the other case is the problem with weighted linear penalty objective function.     

Scheduling problems with position dependent job processing times: computational complexity results

In this paper, we analyse single machine scheduling problems with learning and aging effects to minimize one of the following objectives: the makespan with release dates, the maximum lateness and the number of late jobs. The phenomena of learning and aging are modeled by job processing times described by non-increasing (learning) or non-decreasing (aging) functions dependent on the number of previously processed jobs, i.e., a job position in a sequence. We prove that the considered problems are strongly NP-hard even if job processing times are described by simple linear functions dependent on a number of processed jobs. Additionally, we show a property of equivalence between problems with learning and aging models. We also prove that if the function describing decrease/increase of a job processing time is the same for each job then the problems with the considered objectives are polynomially solvable even if the function is arbitrary. Therefore, we determine the boundary between polynomially solvable and strongly NP-hard cases.     

On Bipartite and Multipartite Clique Problems

In this paper, we introduce the maximum edge biclique problem in bipartite graphs and the edge/node weighted multipartite clique problem in multipartite graphs. Our motivation for studying these problems came from abstractions of real manufacturing problems in the computer industry and from formal concept analysis. We show that the weighted version and four variants of the unweighted version of the biclique problem are NP-complete. For random bipartite graphs, we show that the size of the maximum balanced biclique is considerably smaller than the size of the maximum edge cardinality biclique, thus highlighting the difference between the two problems. For multipartite graphs, we consider three versions each for the edge and node weighted problems which differ in the structure of the multipartite clique (MPC) required. We show that all the edge weighted versions are NP-complete in general. We also provide a special case in which edge weighted versions are polynomially solvable.     

Minimizing the passengers’ traveling time in the stop location problem

In this paper we consider the location of stops along the edges of an already existing public transportation network. The positive effect of new stops is given by the better access of the passengers to the public transport network, while the passengers’ traveling time increases due to the additional stopping activities of the trains, which is a negative effect for the passengers. The problem has been treated in the literature where the most common model is to cover all demand points with a minimal number of new stops. In this paper, we follow this line and seek for a set of new stops covering all demand points but instead of minimizing the number of new stops we minimize the additional passengers’ traveling time due to the new stops. For computing this additional traveling time we do not only take the stopping times of the vehicles but also acceleration and deceleration of the vehicles into account. We show that the problem is NP-hard, but we are able to derive a finite candidate set and two tractable IP formulations. For linear networks we show that the problem is polynomially solvable. We also discuss the differences to the common models from literature showing that minimizing the number of new stops does not necessarily lead to a solution with minimal additional traveling times for the passengers. We finally provide a case study showing that our new model decreases the traveling times for the passengers while still achieving the minimal number of new stops.     

Single-machine scheduling problems with both deteriorating jobs and learning effects

In this paper we consider the single-machine scheduling problems with job-position-based and sum-of-processing-times based processing times. The real processing time of a job is a function of its position and the total processing time of the jobs that are in front of it in the sequence. The objective is to minimize the makespan, and to minimize the mean finish time. We prove that some special cases are polynomially solvable under some restrictions of the parameters. In addition, for some another special cases of minimization of the mean finish time and the makespan, we show that an optimal schedule is V-shaped with respect to job normal processing times. Then, we propose a heuristic based on the V-shaped property, and show through a computational experiment that it performs efficiently.     

Single machine common flow allowance scheduling with controllable processing times

In this paper, we consider single machine SLK due date assignment scheduling problem in which job processing times are controllable variables with linear costs. The objective is to determine the optimal sequence, the optimal common flow allowance and the optimal processing time compressions to minimize a total penalty function based on earliness, tardiness, common flow allowance and compressions. We solve the problem by formulating it as an assignment problem which is polynomially solvable. For some special cases, we present an O(n logn) algorithm to obtain the optimal solution respectively.     

Covering partially directed graphs with directed paths

We consider graphs which contain both directed and undirected edges (partially directed graphs). We show that the problem of covering the edges of such graphs with a minimum number of edge-disjoint directed paths respecting the orientations of the directed edges is polynomially solvable. We exhibit a good characterization for this problem in the form of a min-max theorem. We introduce a more general problem including weights on possible orientations of the undirected edges. We show that this more general weighted formulation is equivalent to the weighted bipartite b-factor problem. This implies the existence of a strongly polynomial algorithm for this weighted generalization of Euler's problem to partially directed graphs (compare this with the negative results for the mixed Chinese postman problem). We also provide a compact linear programming formulation for the weighted generalization that we propose.     

Scheduling jobs with release dates on parallel batch processing machines

In this paper we consider the problem of scheduling jobs with release dates on parallel unbounded batch processing machines to minimize the maximum lateness. We show that the case where the jobs have deadlines is strongly NP-hard. We develop a polynomial-time approximation scheme for the problem to minimize the maximum delivery completion time, which is equivalent to minimizing the maximum lateness from the optimization viewpoint.     

Single-machine common flow allowance scheduling with job-dependent aging effects and a deteriorating maintenance activity

We consider a single machine due date assignment scheduling problem with job-dependent aging effects and a deteriorating maintenance activity, where due dates are assigned using the SLK due date determination method. We need to make a decision on when to schedule the deteriorating maintenance activity, the optimal common flow allowance and the sequence of jobs to minimize total earliness, tardiness and common flow allowance cost. We show that the problem remains polynomially solvable under the proposed model.