Scheduling n jobs on one machine to minimize the maximum lateness with a minimum number of tardy jobs

This study considers the problem of scheduling n jobs, each job having an arrival time, a processing time and a due date, on a single machine with the dual objective of minimizing the maximum lateness subject to obtaining a minimum number of tardy jobs. A simple procedure is introduced to identify two critical jobs from which the maximum lateness is generated for a given sequence. The sequence of jobs between two critical jobs inclusive is called the critical path. On the basis of the critical path, Carlier's binary branching rule is adopted to minimize the maximum lateness. By fixing the position of these two critical jobs for maintaining the minimum maximum lateness, the sequence can further be reordered to reduce the number of tardy jobs. A branch and bound algorithm is presented for this purpose. The algorithm can solve problems with 50 jobs optimally within 5 seconds on a PC Pentium-100.     

Sequencing unreliable jobs on parallel machines

This paper addresses an allocation and sequencing problem motivated by an application in unsupervised automated manufacturing. There are n independent jobs to be processed by one of m machines or units during a finite unsupervised duration or shift. Each job is characterized by a certain success probability p _i , and a reward r _i which is obtained if the job is successfully carried out. When a job fails during processing, the processing unit is blocked, and the jobs subsequently scheduled on that machine are blocked until the end of the unsupervised period. The problem is to assign and sequence the jobs on the machines so that the expected total reward is maximized. This paper presents the following results for this problem and some extensions: (i) a polyhedral characterization for the single machine case, (ii) the proof that the problem is NP-hard even with 2 machines, (iii) approximation results for a round-robin heuristic, (iv) an effective upper bound. Extensive computational results show the effectiveness of the heuristic and the bound on a large sample of instances.     

The departure process of an N/G/1 queue

The departure process of an N/G/1 queue is investigated. The arrival process called an N process is a versatile point process and includes, for example, a Markov-modulated Poisson process, which is comprised of models of packetized voice and video traffic arrival processes. The first passage analysis yields LSTs of distributions of the interdeparture times. Emphasis is on the interdeparture times of an N/D/1 queue. Numerical examples show that correlation of interarrival times is likely to be preserved in interdeparture times, and that the departure of a voice packet multiplexer can be expected to be smoothed for a normal load. The result in this paper enables evaluation of the smoothing effect of burst traffic through nodes in Asynchronous Transfer Mode networks.     

Complex random sample scheduling and its application to an N/M/F/Fmax problem

“Complex Random Sample Scheduling(CRSS)” was proposed in this paper as an efficient heuristic method for solving any permutation scheduling problems. To show the effectiveness of the proposed CRSS, it was applied to an N-job, M-machine, permutation flowshop scheduling problem to minimize makespan, N/M/F/F_max. Numerical experiments made it clear that the proposed CRSS provides a schedule very close to the near-optimal schedule obtained by the existing promising heuristic methods such as taboo search and simulated annealing, within less computation time than these heuristic methods.     

Scheduling jobs on a single machine to maximize the total revenue of jobs

In today's hyper-competitive marketplace, many products like memory chips and computers are characterized by short life cycles and rapidly declining sales prices. This implies that the amount of revenue generated as a result of completing a product (job) may be decreasing as its completion time is delayed. In such an environment, there is a decided preference for the maximization of product revenues as an important objective. Based on the assumption that the decreasing rate of revenue is dependent on their product types, we intend to develop a searching algorithm and some heuristic algorithms to locate optimal and near-optimal job sequences, respectively, and thereby maximize total earned revenue.     

Fast solution of large N×N matrix equations in an MIMD–SIMD Hybrid System

In this paper, we propose a new high-speed computation algorithm for solving a large N×N matrix system using the MIMD–SIMD Hybrid System. The MIMD–SIMD Hybrid System (also denoted as Hybrid System in this paper) is a new parallel architecture consisting of a combination of Cluster of Workstations (COWs) and SIMD systems working concurrently to produce an optimal parallel computation. We first introduce our prototype SIMD system and our Hybrid System setup before presenting how it can be implemented to find the unknowns in a large N×N linear matrix equation system using the Gauss–LU algorithm. This algorithm basically performs the ‘Divide and Conquer’ approach by breaking down the large N×N matrix system into a manageable 32 × 32 matrix for fast computation.     

On axiomatic characterization of information improvement due to N revisions

A characterization theorem is proved for the information improvement due to N revisions by assuming a set of five axioms.     

Scheduling linear deteriorating jobs to minimize makespan with an availability constraint on a single machine

The scheduling problem with deteriorating jobs to minimize the makespan on a single machine where the facility has an availability constraint is studied in this paper. By a deteriorating job we mean that the processing time for the job is a function of its starting time. Even with the introduction of the availability to a facility, the linear deteriorating model can be solved using the 0-1 integer programming technique if the actual job processing time is proportional to the starting time.     

Scheduling jobs and maintenance activities subject to job-dependent machine deteriorations

This paper considers machine scheduling that integrates machine deterioration caused by jobs and, consequently, maintenance activities. The maintenance state of the machine is represented by a maintenance level which drops by a certain, possibly job-dependent amount while jobs are processed. A maintenance level of less than zero is associated with the machine’s breakdown and is therefore forbidden. Hence, maintenance activities that raise the maintenance level may become necessary and have to be scheduled additionally. We consider the objective to minimize the makespan throughout the paper. For the single machine case, we provide a linear-time approximation algorithm with worst-case a bound of 5/4, and comment on how an FPTAS from previous literature can be employed to apply to our problem. Due to problem similarity, these results also apply to the minimum subset sum problem, and the 5/4 linear-time approximation algorithm is an improvement over the 5/4 quadratic-time approximation algorithm of Güntzer and Jungnickel. For the general problem with multiple machines, we provide approximability results, two fast heuristics, an approximation algorithm with an instance-dependent approximation factor and a computational study evaluating the heuristics.     

On exact computational analysis of distributions of numbers in systems for M/G/1/N + 1 and GI/M/1/N + 1 queues using roots

In this paper, we obtain the distribution of number in system and other measures of efficiency for the M/G/1/N + 1 queuing system in terms of the roots of the associated characteristic equation (CE). Results for the GI/M/1/N + 1 queuing system have also been obtained from those of M/G/1/N + 1. Numerical results in the form of tables and graphs have been presented for a variety of service-(interarrival-) time distributions, e.g. Erlang (E_k), generalized Erlang (GE_k) and hyperexponential (HE_k).     

积累N次主动变换的传导知识挖掘

针对前N次可拓变换未引起与之相关的信息元发生传导变换,而N+1次主动变换才能引起与之相关的信息元发生传导变换的实际问题,运用可拓变换、传导效应等,并通过给出信息元某特征对于目标特征灵敏度的概念,深入挖掘此类可拓变换及其传导变换的传导知识。通过对某型导弹武器系统定型过程中的试验数据进行分析,表明该方法是对已有传导知识数据挖掘理论的完善和补充,使传导知识挖掘的理论更加丰富、全面。     

具有交互效应的多变量GM(1,$textbf{N}$)模型

针对一类具有交互效应的小样本系统建模问题,将相关因素序列的交叉项引入经典GM(1,N)模型的灰色作用量,构建交互效应GM(1,N)模型及其派生模型,以反映不同输入变量之间的交互效应对系统特征变量的影响,并通过实例验证交互效应GM(1,N)模型的有效性.结果表明:当相关因素序列的交互作用系数为零时,交互效应GM(1,N)模型退化为经典GM(1,N)模型;对于具有交互效应的系统建模问题,交互效应模型较经典模型具有更高的模拟和预测精度.     

Scheduling n jobs on one machine to minimize the maximum tardiness with minimum number

The “one machine” scheduling problem is considered with the dual objective of minimizing the maximum tardiness with minimum number of tardy jobs. A simple procedure is introduced to obtain an optimal schedule with minimum “maximum tardiness” when the set of nontardy jobs is specified. A branch and bound algorithm is presented to obtain the optimal schedule that minimizes the maximum tardiness with minimum number of tardy jobs. A condition is also given to identify an initial set of early jobs. Several theorems are formulated and proved in order to justify the elimination of much branching.     

Scheduling jobs with equal processing times subject to machine eligibility constraints

We consider the problem of nonpreemptively scheduling a set of n jobs with equal processing times on m parallel machines so as to minimize the makespan. Each job has a prespecified set of machines on which it can be processed, called its eligible set. We consider the most general case of machine eligibility constraints as well as special cases of nested and inclusive eligible sets. Both online and offline models are considered. For offline problems we develop optimal algorithms that run in polynomial time, while for online problems we focus on the development of optimal algorithms of a new and more elaborate structure as well as approximation algorithms with good competitive ratios.     

最小化误工工件个数的两代理单机排序问题

针对研究了两代理情形下的单机排序问题,考虑两类问题：一是在误工工件个数不超过一个给定值的情况下使得总误工最小,另一个是代理[A]的工件加工时间和权重满足反一致关系时,在误工工件个数不超过一个给定值的情况下使得总加权完工时间之和最小。对于这两类问题采用动态规划方法分别给出最优性质和相应的拟多项式时间算法。     

Scheduling resumable simple linear deteriorating jobs on a single machine with an availability constraint to minimize makespan

We consider a single-machine scheduling problem in which the processing time of each job is a simple linear deteriorating function of its waiting time. The machine is subject to an availability constraint. Jobs interrupted by machine unavailability can resume their processing. The objective is to minimize the makespan. We first show that the problem can be solved optimally by 0–1 integer programming. We then prove that the problem is NP-hard in the ordinary sense and there exists a fully polynomial time approximation scheme for it.     

Computational analysis of machine repair problem with unreliable multi-repairmen

This paper considers a multi-repairmen problem comprising of M operating machines with W warm standbys (spares). Both operating and warm standby machines are subject to failures. With a coverage probability c, a failed unit is immediately detected and attended by one of R repairmen if available. If the failed unit is not detected with probability 1−c, the system enters an unsafe state and must be cleared by a reboot action. The repairmen are also subject to failures which result in service (repair) interruptions. The failed repairman resumes service after a random period of time. In addition, the repair rate depends on number of failed machines. The entire system is modeled as a finite-state Markov chain and its steady state distribution is obtained by a recursive matrix approach. The major performance measures are evaluated based on this distribution. Under a cost structure, we propose to use the Quasi-Newton method and probabilistic global search Lausanne method to search for the global optimal system parameters. Numerical examples are presented to demonstrate the effectiveness of our approach in solving a highly complex manufacturing system subject to multiple uncertainties.     

Maximising profits for an EPQ model with unreliable machine and rework of random defective items

This article deals with an economic production quantity (EPQ) model in an imperfect production system. The production system may undergo in ‘out-of-control’ state from ‘in-control’ state, after a certain time that follows a probability density function. The density function varies with reliability of the machinery system that may be controlled by new technologies, investing more costs. The defective items produced in ‘out-of-control’ state are reworked at a cost just after the regular production time. Occurrence of the ‘out-of-control’ state during or after regular production-run time is analysed and also graphically illustrated separately. Finally, an expected profit function regarding the inventory cost, unit production cost and selling price is maximised analytically. Sensitivity analysis of the model with respect to key parameters of the system is carried out. Two numerical examples are considered to test the model and one of them is illustrated graphically.     

Parallel machine scheduling problem to minimize the earliness/tardiness costs with learning effect and deteriorating jobs

The focus of this work is to analyze parallel machine earliness/tardiness (ET) scheduling problem with simultaneous effects of learning and linear deterioration, sequence-dependent setups, and a common due-date for all jobs. By the effects of learning and linear deterioration, we mean that the processing time of a job is defined by an increasing function of its starting time and a decreasing function of the position in the sequence. We develop a mixed integer programming formulation for the problem and show that the optimal sequence is V-shaped: all jobs scheduled before the shortest jobs and all jobs scheduled after the shortest job are in a non-increasing and non-decreasing order of processing times, respectively. The developed model allows sequence-dependent setups and sequence-dependent early/tardy penalties. The illustrative example with 11 jobs for 2 machines and 3 machines shows that the model can easily provide the optimal solution, which is V-shaped, for problem.