Adding machine and calculating machine

In 1642 the French mathematician Blaise Pascal(1623-1662)invented a machine that could add and sub-tract.It had wheels that each had 1 to 10 marked off alongits circumference.When the wheel at the right,represen-ting units,made one complete circle,it engaged the wheelto its left,represents tens,and moved it forward one     

Single machine stochastic JIT scheduling problem subject to machine breakdowns

In this paper we research the single machine stochastic JIT scheduling problem subject to the machine breakdowns for preemptive-resume and preemptive-repeat.The objective function of the problem is the sum of squared deviations of the job-expected completion times from the due date.For preemptive-resume,we show that the optimal sequence of the SSDE problem is V-shaped with respect to expected processing times.And a dynamic programming algorithm with the pseudopolynomial time complexity is given.We discuss the difference between the SSDE problem and the ESSD problem and show that the optimal solution of the SSDE problem is a good approximate optimal solution of the ESSD problem,and the optimal solution of the SSDE problem is an optimal solution of the ESSD problem under some conditions.For preemptive-repeat,the stochastic JIT scheduling problem has not been solved since the variances of the completion times cannot be computed.We replace the ESSD problem by the SSDE problem.We show that the optimal sequence of the SSDE problem is V-shaped with respect to the expected occupying times.And a dynamic programming algorithm with the pseudopolynomial time complexity is given.A new thought is advanced for the research of the preemptive-repeat stochastic JIT scheduling problem.     

What is a universal computing machine?

A computer is classically formalised as a universal Turing machine or a similar device. However over the years a lot of research has focused on the computational properties of dynamical systems other than Turing machines, such cellular automata, artificial neural networks, mirrors systems, etc.In this paper we propose a unifying formalism derived from a generalisation of Turing’s arguments. Then we review some of universal systems proposed in the literature and show that are particular case of this formalism. Finally, we review some of the attempts to understand the relation between dynamical and computational properties of a system.     

An e–E-insensitive support vector regression machine

According to the Statistical Learning Theory, the support vectors represent the most informative data points and compress the information contained in training set. However, a basic problem in the standard support vector machine is that when the data is noisy, there exists no guaranteed scheme in support vector machines’ formulation to dissuade the machine from learning noise. Therefore, the noise which is typically presents in financial time series data may be taken into account as support vectors. In turn, noisy support vectors are modeled into the estimated function. As such, the inclusion of noise in support vectors may lead to an over-fitting and in turn to a poor generalization. The standard support vector regression (SVR) is reformulated in this article in such a way that the large errors which correspond to noise are restricted by a new parameter \(E\) . The simulation and real world experiments indicate that the novel SVR machine meaningfully performs better than the standard SVR in terms of accuracy and precision especially where the data is noisy, but in expense of a longer computation time.     

Multiple machine continuous setup lotsizing with sequence-dependent setups

We address the short-term production planning and scheduling problem coming from the glass container industry. A furnace melts the glass that is distributed to a set of parallel molding machines. Both furnace and machine idleness are not allowed. The resulting multi-machine multi-item continuous setup lotsizing problem with a common resource has sequence-dependent setup times and costs. Production losses are penalized in the objective function since we deal with a capital intensive industry. We present two mixed integer programming formulations for this problem, which are reduced to a network flow type problem. The two formulations are improved by adding valid inequalities that lead to good lower bounds. We rely on a Lagrangian decomposition based heuristic for generating good feasible solutions. We report computational experiments for randomly generated instances and for real-life data on the aforementioned problem, as well as on a discrete lotsizing and scheduling version.     

Matching based very large-scale neighborhoods for?parallel machine scheduling

In this paper we study very large-scale neighborhoods for the minimum total weighted completion time problem on parallel machines, which is known to be strongly $\mathcal{NP}$ -hard. We develop two different ideas leading to very large-scale neighborhoods in which the best improving neighbor can be determined by calculating a weighted matching. The first neighborhood is introduced in a general fashion using combined operations of a basic neighborhood. Several examples for basic neighborhoods are given. The second approach is based on a partitioning of the job sets on the machines and a reassignment of them. In a computational study we evaluate the possibilities and the limitations of the presented very large-scale neighborhoods.     

Fuzzy extensions to Integer Programming models of cell-formation problems in machine scheduling

Cell formation has received much attention from academicians and practitioners because of its strategic importance to modern manufacturing practices. Existing research on cell formation problems using integer programming (IP) has achieved the target of solving problems that simultaneously optimise: (a) cell formation, (b) machine-cell allocation, and (c) part-machine allocation. This paper will present extensions of the IP model where part-machine assignment and cell formation are addressed simultaneously, and also a significant number of constraints together with an enhanced objective function are considered. The main study examines the integration of inter-cell movements of parts and machine set-up costs within the objective function, and also the combination of machine set-up costs associated with parts revisiting a cell when part machine operation sequence is taken into account. The latter feature incorporates a key set of constraints which identify the number of times a part travels back to a cell for a later machine operation. Due to two main drawbacks of IP modelling for cell formation, i.e. (a) only one objective function can be involved and (b) the decision maker is required to specify precisely goals and constraints, fuzzy elements like fuzzy constraints and fuzzy goals will be considered in the proposed model. Overall the paper will not only include an extended and enhanced integer programming model for assessing the performance of cell formation, but also perform a rigorous study of fuzzy integer programming and demonstrate the feasibility of achieving better and faster clustering results using fuzzy theory.     

Is wave propagation computable or can wave computers beat the turing machine?

According to the Church-Turing Thesis a number function is computableby the mathematically defined Turing machine if and only ifit is computable by a physical machine. In 1983 Pour-El andRichards defined a three-dimensional wave u(t,x) such that theamplitude u(0,x) at time 0 is computable and the amplitude u(1,x)at time 1 is continuous but not computable. Therefore, theremight be some kind of wave computer beating the Turing machine.By applying the framework of Type 2 Theory of Effectivity (TTE),in this paper we analyze computability of wave propagation.In particular, we prove that the wave propagator is computableon continuously differentiable waves, where one derivative islost, and on waves from Sobolev spaces. Finally, we explainwhy the Pour-El-Richards result probably does not help to designa wave computer which beats the Turing machine. 2000 Mathematical Subject Classification: 03D80, 03F60, 35L05,68Q05.     

Lagrangian domain reductions for the single machine earliness–tardiness problem with release dates

This paper presents new elimination rules for the single machine problem with general earliness and tardiness penalties subject to release dates. These rules, based on a Lagrangian decomposition, allow to drastically reduce the execution windows of the jobs. We measure the efficiency of these properties by integrating them in a branch-and-bound. Tests show that instances with up to 70 jobs without release dates, and up to 40 jobs with release dates, can be optimally solved within 1000 seconds.     

Scheduling jobs on a machine subject to stochastic breakdowns to minimize absolute early-tardy penalties

This article addresses the problem of scheduling n jobs with a common due date on a machine subject to stochastic breakdowns to minimize absolute early-tardy penalties.We investigate the problem under the conditions that the uptimes follow an exponential distribution,and the objective measure in detail is to minimize the expected sum of the absolute deviations of completion times from the common due date.We proceed to study in two versions (the downtime follows an exponential distribution or is a constant entailed for the repeat model job),one of which is the so-called preempt- resume version,the other of which is the preempt-repeat version.Three terms of work have been done.(i)Formulations and Preliminaries.A few of necessary definitions,relations and basic facts are established.In particular,the conclusion that the expectation of the absolute deviation of the completion time about a job with deterministic processing time t from a due date is a semi-V-shape function in t has been proved.(ii) Properties of Optimal Solutions.A few characteristics of optimal solutions are established.Most importantly,the conclusion that optimal solutions possess semi-V- shape property has been proved.(iii) Algorithm.Some computing problems on searching for optimal solutions are discussed.     

Minimizing weighted earliness–tardiness on a single machine with a common due date using quadratic models

In this paper we study the problem of minimizing weighted earliness and tardiness on a single machine when all the jobs share the same due date. We propose two quadratic integer programming models for solving both cases of unrestricted and restricted due dates, an auxiliary model based on unconstrained quadratic integer programming and an algorithmic scheme for solving each instance, according to its size and characteristics, in the most efficient way. The scheme is tested on a set of well-known test problems. By combining the solutions of the three models we prove the optimality of the solutions obtained for most of the problems. For large instances, although optimality cannot be proved, we actually obtain optimal solutions for all the tested instances.     

Parallel machine covering with limited number of preemptions简

In this paper,we investigate the i-preemptive scheduling on parallel machines to maximize the minimum machine completion time,i.e.,machine covering problem with limited number of preemptions. It is aimed to obtain the worst case ratio of the objective value of the optimal schedule with unlimited preemptions and that of the schedule allowed to be preempted at most i times. For the m identical machines case,we show the worst case ratio is 2m.i.1 m,and we present a polynomial time algorithm which can guarantee the ratio for any 0 ≤ i ≤ m. 1. For the i-preemptive scheduling on two uniform machines case,we only need to consider the cases of i = 0 and i = 1. For both cases,we present two linear time algorithms and obtain the worst case ratios with respect to s,i.e.,the ratio of the speeds of two machines.     

Comments on “Flow shop and open shop scheduling with a critical machine and two operations per job”

A recent paper [Eur. J. Operat. Res. 127 (2000) 120] addresses a flow-shop scheduling problem, where (i) each of the n jobs is limited to at most two operations, and (ii) one of these operations is common for all the jobs. The paper introduces a polynomial time solution algorithm for the problem, which appears to be surprisingly simple. Our short note contains several comments related to the correctness of the algorithm, to its complexity, to the proof of optimality and to a possible extension.     

A branch and bound algorithm for scheduling jobs with controllable processing times on a single machine to meet due dates

In most deterministic scheduling problems, job-processing times are regarded as constant and known in advance. However, in many realistic environments, job-processing times can be controlled by the allocation of a common resource to jobs. In this paper, we consider the problem of scheduling jobs with arbitrary release dates and due dates on a single machine, where job-processing times are controllable and are modeled by a non-linear convex resource consumption function. The objective is to determine simultaneously an optimal processing permutation as well as an optimal resource allocation, such that no job is completed later than its due date, and the total resource consumption is minimized. The problem is strongly NP\mathcal{NP}-hard. A branch and bound algorithm is presented to solve the problem. The computational experiments show that the algorithm can provide optimal solution for small-sized problems, and near-optimal solution for medium-sized problems in acceptable computing time.     

Calculatrices digitales. Du déchiffrage de formules logico-mathématiques par la machine même dans la conception du programme

Summary First of all (Chap. 1) the structure and organisation is described of a computer of the type of those already in use. A basic cyclic programme can then be explicitly defined, translating the definition of ? programme ? in terms of this machine (see 0.32), before specifying what the coded instructions are to be. Having chosen the latter, the universality of the machine is shown and some supplementary instructions useful later on are introduced. After passing from the usual programme notation to another (Chap. 2), the symbolism introduced in order to write the whole programme in formal language is justified, making use only of logical or algebraic concepts (Chap. 3). Furthermore, it is shown (Chap. 4) that this formalism can be made accessible to the machine by means of a teletyper, establishing once for all a one-one correspondence between symbols and integral numbers. The formulae expressing algebraically a computing programme may contain brackets (Chap 5) or polynomials in several variables put in the normal form (Chap. 6). In either case the machine itself, by means of a fixed programme independent of the particular nature of the formulae, can be made to perform the calculations necessary to produce the detailed coded instructions, from the formulae interpreting the numerical method envisaged. Finally (Chap. 8) the logical redundance of certain operations is printed out, and some arithmetisation procedures of propositional calculus is recalled.

---

Zusammenfassung Wir beschreiben zun?chst (Kap. 1) die Struktur und die Organisation einer Rechenmaschine vom Typ der bereits konstruierten. Wir k?nnen so ein zyklisches Grundprogramm explizit definieren (siehe 0.32), noch bevor wir spezifizieren, welches die kodifizierten Befehle sein müssen. Nachdem wir von der gew?hnlichen Bezeichnung der Programme zu einer anderen Bezeichnung (Kap. 2) übergegangen sind, rechtfertigen wir den eingeführten Symbolismus durch die M?glichkeit, jedes Programm in dieser formalen Sprache schreiben zu k?nnen, unter blosser Zuhilfenahme logischer oder algebraischer Bezeichnungen (Kap. 3). Weiterhin beweisen wir (Kap. 4), dass man diesen Formalismus der Rechenmaschine zug?nglich machen kann mit Hilfe eines Fernschreibers, indem wir ein für alle Mal eine eineindeutige Zuordnung zwischen Symbolen und ganzen Zahlen festlegen. Die Formeln, die ein Rechenprogramm in algebraischer Weise übersetzen, k?nnen Klammern enthalten (Kap. 5) oder Polynome in mehreren Variablen in der normalen Form. (Kap. 6). In beiden F?llen k?nnen wir durch die Rechenmaschine selbst, dank einem festen Programm, das von der speziellen Natur der Formeln (Kap. 7) unabh?ngig ist. die für die Herstellung der endgültigen kodifizierten Befehle auf Grund der Formeln notwendigen Rechnungen, ausführen lassen, die die ins Auge gefasste numerische Methode darstellen. Schliesslich (Kap. 8) haben wir die logische Entbehrlichkeit gewisser Operationen hervorgehoben und Verfahren zu Arithmetisierung des Aussagenkalküls in Erinnerung gerufen.

---

Riassunto Vengono descritte, in primo luogo (Cap. 1), la struttura e l'organizzazione d'una calcolatrice numerica del tipo di quelle già in servizio. Riesce così possibile definire esplicitamente un programma ciclico fondamentale che traduce meccanicamente per mezzo di tale macchina ciò che si intende per ? programma ? (vedi 0.32) prima ancora di dovere specificare quali siano le istruzioni codificate. Fatta poi quest'ultima scelta, viene dimostrata l'universalità della calcolatrice in questione e vengono aggiunte alcune nuove istruzioni che si riveleranno utili in seguito. Dalla notazione usuale per i programmi si passa ad un'altra notazione (Cap. 2) il cui simbolismo viene poi giustificato dalla possibilità di potere scrivere ogni programma in tale linguaggio formale ricorrendo unicamente a nozioni logiche o algebriche (Cap. 3). Inoltre viene dimostrato (Cap. 4) che questo formalismo può essere reso accessibile alla calcolatrice mediante una telescrivente, stabilendo una volta per tutte una corrispondenza biunivoca fra simboli e numeri intieri. Le formule che traducono algebricamente un programma di calcolo possono contenere parentesi (Cap. 5) oppure doi polinomi scritti in forma normale (Cap. 6). In ambo i casi la calcolatrice stessa, grazie ad un programma fisso, indipendente cioè dalla natura particolare delle formule (Cap. 7) è messa in grado di eseguire i calcoli necessari per produrre le istruzioni codificate finali procedendo dalle formule che interpretano il metodo numerico prescelto. Infine (Cap. 8) viene messa in evidenza la superfluità logica di certe operazioni e vengono applicati alcuni metodi di aritmetizzazione del calcolo delle proposizioni.

---

---

Ricercatore à l'Istituto Naz. per le Applicazioni del Calcolo. Thèse présentée à l'Ecole Polytechnique Fédérale, Zurich, pour l'obtention du grade de Docteur ès Sciences mathématiques. Rapporteur: Prof. Dr. E. Stiefel; corapporteur: Prof. Dr. P. Bernays (1952).     

A (2+ϵ)-approximation for precedence constrained single machine scheduling with release dates and total weighted completion time objective

We give a $(2+?)$-approximation algorithm for minimizing total weighted completion time on a single machine under release time and precedence constraints. This settles a recent conjecture on the approximability of this scheduling problem (Skutella, 2016).