The efficiency of bi-directionally patrolled machines when repairs are not always successful

This paper solves the problem of calculating the effective rate of production of a set of N machines, under the care of one operative, whose method of working is to patrol the machines, first in one direction until all the machines have been inspected and then in the opposite direction, and so on. The time taken to walk from one machine to the next, and inspect and service that machine is assumed to be a constant and is called the walking time. If a machine is stopped when the operative reaches it he spends an additional constant repair time putting it in order before proceeding to the next machine. The problem arises in the practical context of a textile winding process in which the operative is a robot which is not always successful in its attempt to carry out a repair. The numerical results are of value in monitoring this process.     

The efficiency of unidirectionally patrolled machines

This paper solves the problem of determining the efficiency of N (not identical) machines which are unidirectionally patrolled by one operative. Generally the machines will be equally spaced in a circular configuration so that the time to walk from one machine to the next will be a constant. However, the case of unequal spacing is just as easy to handle. It is assumed that breakdowns of machine j occur at random at average rate γ_j in running time, and that the time to repair this machine is a constant, c_j. This situation could arise from a mix of new and old machines or, in a textile context, in a situation where different types of yarn are being processed on different machines.     

The maintenance of bidirectionally patrolled machines

The problem considered is that of maintaining a set of N stations(machines, production facilities) which are set out along aline and numbered, say, from left to right, 1 to N. The stations(which are not necessarily identical) are maintained and repairedif necessary by one operative, who patrols them first from leftto right in the order 1 to N and then from right to left inthe order N - 1 down to 1 and so on. It is assumed that breakdowns at station i occur completelyat random in running time at an average rate 1,. The time forthe operative to travel from left to right from station i -1 to station i (or from right to left from station i to stationi - 1) and then to carry out routine maintenance at stationi is assumed to be a constant for this pair of stations, andis denoted by w,. If, on amval at station i, the operative findsthe station out of action, then an additional time r, is neededto repair station i. It is assumed that r, is a constant forstation i. It is{small tilde}alsoa ssumed that a repair attemptat station i is successful with probability a, (not n d l y1). Thus the model caters for a heterogeneous set of stations,unequally spaced. Important performance measures for the system include the averagetime to traverse the line of stations, along with the mean availability.For individual stations, the availability, the mean time spentwaiting for attention, and the mean length of the stopped periodare all important. It is shown how all of these quantities canbe computed.     

Cost Analysis of the <Emphasis Type="Italic">M/M/R</Emphasis> Machine Repair Problem with Spares and Two Modes of Failure

In this paper we deal with the machine repair problem consisting of M operating machines with S spare machines, and R repairmen where machines have two failure modes under steady-state conditions. Spares are considered to be either cold-standby, warm-standby or hot-standby. The two failure modes have equal probability of repair. Failure time of the machines and repair time of the repairmen are assumed to follow a negative exponential distribution. A cost model is developed in order to determine the optimal values of the number of repairmen and the number of spares simultaneously, while maintaining a minimum specified level of system availability. Numerical results are presented in which several system characteristics are evaluated for three types of standby under optimal operating conditions.     

The M/Ek/r machine interference model steady state equations and numerical solutions

This paper studies the machine interference problem in which the running times follow the negative exponential distribution, the repair times the Erlang distribution and the number of operatives is more than one. The steady state equations are derived and it is shown that unlike the case of the M/E_k/r ordinary queueing model, the solution cannot be taken in closed form. An efficient numerical procedure is developed instead, based on a decomposition principle. Tabulated results of the average number of machines running and the operative utilization for a range of the problem parameters are given, for the cases M/E₃/2 and M/E₃/3. A tentative conclusion for a closeness in performance between the models M/M/r and M/E_k/r is drawn.     

Cost analysis of the M/M/R machine repair problem with balking,reneging, and server breakdowns

We consider the machine repair problem in which failed machines balk (do not enter) with a constant probability (1 – b) and renege (leave the queue after entering) according to a negative exponential distribution. A group of identical automatic machines are maintained by R servers which themselves are subject to breakdowns. Failure and service times of the machines, and breakdown and repair times of the servers, are assumed to follow a negative exponential distribution. Each server is subject to breakdown even if no failed machines are in the system. This paper presents a matrix geometric method for deriving the steady-state probabilities, using which various system performance measures that can be obtained. A cost model is developed to determine the optimum number of servers. The minimum expected cost, the optimal number of servers, and various system performance measures are provided based on assumed numerical values given to the system parameters. Also the sensitivity analysis is investigated.     

Due-date assignment on uniform machines

The classical weighted minsum scheduling and due-date assignment problem (with earliness, tardiness and due-date costs) was shown to be polynomially solvable on a single machine, more than two decades ago. Later, it was shown to have a polynomial time solution in the case of identical processing time jobs and parallel identical machines. We extend the latter setting to parallel uniform machines. We show that the two-machine case is solved in constant time. Furthermore, the problem remains polynomially solvable for a given (fixed) number of machines.     

A polynomially solvable case of the three machine johnson problem

Under study is the classical NP-hard problem with three machines: N tasks must be fulfilled at three machines in minimum time. The processing time is given of each task at each machine. The processing sequences of all tasks are identical. It is impossible to process two tasks at one machine at the same time. We address the properties of this problem, find a new polynomially solvable case, and discuss a corresponding algorithm.     

Stochastically minimizing total flowtime in flowshops with no waiting space

The problem of scheduling n jobs in a two-machine flowshop with constant and known processing times is considered with the total flowtime performance measure. The machines are subject to random breakdowns and there is no waiting space between them. The problem is formulated and an expression for the completion time of the jobs is obtained in terms of the processing times and the breakdown elements. Provided that the counting processes associated with both machines have stationary increments property, a sequence that stochastically minimizes the performance criterion is established for the cases when only the first or the second machine suffers breakdowns.     

Optimal on-line flow time with resource augmentation

We study the problem of scheduling n jobs that arrive over time. We consider a non-preemptive setting on a single machine. The goal is to minimize the total flow time. We use extra resource competitive analysis: an optimal off-line algorithm which schedules jobs on a single machine is compared to a more powerful on-line algorithm that has ? machines. We design an algorithm of competitive ratio , where Δ is the maximum ratio between two job sizes, and provide a lower bound which shows that the algorithm is optimal up to a constant factor for any constant ?. The algorithm works for a hard version of the problem where the sizes of the smallest and the largest jobs are not known in advance, only Δ and n are known. This gives a trade-off between the resource augmentation and the competitive ratio.We also consider scheduling on parallel identical machines. In this case the optimal off-line algorithm has m machines and the on-line algorithm has ?m machines. We give a lower bound for this case. Next, we give lower bounds for algorithms using resource augmentation on the speed. Finally, we consider scheduling with hard deadlines, and scheduling so as to minimize the total completion time.     

A Numerical Approach to the Repairman Problem with Two Different Types of Machine

In this paper we deal with a heterogeneous machine-interference model under the assumption that the priority machines have pre-emptive priority over the ordinary ones. In each group, machines are characterized by exponentially distributed failure and repair times with different rates. The failed machines are served by a single repairman according to FIFO discipline. The aim of the paper is to give the steady-state operational characteristics of the system, such as operative utilization, expected busy-period length, machine availability, mean waiting times and average number of failed machines. Finally, numerical examples illustrate the problem in question.     

Scheduling jobs with release dates,equal processing times,and inclusive processing set restrictions

We consider the problem of scheduling a given set of n jobs with equal processing times on m parallel machines so as to minimize the makespan. Each job has a given release date and is compatible to only a subset of the machines. The machines are ordered and indexed in such a way that a higher-indexed machine can process all the jobs that a lower-indexed machine can process. We present a solution procedure to solve this problem in O(n²+mnlogn) time. We also extend our results to the tree-hierarchical processing sets case and the uniform machine case.     

Optimal streaming of a single job in a two-stage flow shop

Lot streaming is moving some portion of a process batch ahead to begin a downstream operation. The problem to be considered in this paper is the following: a single job consisting of U units is to be processed on two machines in the given order. Given a fixed number of possible transfer batches between the two machines, the problem is to find the timing and the size of the transfer batches (or, sublots) so as to optimize a given criterion. The schedules can be evaluated based on job completion, sublot completion, or item completion times. In the single job lot streaming problem, minimizing job completion time corresponds to minimizing the makespan, for which formulas for optimal sublot sizes are available. In this paper, the results for the sublot and item completion time models are presented.     

Vacation policies for machine repair problem with two type spares

This paper studies the machine repair problem consisting of M operating machines with two types of spare machines (S = S₁ + S₂), and R servers (repairmen) who leave for a vacation of random length when there are no failed machines queuing up for repair in the repair facility. At the end of the vacation the servers return and operate two vacation policies. First, the servers take vacations repeatedly until they find the repair facility has at least one waiting failed machine in the queue. Second, the servers do not take a vacation again and remain idle until the first arriving failed machine arrives, which starts a busy period in the repair facility. For both policies, the servers have two service rates for repair-slow and fast. The matrix geometric theory is used to find the steady-state probabilities of the number of failed machines in the system as well as the performance measures. Some special cases are given. A direct search algorithm is used to simultaneously determine the optimal values of the number of two types of spares and the number of servers while maintaining a minimum specified level of system availability.     

Sensitivity analysis of machine repair problems in manufacturing systems with service interruptions

This paper models a manufacturing system consisting of M operating machines and S spare machines under the supervision of a group of technicians in a repair facility. Machines fail according to a Poisson process, and the repair (service) process of a failed machine may require more than one phase. In each phase, service times are assumed to be exponentially distributed but may be interrupted when the repair facility encounters unpredictable breakdowns. Two models of manufacturing systems are considered. In the first model, technicians repair failed machines at different rates in each phase. In the second model, a two-phase service system with differing numbers of technicians is considered. Profit functions are developed for both models and optimized by a suitable allocation of the number of machines, spares, and technicians in the system. Finally, a sensitivity analysis (see Cao [X.R. Cao, Realization Probabilities: The Dynamics of Queuing Systems, Springer-Verlag: London, 1994; X.R. Cao, The relations among potentials, perturbation analysis, and Markov decision processes, Discrete Event Dynam. Syst.: Theory Applicat. 8 (1998) 71–87]) is performed to provide an approach that quantifies the impact of changes in the parameters on the profit models.     

On the complexity of scheduling unrelated parallel machines with limited preemptions

We consider the problem of finding a minimum-length preemptive schedule for n jobs on m parallel machines. The problem is solvable in polynomial time, whether the machines are identical, uniform or unrelated. For identical or uniform machines, it is easy to obtain an optimal schedule in which the portion of a job that is assigned to a single machine is processed without interruption. We show that imposing this condition in the case of unrelated machines makes the problem NP-hard.     

Scheduling of nonresumable jobs and flexible maintenance activities on a single machine to minimize makespan

This study addresses a single machine scheduling problem with periodic maintenance, where the machine is assumed to be stopped periodically for maintenance for a constant time w during the scheduling period. Meanwhile, the maintenance period [u, v] is assumed to have been previously arranged and the time w is assumed not to exceed the available maintenance period [u, v] (i.e. w ? v − u). The time u(v) is the earliest (latest) time at which the machine starts (stops) its maintenance. The objective is to minimize the makespan. Two mixed binary integer programming (BIP) models are provided for deriving the optimal solution. Additionally, an efficient heuristic is proposed for finding the near-optimal solution for large-sized problems. Finally, computational results are provided to demonstrate the efficiency of the models and the effectiveness of the heuristics. The mixed BIP model can optimally solve up to 100-job instances, while the average percentage error of the heuristic is below 1%.     

Heuristic constructive algorithms for open shop scheduling to minimize mean flow time

In this paper, we consider the problem of scheduling n jobs on m machines in an open shop environment so that the sum of completion times or mean flow time becomes minimal. For this strongly NP-hard problem, we develop and discuss different constructive heuristic algorithms. Extensive computational results are presented for problems with up to 50 jobs and 50 machines, respectively. The quality of the solutions is evaluated by a lower bound for the corresponding preemptive open shop problem and by an alternative estimate of mean flow time. We observe that the recommendation of an appropriate constructive algorithm strongly depends on the ratio n/m.     

Two meta-heuristics for parallel machine scheduling with job splitting to minimize total tardiness

Parallel machine scheduling is a popular research area due to its wide range of potential application areas. This paper focuses on the problem of scheduling n independent jobs to be processed on m identical parallel machines with the aim of minimizing the total tardiness of the jobs considering a job splitting property. It is assumed that a job can be split into sub-jobs and these sub-jobs can be processed independently on parallel machines. We present a mathematical model for this problem. The problem of total tardiness on identical parallel machines is NP-hard. Obtaining an optimal solution for this type of complex, large-sized problem in reasonable computational time by using an optimization solver is extremely difficult. We propose two meta-heuristics: Tabu search and simulated annealing. Computational results are compared on random generated problems with different sizes.     

The 〈G<Emphasis Type="Italic">/M/r/</Emphasis>FIFO〉 Machine-Interference Model with State-Dependent Speeds

This article treats a version of the multiple machine-interference problem with r operatives under FIFO repair discipline. The running times of machine i are supposed to be identically and arbitrarily distributed random variables with density function f _i (x), i = 1,…, n. The repair times of all machines are assumed to be identically and exponentially distributed random variables with mean 1/μ. The paper provides the main steady-state operational characteristics of the system when the running and repair speeds are dependent on the number of machines in working order.