Parallel machines scheduling to minimize job tardiness and machine deteriorating cost with deteriorating jobs

This paper studies the parallel machines bi-criteria scheduling problem (PMBSP) in a deteriorating system. Sequencing and scheduling problems (SSP) have seldom considered the two phenomena concurrently. This paper discusses the parallel machines scheduling problem with the effects of machine and job deterioration. By the machine deterioration effect, we mean that each machine deteriorates at a different rate. This deterioration is considered in terms of cost which depends on the production rate, the machine’s operating characteristics and the kind of work done by each machine. Moreover, job processing times are increasing functions of their starting times and follow a simple linear deterioration. The objective functions are minimizing total tardiness and machine deteriorating cost. The problem of total tardiness on identical parallel machines is NP-hard, thus the problem with machine deteriorating cost as an additional term is also NP-hard. We propose the LP-metric method to show the importance of our proposed multi-objective problem. A metaheuristic algorithm is developed to locate optimal or near optimal solutions based on a Tabu search mechanism. Numerical examples are presented to show the efficiency of this model.     

Fast approximation algorithms for bi-criteria scheduling with machine assignment costs

We consider parallel machine scheduling problems where the processing of the jobs on the machines involves two types of objectives. The first type is one of two classical objective functions in scheduling theory: either the total completion time or the makespan. The second type involves an actual cost associated with the processing of a specific job on a given machine; each job-machine combination may have a different cost. Two bi-criteria scheduling problems are considered: (1) minimize the maximum machine cost subject to the total completion time being at its minimum, and (2) minimize the total machine cost subject to the makespan being at its minimum. Since both problems are strongly NP-hard, we propose fast heuristics and establish their worst-case performance bounds.     

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.     

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.     

The effect of material flow and workload on the performance of machine location heuristics

Depending on the problem structure and routing strategies a machine location problem plays an important role in controlling the material flow of work-in-process in discrete product manufacturing environment. In this paper we investigate the effect of material flow and workload on the performance of heuristics for solving an important design problem for job routing and material flow in a manufacturing system. In this research we first develop a model for workload or traffic intensity between machines in a shop floor and then identify different structures of the problems, especially the data. This measure is then used to evaluate the effect of workload on efficiency of the heuristics to solve machine location problems. Some concluding remarks are made on to the effect of the workload or the traffic intensity of materials within the machine cell on the performance of some known heuristics. Conclusions are also made on the performance measures such as makespan, transporter utilization and machine utilization, depending on the problem and data structures.     

Multi-objective parallel machine scheduling problems by considering controllable processing times

This study examines parallel machine scheduling problems with controllable processing times. The processing time of each job can be between lower and upper bounds, and a cost is associated with the processing of a job on a machine. The processing time of a job can be decreased, which may lower the cycle time, although doing so would incur additional costs. This study develops two multi-objective mathematical models, which consist of two and three inconsistent objective functions, respectively. The first model minimizes the total manufacturing cost (TMC) and the total weighted tardiness (TWT) simultaneously, while the second uses makespan (C_max) as an additional objective function. In contrast to conventional mathematical models, efficient solutions are attained using the lexicographic weighted Tchebycheff method (LWT). Experimental results indicate that the LWT yields better-spread solutions and obtains more non-dominated solutions than its alternative, that is the weighted-sum method, which is a widely used yet promising approach to achieve multi-objective optimization. Results of this study also demonstrate that in purchasing machines, the variation in the fixed costs associated with the processing of jobs on machines is critical to reducing TWT. Moreover, using C_max as an additional objective function typically improves TWT and worsens TMC.     

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.     

New trends in machine scheduling

This review is concerned with new directions in deterministic machine scheduling theory. We study: resource constrained scheduling, scheduling tasks that require more than one machine at a time, scheduling with nonlinear speed-resource alloted functions, and scheduling in flexible manufacturing systems. The two features that distinguish the above problems are the use of resources in addition to the machines and new models for the processing of tasks. The study of these models was primarily motivated by their practical importance. In each case, we overview the existing results and present solution strategies for particularly chosen problems.     

Contribution of simulation to the optimization of maintenance strategies for a randomly failing production system

This paper compares two strategies for operating a production system composed of two machines working in parallel and a downstream inventory supplying an assembly line. The two machines, which are prone to random failures, undergo preventive and corrective maintenance operations. These operations with a random duration make the machines unavailable. Moreover, during regular subcontracting operations, one of these machines becomes unavailable to supply the downstream inventory. In the first strategy it is assumed that the periodicity of preventive maintenance operations and the production rate of each machine are independent. The second strategy suggests an interaction between the periods of unavailability and the production rates of the two machines in order to minimize production losses during these periods. A simulation model for each strategy is developed so as to be able to compare them and to simultaneously determine the timing of preventive maintenance on each machine considering the total average cost per time unit as the performance criterion. The second strategy is then considered, and a multi-criteria analysis is adopted to reach the best cost-availability compromise.     

A study on the characteristics in a symmetry Boltzmann machine composed of two Boltzmann machines

We propose a symmetry Boltzmann machine as a model of the brain which has the left hemispherium cerebri and the right one. A symmetry Boltzmann machine is composed of two Boltzmann machines. In case of two independent Boltzmann machines, we consider irreversible processes in a symmetry Boltzmann machine. We are interested in the entropy which depends on time and focus on its time change. First, we try to understand Boltzmann machines from the viewpoint of thermodynamics. Next, we consider an average of energy as an extensive variable which describes the relatively long time or macroscopic states of the independent systems. Then we derive its affinity. The result says that the temperature of each system determines the macroscopic equilibrium. On the other hand, in case of two correlative Boltzmann machines, we simulate a simple learning by using our model. The results say that a single unit's power spectrum density looks like the white noise in the forward learning, but it becomes the 1/f fluctuation in the reverse learning.     

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.     

Multi-agent single machine scheduling

We consider the scheduling problems arising when several agents, each owning a set of nonpreemptive jobs, compete to perform their respective jobs on one shared processing resource. Each agent wants to minimize a certain cost function, which depends on the completion times of its jobs only. The cost functions we consider in this paper are maximum of regular functions (associated with each job), number of late jobs and total weighted completion time. The different combinations of the cost functions of each agent lead to various problems, whose computational complexity is analysed in this paper. In particular, we investigate the problem of finding schedules whose cost for each agent does not exceed a given bound for each agent.     

Efficient Resource Allocation with Non-Concave Objective Functions

We consider resource allocation with separable objective functions defined over subranges of the integers. While it is well known that (the maximization version of) this problem can be solved efficiently if the objective functions are concave, the general problem of resource allocation with non-concave functions is difficult. In this article we show that for fairly well-shaped non-concave objective functions, the optimal solution can be computed efficiently. Our main enabling ingredient is an algorithm for aggregating two objective functions, where the cost depends on the complexity of the two involved functions. As a measure of complexity of a function, we use the number of subintervals that are convex or concave.     

考虑成本的最大延迟时间同类机调度问题

假定生产时机器成本是固定的,研究了一类考虑成本的同类机调度问题,调度的目标是在给定加工完所有作业的总预算的成本限制下最小化最大作业延迟时间。为该类问题构建了混合整数规划模型。通过设计相关规则在机器成本预算内来选择加工机器,以及对传统的LPT(最长加工时间优先)、ECT(最早完工时间优先)、EDD(最早工期优先)等算法进行改进,提出了一个启发式算法H,并理论证明了该算法在同型机和同类机下的最坏误差界。通过算例说明了算法的执行情况,同时也考虑了给定总预算不同的多种情形,采用大量随机数据实验验证了算法的有效性。     

Average performance of adaptive algorithms for programming co‐ordinate measuring machines under budget constraint

In this paper we develop two adaptive algorithms for programming co‐ordinate measuring machines assuming fixed sampling budget. Two different costs are considered: the travelling cost of the machine probe, and the sampling cost to read and store all measurements. Simulation is used to compare the average performance of the proposed algorithms under the assumption of Wiener measure on the space of all surface contours of the manufactured parts. Expected value of the probability of Type II error is the criterion that we use to characterize algorithms performance. Analysis shows that placing sample points according to the criterion of maximizing the expected gain demonstrates a substantial improvement in the average performance. Copyright © 1999 John Wiley & Sons, Ltd.     

Non-crossing quantile regression via doubly penalized kernel machine

Quantile regression provides a more complete statistical analysis of the stochastic relationships among random variables. Sometimes quantile regression functions estimated at different orders can cross each other. We propose a new non-crossing quantile regression method using doubly penalized kernel machine (DPKM) which uses heteroscedastic location-scale model as basic model and estimates both location and scale functions simultaneously by kernel machines. The DPKM provides the satisfying solution to estimating non-crossing quantile regression functions when multiple quantiles for high-dimensional data are needed. We also present the model selection method that employs cross validation techniques for choosing the parameters which affect the performance of the DPKM. One real example and two synthetic examples are provided to show the usefulness of the DPKM.     

Classification analysis for simulation of the duration of machine breakdowns

Machine failure can have a significant impact on the throughput of manufacturing systems, therefore accurate modelling of breakdowns in manufacturing simulation models is essential. Finite mixture distributions have been successfully used by Ford Motor Company to model machine breakdown durations in simulation models of engine assembly lines. These models can be very complex, with a large number of machines. To simplify the modelling we propose a method of grouping machines with similar distributions of breakdown durations, which we call the Arrows Classification Method, where the Two-Sample Cramér-von-Mises statistic is used to measure the similarity of two sets of the data. We evaluate the classification procedure by comparing the throughput of a simulation model when run with mixture models fitted to individual machine breakdown durations; mixture models fitted to group breakdown durations; and raw data. Details of the methods and results of the classification will be presented, and demonstrated using an example.     

Two machine open shop scheduling problem to minimize an arbitrary machine usage regular penalty function

The paper present a linear-time algorithm for solving the two machine open shop scheduling problem to minimize an arbitrary regular penalty function depending on the lengths of periods during which the machines are used. Both the preemptive and the nonpreemptive cases of the problem are considered.     

On the M/G/1 machine interference model with spares

In this paper a recursive method is developed to obtain the steady state probability distribution of the number of down machines at arbitrary time epoch of a machine interference problem with spares. Various system performance measures, such as average number of down machines, average waiting time for repair, average number of spare machines, average number of operating machines, machine availability and opdrator utilization, etc., have been obtained for a variety of repain time distributions.