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.     

Online scheduling with general machine cost functions

For most scheduling problems the set of machines is fixed initially and remains unchanged for the duration of the problem. Recently online scheduling problems have been investigated with the modification that initially the algorithm possesses no machines, but that at any point additional machines may be purchased. In all of these models the assumption has been made that each machine has unit cost. In this paper we consider the problem with general machine cost functions. Furthermore we also consider a more general version of the problem where the available machines have speed, the algorithm may purchase machines with speed 1 and machines with speed s. We define and analyze some algorithms for the solution of these problems and their special cases. Moreover we prove some lower bounds on the possible competitive ratios.     

问题Pm|rj,B|∑Cj的多项式时间近似算法

本文针对同型机分批排序问题Pm|rj,B|∑Cj进行了研究,给出了该问题在批容量B及机器台数m为常数情况下的多项式时间近似算法(以下简称PTAS);在B为常数时设计出了问题1|rj,B|∑WjCj的计算时间更少的PTAS．     

Lattice-valued fuzzy Turing machines: Computing power, universality and efficiency

In this paper we study fuzzy Turing machines with membership degrees in distributive lattices, which we called them lattice-valued fuzzy Turing machines. First we give several formulations of lattice-valued fuzzy Turing machines, including in particular deterministic and non-deterministic lattice-valued fuzzy Turing machines (l-DTMcs and l-NTMs). We then show that l-DTMcs and l-NTMs are not equivalent as the acceptors of fuzzy languages. This contrasts sharply with classical Turing machines. Second, we show that lattice-valued fuzzy Turing machines can recognize n-r.e. sets in the sense of Bedregal and Figueira, the super-computing power of fuzzy Turing machines is established in the lattice-setting. Third, we show that the truth-valued lattice being finite is a necessary and sufficient condition for the existence of a universal lattice-valued fuzzy Turing machine. For an infinite distributive lattice with a compact metric, we also show that a universal fuzzy Turing machine exists in an approximate sense. This means, for any prescribed accuracy, there is a universal machine that can simulate any lattice-valued fuzzy Turing machine on it with the given accuracy. Finally, we introduce the notions of lattice-valued fuzzy polynomial time-bounded computation (lP) and lattice-valued non-deterministic fuzzy polynomial time-bounded computation (lNP), and investigate their connections with P and NP. We claim that lattice-valued fuzzy Turing machines are more efficient than classical Turing machines.     

Online C-benevolent job scheduling on multiple machines

We consider scheduling a sequence of C-benevolent jobs on multiple homogeneous machines. For two machines, we propose a 2-competitive Cooperative Greedy algorithm and provide a lower bound of 2 for the competitive ratio of any deterministic online scheduling algorithms on two machines. For multiple machines, we propose a Pairing-m Greedy algorithm, which is deterministic 2-competitive for even number of machines and randomized \((2+2/{\hbox {m}})\)-competitive for odd number of machines. We provide a lower bound of 1.436 for the competitive ratio of any deterministic online scheduling algorithms on three machines, which is the best known lower bound for competitive ratios of deterministic scheduling algorithms on three machines.     

Machines Over the Reals and Non-Uniformity

We survey the research performed in the last few years on a specific topic: the power of real machines over binary inputs. This research attempts to characterize the classes of decision problems over a finite alphabet - say {0,1} - which can be decided by real machines working under several resource restrictions. Non-uniformity appears here in a natural way. However, since this is a technical concept which is not widely known, we summarize in Section 2 some of the intuitive notions, as well as a few basic theorems related to it. In Section 3 we do this for the subject of real machines and then, in Section 4 we present the state of the art of the surveyed topic. We devote Section 1 to introduce the main concepts of complexity theory. Proofs in this article are quite sketchy and are included more to convey intuitive ideas than to completely prove the claimed statements. Bibliographical references to the original literature are supplied for the latter purpose.     

Minimizing the number of machines for scheduling jobs with equal processing times

In this paper, we consider a parallel machine environment when all jobs have the same processing time and arbitrary release dates and deadlines of the jobs are given. We suppose that the available number of machines, which can be used simultaneously, may vary over time. The aim is to construct a feasible schedule in such a way that the maximal number of simultaneously used machines is minimal. We give a polynomial algorithm for this problem.     

Post’s Problem for ordinal register machines: An explicit approach

We provide a positive solution for Post’s Problem for ordinal register machines, and also prove that these machines and ordinal Turing machines compute precisely the same partial functions on ordinals. To do so, we construct ordinal register machine programs which compute the necessary functions. In addition, we show that any set of ordinals solving Post’s Problem must be unbounded in the writable ordinals.     

On-line scheduling of small open shops

We investigate the problem of on-line scheduling open shops of two and three machines with an objective of minimizing the schedule makespan. We first propose a 1.848-competitive permutation algorithm for the non-preemptive scheduling problem of two machines and show that no permutation algorithm can be better than 1.754-competitive. Secondly, we develop a (27/19)-competitive algorithm for the preemptive scheduling problem of three machines, which is most competitive.     

Online scheduling with machine cost and rejection

In this paper we define and investigate a new scheduling model. In this new model the number of machines is not fixed; the algorithm has to purchase the used machines, moreover the jobs can be rejected. We show that the simple combinations of the algorithms used in the area of scheduling with rejections and the area of scheduling with machine cost are not constant competitive. We present a 2.618-competitive algorithm called OPTCOPY.     

异时排序问题的算法复杂性

我们将限制某些工件不能同时处理的平行机排序问题称为异时排序问题．本文我们讨论工件加工时间相同、目标为总完工时间最小的异时排序问题．我们证明了当机器台数为2时,该问题等价于图上的最大匹配问题,因此存在组合强多项式时间算法;但量当机器台数为3或者多于3时,该问题是强NP困难的．     

On NP-Completeness for Linear Machines

We consider linear and scalar versions of the Blum–Shub–Smale model of computation over the reals. The permitted computing operations of linear machines are addition and multiplication by constants. The scalar machines can only multiply by constants. The size of an input is its dimension, and the cost of any instruction is one. For each of these structures we consider DNP and NP, the corresponding complexity classes with respect to digital nondeterminism and standard real nondeterminism, respectively. We give DNP- and NP-complete problems for linear and real scalar machines. On the other hand, we show that the NP-class restricted to scalar machines over the integers with equality-tests does not own a complete problem.     

A note on makespan minimization in two-stage flexible flow shops with uniform machines

We consider the two-stage flexible flow shop makespan minimization problem with uniform parallel machines. Soewandi and Elmaghraby [Soewandi, H., Elmaghraby, S., 2003. Sequencing on two-stage hybrid flowshops with uniform machines to minimize makespan. IIE Transaction 35, 467–477] developed a heuristic (S–E) and derived a machine speed-dependent worst-case ratio bound for it. We point out that this bound works well when the uniform machines have approximately equal speeds but is not indicative of the performance of the S–E heuristic when the machine speeds are in a wide range. Motivated by this observation, we propose an alternative tight machine-speed dependent worst-case bound for the S–E heuristic that works well when the machine speeds vary significantly. We then combine the two speed-dependent ratio bounds into a speed-independent bound. Our findings facilitate the narrowing of the gap between experimental performance and worst-case bound for the S–E heuristic.     

GENERALIZATION PERFORMANCE OF MULTI-CATEGORY KERNEL MACHINES -In Memory of Professor Sun Yongsheng

Support vector machines are originally designed for binary classification. How to effectively extend it for multi-class classification is still an on-going research issue. In this paper, we consider kernel machines which are natural extensions of multi-category support vector machines originally proposed by Crammer and Singer. Based on the algorithm stability, we obtain the generalization error bounds for the kernel machines proposed in the paper.     

On the resolution of the single product capacitated machine siting problem

The single product capacitated machine siting problem (SPCMSP) is an extension of the simple plant location problem, in which plant production depends on installing capacitated machines. In this paper we compare, both theoretically and computationally, three heuristic algorithms for the SPCMSP based upon Lagrangean relaxation and reduction tests of a mixed-integer formulation of the problem, which is NP-hard. We test the performance of the algorithms with examples involving up to 100 potential plants, 1000 customers and six potential machines per plant, which we obtain encouraging results.     

A tabu search algorithm for the Open Shop problem

In this paper we consider the minimum makespan Open Shop problem without preemption. It is well-known that the case with only two machines can be optimally solved in linear time, whereas the problem with an arbitrary number of machines is NP-hard in the strong sense. We propose a tabu search algorithm for the solution of the problem which uses simple list scheduling algorithms to build the starting solutions. The algorithm is extensively tested on randomly generated instances.     

Online scheduling of parallel jobs on two machines is 2-competitive

We consider online scheduling of parallel jobs on parallel machines. For the problem with two machines and the objective of minimizing the makespan, we show that 2 is a tight lower bound on the competitive ratio. For the problem with m machines, we derive lower bounds using an ILP formulation.     

Sevast'yanov's algorithm for the flow-shop scheduling problem

We consider the flow-shop scheduling problem. The objective is to schedule the jobs on the machines so that we minimize the time by which all jobs are completed. We studied and implemented different versions of the algorithm of Sevast'yanov based on linear programming to solve this problem. Using CPLEX, we did computational tests with random instances having up to 1000 jobs and 100 machines. If the size of the flow-shop scheduling problem is small or if the running time is not a critical factor, the Nawaz-Enscore-Ham approximation algorithm still performs better. But if the running time is an important factor, Sevast'yanov's algorithm can be a very good alternative especially in presence of very large scale instances with a relatively small number of machines.     

P|rj,on-line|∑Cj的一类在线算法与竞争比分析

本文研究平等机上的在线排序问题,优化目标是使总完工时间最小,算法SSPT是此问题的一类在线算法,论文引入一个拟时间表,此时间表具有SRPT时间表的部分性质,论文通过此辅助时间表证明了SSPT算法是(3-(1/m))-competitive的.     

A branch-and-price algorithm for scheduling parallel machines with sequence dependent setup times

We consider the problem of scheduling n independent jobs on m unrelated parallel machines with sequence-dependent setup times and availability dates for the machines and release dates for the jobs to minimize a regular additive cost function. In this work, we develop a new branch-and-price optimization algorithm for the solution of this general class of parallel machines scheduling problems. A new column generation accelerating method, termed “primal box”, and a specific branching variable selection rule that significantly reduces the number of explored nodes are proposed. The computational results show that the approach solves problems of large size to optimality within reasonable computational time.