Some single-machine scheduling problems with actual time and position dependent learning effects

In this paper we study some single-machine scheduling problems with learning effects where the actual processing time of a job serves as a function of the total actual processing times of the jobs already processed and of its scheduled position. We show by examples that the optimal schedules for the classical version of problems are not optimal under this actual time and position dependent learning effect model for the following objectives: makespan, sum of kth power of the completion times, total weighted completion times, maximum lateness and number of tardy jobs. But under certain conditions, we show that the shortest processing time (SPT) rule, the weighted shortest processing time (WSPT) rule, the earliest due date (EDD) rule and the modified Moore’s Algorithm can also construct an optimal schedule for the problem of minimizing these objective functions, respectively.     

Bicriteria scheduling for contiguous and non contiguous parallel tasks

We study the problem of scheduling on k identical machines a set of parallel tasks with release dates and deadlines in order to maximize simultaneously two criteria, namely the Size (number of scheduled tasks) and the Weight (sum of the weights of scheduled tasks). If no task requires more than half of the machines, we construct schedules that are simultaneously approximations for the Size and the Weight by combining two approximate schedules, one for each parameter. We obtain existence results and polynomial time bicriteria approximation algorithms in contiguous and non contiguous models.     

An improved lower bound for a bi-criteria scheduling problem

For the bi-criteria scheduling problem of minimizing the sum of completion times and the sum of weighted completion times, min-sum of weighted completion times, we prove that there exists no constant β>1 such that (1+1/γ,β)-approximate schedules can be found for any γ>0. This result confirms a recently published conjecture.     

Single machine scheduling with general time-dependent deterioration, position-dependent learning and past-sequence-dependent setup times

The paper deals with single machine scheduling problems with setup time considerations where the actual processing time of a job is not only a non-decreasing function of the total normal processing times of the jobs already processed, but also a non-increasing function of the job’s position in the sequence. The setup times are proportional to the length of the already processed jobs, i.e., the setup times are past-sequence-dependent (p-s-d). We consider the following objective functions: the makespan, the total completion time, the sum of the δth (δ ≥ 0) power of job completion times, the total weighted completion time and the maximum lateness. We show that the makespan minimization problem, the total completion time minimization problem and the sum of the δ th (δ ≥ 0) power of job completion times minimization problem can be solved by the smallest (normal) processing time first (SPT) rule, respectively. We also show that the total weighted completion time minimization problem and the maximum lateness minimization problem can be solved in polynomial time under certain conditions.     

Single machine scheduling with a general exponential learning effect

In this paper we consider the scheduling problem with a general exponential learning effect and past-sequence-dependent (p-s-d) setup times. By the general exponential learning effect, we mean that the processing time of a job is defined by an exponent function of the total weighted normal processing time of the already processed jobs and its position in a sequence, where the weight is a position-dependent weight. The setup times are proportional to the length of the already processed jobs. We consider the following objective functions: the makespan, the total completion time, the sum of the δ ? 0th power of completion times, the total weighted completion time and the maximum lateness. We show that the makespan minimization problem, the total completion time minimization problem and the sum of the quadratic job completion times minimization problem can be solved by the smallest (normal) processing time first (SPT) rule, respectively. We also show that the total weighted completion time minimization problem and the maximum lateness minimization problem can be solved in polynomial time under certain conditions.     

Ordered sets with small width and large jump number

The following result is proved in this note: For any positive integers w and t, if an ordered set P has jump number at least (t+1) ^w–1, then either the width of P is more than w, or P has a tower, i.e., a linear sum of pairs of noncomparable elements, of height more than t.     

Single machine scheduling with exponential sum-of-logarithm-processing-times based learning effect

In this paper we consider the single machine scheduling problems with exponential sum-of-logarithm-processing-times based learning effect. By the exponential sum-of-logarithm-processing-times based learning effect, we mean that the processing time of a job is defined by an exponent function of the sum of the logarithm of the processing times of the jobs already processed. We consider the following objective functions: the makespan, the total completion time, the sum of the quadratic job completion times, the total weighted completion time and the maximum lateness. We show that the makespan minimization problem, the total completion time minimization problem and the sum of the quadratic job completion times minimization problem can be solved by the smallest (normal) processing time first (SPT) rule, respectively. We also show that the total weighted completion time minimization problem and the maximum lateness minimization problem can be solved in polynomial time under certain conditions.     

Ordering the structural set of jobs,minimizing the total penalty

The problem of setting up a schedule minimizing the total penalty is solved. A job set is specified. There are no precedence conditions. Each job consists of elementary operations. Job interruptions are allowed. Interruptions of elementary operations are not allowed. The penalty for an operation of a job to be executed at instantt is. A schedule is evaluated by a penalty that is the sum of the penalties of all the elementary operations of all jobs in set. It is assumed that set is structural. The problem is to find the schedule with a start in a prescribed interval [ T₁,T₂] with the least penalty. Compatible structural schedules are introduced into consideration. The class of compatible structural schedules contains the solution of the problem. An algorithm solving the problem is proposed having complexity, in the worst case, whereK is the number of jobs in the set.Translated from Zapiski Nauchnykh Seminarov Leningradskogo Otdeleniya Matematicheskogo Instituta im. V. A. Steklova AN SSSR, Vol. 90, pp. 229–264, 1979.     

Single machine past-sequence-dependent setup times scheduling with general position-dependent and time-dependent learning effects

In this paper we consider the single machine past-sequence-dependent (p-s-d) setup times scheduling problems with general position-dependent and time-dependent learning effects. By the general position-dependent and time-dependent learning effects, we mean that the actual processing time of a job is not only a function of the total normal processing times of the jobs already processed, but also a function of the job’s scheduled position. The setup times are proportional to the length of the already processed jobs. We consider the following objective functions: the makespan, the total completion time, the sum of the θth (θ ? 0) power of job completion times, the total lateness, the total weighted completion time, the maximum lateness, the maximum tardiness and the number of tardy jobs. We show that the problems of makespan, the total completion time, the sum of the θth (θ ? 0) power of job completion times and the total lateness can be solved by the smallest (normal) processing time first (SPT) rule, respectively. We also show that the total weighted completion time minimization problem, the maximum lateness minimization problem, maximum tardiness minimization problem and the number of tardy jobs minimization problem can be solved in polynomial time under certain conditions.     

Sum Multicoloring of Graphs

Scheduling dependent jobs on multiple machines is modeled by the graph multicoloring problem. In this paper we consider the problem of minimizing the average completion time of all jobs. This is formalized as the sum multicoloring problem: Given a graph and the number of colors required by each vertex, find a multicoloring which minimizes the sum of the largest colors assigned to the vertices. It reduces to the known sum coloring problem when each vertex requires exactly one color.This paper reports a comprehensive study of the sum multicoloring problem, treating three models: with and without preemptions, as well as co-scheduling where jobs cannot start while others are running. We establish a linear relation between the approximability of the maximum independent set problem and the approximability of the sum multicoloring problem in all three models, via a link to the sum coloring problem. Thus, for classes of graphs for which the independent set problem is ρ-approximable, we obtain O(ρ)-approximations for preemptive and co-scheduling sum multicoloring and O(ρ log n)-approximation for nonpreemptive sum multicoloring. In addition, we give constant ratio approximations for a number of fundamental classes of graphs, including bipartite, line, bounded degree, and planar graphs.     

The counting complexity of a simple scheduling problem

Let T be a set of tasks. Each task has a non-negative processing time and a deadline. The problem of determining whether or not there is a schedule of the tasks in T such that a single machine can finish processing each of them before its deadline is polynomially solvable. We prove that counting the number of schedules satisfying this condition is #P-complete.     

Single-machine and two-machine flowshop scheduling with general learning functions

We show that the O(n log n) (where n is the number of jobs) shortest processing time (SPT) sequence is optimal for the single-machine makespan and total completion time minimization problems when learning is expressed as a function of the sum of the processing times of the already processed jobs. We then show that the two-machine flowshop makespan and total completion time minimization problems are solvable by the SPT sequencing rule when the job processing times are ordered and job-position-based learning is in effect. Finally, we show that when the more specialized proportional job processing times are in place, then our flowshop results apply also in the more general sum-of-job-processing-times-based learning environment.     

Transformation graph

The transformation graph G^-+- of a graph G is the graph with vertex set V(G)E(G), in which two vertices u and v are joined by an edge if one of the following conditions holds: (i) u,vV(G) and they are not adjacent in G, (ii) u,vE(G) and they are adjacent in G, (iii) one of u and v is in V(G) while the other is in E(G), and they are not incident in G. In this paper, for any graph G, we determine the connectivity and the independence number of G^-+-. Furthermore, for a graph G of order n4, we show that G^-+- is hamiltonian if and only if G is not isomorphic to any graph in {2K₁+K₂,K₁+K₃}{K_1,n-1,K_1,n-1+e,K_1,n-2+K₁}.     

A property of weighted graphs without induced cycles of nonpositive weights

It has been conjectured [B. Xu, On signed cycle domination in graphs, Discrete Math. 309 (4) (2009) 1007–1012] that if there is a mapping from the edge set of a 2-connected graph G to {−1,1} such that for each induced subgraph, that is a cycle, the sum of all numbers assigned to its edges by this mapping is positive, then the number of all those edges of G to which 1 is assigned, is more than the number of all other edges of G. This conjecture follows from the main result of this note: If a mapping assigns integers as weights to the edges of a 2-connected graphGsuch that for each edge, its weight is not more than 1 and for each cycle which is an induced subgraph ofG, the sum of all weights of its edges is positive, then the sum of all weights of the edges ofGalso is positive. A simple corollary of this result is the following: If?is a mapping from the edge set of a 2-connected graphGto a set of real numbers such that for each cycleCofG, ∑_e∈E(C)?(e)>0, then∑_e∈E(G)?(e)also is positive.     

Every 4-connected line graph of a quasi claw-free graph is hamiltonian connected

Let G be a graph. For u,vV(G) with dist_G(u,v)=2, denote J_G(u,v)={wN_G(u)∩N_G(v)|N_G(w)N_G(u)N_G(v){u,v}}. A graph G is called quasi claw-free if J_G(u,v)≠ for any u,vV(G) with dist_G(u,v)=2. In 1986, Thomassen conjectured that every 4-connected line graph is hamiltonian. In this paper we show that every 4-connected line graph of a quasi claw-free graph is hamiltonian connected.     

基于重新排序时间错位限制下的最小化总完工时间的平行分批排序（英文）

In the rescheduling on a single machine, a set of the original jobs has already been scheduled, in order to make a given objective function is optimal. The decision maker needs to insert the new jobs into the existing schedule without excessively disrupting it. A batching machine is a machine that can handle up to some jobs simultaneously. In this paper,we consider the total completion time under a limit on the sequence disruptions for parallel batching based on rescheduling. For the parallel batching problem based on rescheduling, we research the properties of feasible schedules and optimal schedules on the total completion time under a limit on the maximum time disruptions or total time disruptions, in which the jobs are sequenced in SPT order, and give out the pseudo-polynomial time algorithms on the number of jobs and the processing time of jobs by applying the dynamic programming method.     

Semiconductor Equations for variable Mobilities Based on Boltzmann Statistics or Fermi-Dirac Statistics

The first aim of this paper is to characterize those limit spaces (X, τ) which can be valuated, i.e. for which a set E of valuations exists such that for each x ∈ X, τ(x) equals the set of filters on X which converge to x relative to E. It is shown further that a separated pretopological space is a URYSOHN -space iff it can be valuated by a set of subadditive valuations. In the second part of the paper a completion is constructed for the separated subadditively valuated limit spaces which can be considered as a generalization of the usual completion of a uniform space.     

Single machine past-sequence-dependent delivery times scheduling with general position-dependent and time-dependent learning effects

This paper studies the single machine past-sequence-dependent (p-s-d) delivery times scheduling with general position-dependent and time-dependent learning effects. By the general position-dependent and time-dependent learning effects we mean that the actual processing time of a job is not only a function of the total normal processing times of the jobs already processed, but also a function of the job’s scheduled position. We consider the following objective functions: the makespan, the total completion time, the sum of the θ$\theta$th (θ?0$\theta ?0$) power of job completion times, the total lateness, the total weighted completion time, the maximum lateness, the maximum tardiness and the number of tardy jobs. We show that the problems of minimization of the makespan, the total completion time, the sum of the θ$\theta$th (θ?0$\theta ?0$) power of job completion times and the total lateness can be solved by the smallest (normal) processing time first (SPT) rule, respectively. We also show that the total weighted completion time minimization problem, the discounted total weighted completion time minimization problem, the maximum lateness minimization problem, the maximum tardiness minimization problem and the total tardiness minimization problem can be solved in polynomial time under certain conditions.     

Single machine group scheduling with ordered criteria

The single machine group scheduling problem is considered. Jobs are classified into several groups on the basis of group technology, i.e. jobs of the same group have to be processed jointly. A machine set-up time independent of the group sequence is needed between each two consecutive groups. A schedule specifies the sequence of groups and the sequence of jobs in each group. The quality of a schedule is measured by the criteriaF ₁, ...,F _m ordered by their relative importance. The objective is to minimize the least important criterionF _m subject to the schedule being optimal with respect to the more important criterionF _m–1 which is minimized on the set of schedules minimizing criterionF _m–2 and so on. The most important criterion isF ₁, which is minimized on the set of all feasible schedules. An approach to solve this multicriterion problem in polynomial time is presented if functionsF ₁, ...,F _m have special properties. The total weighted completion time and the total weighted exponential time are the examples of functionsF ₁, ...,F _m–1 and the maximum cost is an example of functionF _m for which our approach can be applied.The research of the authors was partially supported by a KBN Grant No. 3 P 406 003 05, the Fundamental Research Fund of Belarus, Project N 60-242, and the Deutsche Forschungsgemeinschaft, Project Schema, respectively. The paper was completed while the first author was visiting the University of Melbourne.