Joint Optimization of Imperfect Preventive Maintenance and Production Scheduling for Single Machine Based on Game Theory Method

In this study,an optimization model of a single machine system integrating imperfect preventive maintenance planning and production scheduling based on game theory is proposed.The costs of the production department and the maintenance department are minimized,respectively.Two kinds of three-stage dynamic game models and a backward induction method are proposed to determine the preventive maintenance(PM)threshold.A lemma is presented to obtain the exact solution.A comprehensive numerical study is provided to illustrate the proposed maintenance model.The effectiveness is also validated by comparison with other two existed optimization models.

Rolling optimization algorithm based on collision window for single machine scheduling problem

Focusing on the single machine scheduling problem which minimizes the total completion time in the presence of dynamic job arrivals, a rolling optimization scheduling algorithm is proposed based on the analysis of the character and structure of scheduling. An optimal scheduling strategy in collision window is presented. Performance evaluation of this algorithm is given. Simulation indicates that the proposed algorithm is better than other common heuristic algorithms on both the total performance and stability.

Dominance property based tabu search for single machine scheduling problems with family setups

The problem of minimizing the maximum lateness on a single machine with family setups is considered.To solve the problem, dominance property is studied and then introduced into the tabu search（TS） algorithm.With the dominance property, most unpromising neighbors can be excluded from the neighborhood, which makes the search process always focus on the most promising areas of the solution space.The proposed algorithms are tested both on the randomly generated problems and on the real-life problems.Computational results show that the proposed TS algorithm outperforms the best existing algorithm and can solve the real-life problems in about 1.3 on average.

Dominance rules for single machine schedule with sequence dependent setup and due date

Some dominance rules are proposed for the problems of scheduling N jobs on a single machine with due dates, sequence dependent setup times and no preemption. Two algorithms based on Ragatz＇ s branch and bound scheme are developed including the dominance rules where the objective is to minimize the maximum tardiness or the total tardiness. Computational experiments demonstrate the effectiveness of the dominance rules.

Algorithms for single machine scheduling with availability constraints

It is a NP-hard problem to schedule a list of nonresumable jobs to the available intervals of an availability-constrained single machine to minimize the scheduling length. This paper transformed this scheduling problem into a variant of the variable-sized bin packing problem, put forward eight bin packing algorithms adapted from the classic one-dimensional bin packing problem and investigated their performances from both of the worst-case and the average-case scenarios. Analytical results show that the worst-case performance ratios of the algorithms are not less than 2. Experimental results for average cases show that the Best Fit and the Best Fit Decreasing algorithm outperform any others for independent and precedence-constrained jobs respectively.

A Genetic Algorithm for Single Machine Scheduling with Fuzzy Processing Time and Multiple Objectives

In this paper, by considering the fuzzy nature of the data in real-life problems, single machine scheduling problems with fuzzy processing time and multiple objectives are formulated and an efficient genetic algorithm which is suitable for solving these problems is proposed. As illustrative numerical examples, twenty jobs processing on a machine is considered. The feasibility and effectiveness of the proposed method have been demonstrated in the simulation.

A Class of Single Machine Scheduling Problems with Variable Processing Time

In this paper, single machine scheduling problems with variable processing time are raised. The criterions of the problem considered are minimizing scheduling length of all jobs, flow time and number of tardy jobs and so on. The complexity of the problem is determined. [WT5HZ]

A Note on Two-Agent Scheduling with Rejection on a Single Machine

In a recent paper,Feng et al.[5](Two-agent scheduling with rejection on a single machine.Appl.Math.Model.39(2015)1183-1193)studied some two-agent scheduling problems with rejection on a single machine.The authors showed that all problems are NP-hard and then provided four dynamic programming algorithms.Unfortunately,we observe that some mistakes are contained in the two dynamic programming algorithms.In this note,we first show by a counter-example that the above two algorithms are incorrect.Furthermore,we also provide two new dynamic programming algorithms to solve the same problems.

Single Machine Scheduling Problems with General Learning Effect

In a learning effect environment, the machine improves continuously as a result of repeating the same or similar jobs, hence the later a given job is scheduled in the sequence, the shorter its processing time is. In this paper, we consider a new general learning effect, i.e. Dejong＇s learning effect. Using this Dejong＇s learning effect polynomial solutions for the single machine makespan minimization problem, total flow time minimization problem and two classes of single machine multi-criteria problems are obtained.

Strong NP-Hardness of Single Machine Scheduling Problems with Variable Processing Time

In this paper, single machine scheduling problems with variable processing time is discussed according to published instances of management engineering. Processing time of a job is the product of a “coefficient' of the job on position i and a “normal' processing time of the job. The criteria considered is to minimize scheduled length of all jobs. A lemma is proposed and proved. In no deadline constrained condition, the problem belongs to polynomial time algorithm. It is proved by using 3 partition that if the problem is deadline constrained, its complexity is strong NP hard. Finally, a conjuncture is proposed that is to be proved.

Algorithms for Multicriteria Scheduling Problems to Minimize Maximum Late Work, Tardy, and Early

This study examines the multicriteria scheduling problem on a single machine to minimize three criteria: the maximum cost function, denoted by maximum late work (Vmax), maximum tardy job, denoted by (Tmax), and maximum earliness (Emax). We propose several algorithms based on types of objectives function to be optimized when dealing with simultaneous minimization problems with and without weight and hierarchical minimization problems. The proposed Algorithm (3) is to find the set of efficient solutions for 1//F (Vmax, Tmax, Emax) and 1//(Vmax + Tmax + Emax). The Local Search Heuristic Methods (Descent Method (DM), Simulated Annealing (SA), Genetic Algorithm (GA), and the Tree Type Heuristics Method (TTHM) are applied to solve all suggested problems. Finally, the experimental results of Algorithm (3) are compared with the results of the Branch and Bound (BAB) method for optimal and Pareto optimal solutions for smaller instance sizes and compared to the Local Search Heuristic Methods for large instance sizes. These results ensure the efficiency of Algorithm (3) in a reasonable time.

A multiple-criterion model for machine scheduling with constant deteriorating jobs

We consider a scheduling problem involving a single processor utilized by two customers with constant deteriorating jobs, i.e., jobs whose processing times are an increasing function of their starting times. Traditionally, such scenarios are modeled by assuming that each customer has the same criterion. In practice, this assumption may not hold. Instead of using a single criterion, we examine the implications of minimizing an aggregate scheduling objective function in which jobs belonging to different customers are evaluated with their individual criteria. We examine three basic scheduling criteria： minimizing makespan, minimizing maximum lateness, and minimizing total weighted completion time. We demonstrate all the scheduling problems considered are polynomially solvable.

Examining the effect of adverse geological conditions on jamming of a single shielded TBM in Uluabat tunnel using numerical modeling

Severe shield jamming events have been reported during excavation of Uluabat tunnel through adverse geological conditions, which resulted in several stoppages at advancing a single shielded tunnel boring machine(TBM). To study the jamming mechanism, three-dimensional(3D) simulation of the machine and surrounding ground was implemented using the finite difference code FLAC3D. Numerical analyses were performed for three sections along the tunnel with a higher risk for entrapment due to the combination of overburden and geological conditions. The computational results including longitudinal displacement contours and ground pressure profiles around the shield allow a better understanding of ground behavior within the excavation. Furthermore, they allow realistically assessing the impact of adverse geological conditions on shield jamming. The calculated thrust forces, which are required to move the machine forward, are in good agreement with field observations and measurements. It also proves that the numerical analysis can effectively be used for evaluating the effect of adverse geological environment on TBM entrapments and can be applied to prediction of loads on the shield and preestimating of the required thrust force during excavation through adverse ground conditions.

Rescheduling Problems with Bicriteria

In the rescheduling on a single machine,a set of original jobs has already been scheduled to minimize some cost objective,when a new set of jobs arrives and creates a disruption.The decision maker needs to insert the new jobs into the existing schedule without excessively disrupting it.In this paper,we consider hierarchical optimization between the scheduling cost of all the jobs and the degree of this disruption.For every problem,we provide either a polynomial time algorithm or an intractable result.

Scheduling problems on tardiness penalty and earliness award with simply linear processing time

In this paper, a single-machine scheduling model with a given common due date and simple linear processing times was considered. The objective is the total weighted tardiness penalty and earliness award. Some polynomial time solvable cases for this problem are given. A dynamic programming algorithm was provided and a branch and bound algorithm for general case of the problem was provided based on a rapid method for estimating the lower bound.

Rescheduling to Minimize Total Completion Time Under a Limit Time Disruption for the Parallel Batch

In the rescheduling on a single machine, a set of the original jobs has already been scheduled, in order to make a given objective function is optimal. The decision maker needs to insert the new jobs into the existing schedule without excessively disrupting it. A batching machine is a machine that can handle up to some jobs simultaneously. In this paper,we consider the total completion time under a limit on the sequence disruptions for parallel batching based on rescheduling. For the parallel batching problem based on rescheduling, we research the properties of feasible schedules and optimal schedules on the total completion time under a limit on the maximum time disruptions or total time disruptions, in which the jobs are sequenced in SPT order, and give out the pseudo-polynomial time algorithms on the number of jobs and the processing time of jobs by applying the dynamic programming method.

Sensitivity analysis for some scheduling problems

This paper gives the sensitivity analysis for some scheduling problems, including the following： what are the limits to a parameter change such that the solution remain optimal？ Given a specific change of a parameter, what is the new optimal cost？ Given a specific change of a parameter, what is a new optimal solution？ Here, the concern is mainly with the sensitivity analysis for some single-machine and flowshop scheduling problems with polynomial time algorithms. It is shown that, for these problems, the sensitivity analysis results depend on the positions of jobs with changed parameters.

Determination of Optimal Due-Date for Single-Machine Scheduling with Dynamic Programming Approach

This paper presents a method of dealing with the problem of assigning a due date which can either be known or unknown to a set of simultaneously available jobs and sequencing them on a single machine. The objective is to determine the optimal job sequence when the due date is common and known or to determine an optimal combination of the common due date and job sequence when the due date is unknown that minimizes a cost function. A dynamic programming algorithm of finding the optimal solution to the problem is presented. It is shown that the due date can simply be chosen from the set of marginal points of an interval which is divide within [0,∞] by the sum of every possible combination the job sequences. Finally, an illustrative example is provided.

ACHIEVING THRESHOLD BARRIER OF 1 nm ROUGHNESS VALUE OF SILICON SURFACE BY DIAMOND TURNING

nm roughness value of silicon surface by diamond turning is obtained firstly and three novel techniques are proposed. The surface integrity is studied in detail by using atomic force microscope, scanning electron microscope, and stylus surface instrument. The diamond tool sharpness has a considerable influence on the machined surface, therefore a novel technique—brightness modulation for measuring accurately the edge of the cutter is proposed. Mirror surfaces are assessed by another novel technique—a measure of their reflectivity. A third technique, single grit diamond machining is carried out. It supplies a experimental evidence for verifying the obtained high quality turned surfaces.

Minmax Common Due-Window Assignment Scheduling with Deteriorating Jobs

This paper investigates the common due-window assignment scheduling problem with deteriorating jobs on a single machine in which the processing time of a job is a proportional function of its starting time.The goal is to minimize the maximum value of earliness and tardiness penalties,as well as due-window location cost,and size cost.Depending on whether the location and size of due-window are known,this paper studies three relevant cases,all of which are solvable in polynomial time.