Number of Tardy Jobs of Single Machine Scheduling Problem with Variable Processing Time

The number of tardy jobs of the single machine scheduling problem with a variable processing time is studied in accordance with the published instances of traffic transportation management engineering. It is proved by 3 partition problem that if the problem is of ready time and common deadline constrained, its complexity is NP hard in the strong sense. Finally, a polynomial algorithm for solving unit processing time and common deadline problems is proposed.

Minimizing Tardy Jobs in a Single Machine Scheduling Problem with Fuzzy Processing Times and Due Dates

The optimality of a fuzzy logic alternative to the usual treatment of uncertainties in a scheduling system using fuzzy numbers is examined formally. Processing times and due dates are fuzzified and presented by fuzzy numbers. With introducing the necessity measure, we compare fuzzy completion times of jobs with fuzzy due dates to decide whether jobs are tardy. The object is to minimize the numbers of tardy jobs. The efficient solution method for this problem is proposed. And deterministic counterpart of this single machine scheduling problem is a special case of fuzzy version.

A Note on Single-Machine Lot Scheduling with Splittable Jobs to Minimize the Number of Tardy Jobs

The single-machine lot scheduling problem with splittable jobs to minimize the number of tardy jobs has been showed to be weakly NP-hard in the literature.In this paper,we show that a generalized version of this problem in which jobs have deadlines is strongly NP-hard,and also present the results of some related scheduling problems.

透明聚碳酸酯板材的应力条纹值信息研究

根据Tardy补偿法的原理,对透明件用聚碳酸酯(PC)板材进行热光曲线实验,在不同加载状态下对条纹级次的变化进行了分析。结果表明:PC材料仅需要较小的载荷即可出现理想的条纹级次;PC材料受力后的应力响应时间对条纹级次有很大的影响;挤出成型获得的PC材料具有惟一的加载方向以获得规则的条纹图。同时,本研究获得了PC材料的条纹值这一重要基础数据。

具有窗口交货期的单机E/T调度问题

工件完成时间与交货期差的绝对值加权和最小化单机调度是典型的E/T(Earliness/Tardiness)的调度模型,是NP-hard问题.然而,当工件权值与加工时间成正比时,LPT(LargestProcessingTime)工件调度最优.本文讨论了上述问题具有窗口交货期且工件权值与加工时间成正比的情形,结果表明LPT工件调度仍然最优.

Robust single machine scheduling problem with uncertain job due dates for industrial mass production

The single machine scheduling problem which involves uncertain job due dates is one of the most important issues in the real make-to-order environment. To deal with the uncertainty, this paper establishes a robust optimization model by minimizing the maximum tardiness in the worst case scenario over all jobs. Unlike the traditional stochastic programming model which requires exact distributions, our model only needs the information of due date intervals. The worst case scenario for a given sequence that belongs to a set containing only n scenarios is proved, where n is the number of jobs. Then, the model is simplified and reformulated as an equivalent mixed 0-1 integer linear programming(MILP) problem. To solve the MILP problems efficiently, a heuristic approach is proposed based on a robust dominance rule. The experimental results show that the proposed method has the advantages of robustness and high calculating efficiency, and it is feasible for large-scale problems.

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.

A dynamic programming algorithm for scheduling problems on earliness award and tardiness penalty with time-dependent processing time

In this paper, a single-machine scheduling model with a given common due date is considered. Job processing time is a linear decreasing function of its starting time. The objective function is to minimize the total weighted earliness award and tardiness penalty. Our aim is to find an optimal schedule so as to minimize the objective function. As the problem is NP-hard, some properties and polynomial time solvable cases of this problem are given. A dynamic programming algorithm for the general case of the problem is provided.

Combined Timetabling Procedure and Complete Local Search for No-Wait Job Shop Scheduling with Total Tardiness

The strong non-deterministic polynomial-hard( NP-hard)character of job shop scheduling problem( JSSP) has been acknowledged widely and it becomes stronger when attaches the nowait constraint,which widely exists in many production processes,such as chemistry process, metallurgical process. However,compared with the massive research on traditional job shop problem,little attention has been paid on the no-wait constraint.Therefore,in this paper, we have dealt with this problem by decomposing it into two sub-problems, the timetabling and sequencing problems,in traditional frame work. A new efficient combined non-order timetabling method,coordinated with objective of total tardiness,is proposed for the timetabling problems. As for the sequencing one,we have presented a modified complete local search with memory combined by crossover operator and distance counting. The entire algorithm was tested on well-known benchmark problems and compared with several existing algorithms.Computational experiments showed that our proposed algorithm performed both effectively and efficiently.

Modified NSGA-II for a Bi-Objective Job Sequencing Problem

This paper proposes a better modified version of a well-known Multi-Objective Evolutionary Algorithm (MOEA) known as Non-dominated Sorting Genetic Algorithm-II (NSGA-II). The proposed algorithm contains a new mutation algorithm and has been applied on a bi-objective job sequencing problem. The objectives are the minimization of total weighted tardiness and the minimization of the deterioration cost. The results of the proposed algorithm have been compared with those of original NSGA-II. The comparison of the results shows that the modified NSGA-II performs better than the original NSGA-II.

No-Wait Flowshops to Minimize Total Tardiness with Setup Times

The m-machine no-wait flowshop scheduling problem is addressed where setup times are treated as separate from processing times. The objective is to minimize total tardiness. Different dispatching rules have been investigated and three were found to be superior. Two heuristics, a simulated annealing (SA) and a genetic algorithm (GA), have been proposed by using the best performing dispatching rule as the initial solution for SA, and the three superior dispatching rules as part of the initial population for GA. Moreover, improved versions of SA and GA are proposed using an insertion algorithm. Extensive computational experiments reveal that the improved versions of SA and GA perform about 95% better than SA and GA. The improved version of GA outperforms the improved version of SA by about 3.5%.

Genetic Algorithm for Scheduling Problem of Chemical Batch Process with Due Date Constraints

The intense competition in the current marketplace ha s forced firms to reexamine their methods of doing business, using superior manu facturing practices in the form of just-in-time (JIT), production with JIT pra ctices pursue completion on time and zero inventory, which is often instruct ed according to the custom’s demand or the sale contract. Earliness and tardine ss are undesirable because both of them will bring the extra cost, cost will als o be increased by some factors such as operation condition, intermediate storage , clean method, etc, to minimize the total cost is often the main scheduling objective, but sometime it is most important for factories to eliminate the tar diness cost in order to maintain the commercial credit and to avoid penalty, the refore, minimum of tardiness cost becomes the first objective. It is more import ant to select a reasonable objective by the actual condition during scheduli ng. In this paper scheduling problem of chemical batch process with due date is studied, two different intermediate storage policies and two different productio n modes are also discussed, production scheduling with different intermediate st orage policy and different production mode is proposed and the result is compare d. In order to complete all products within the due date, not only earliness and tardiness but also holding problem is considered, the objective is to selec t a proper intermediate storage policy and production mode and to minimize the c ost resulted by the earliness and tardiness, even the cost result by the interme diate storage. Scheduling with multiple stage and multiple machine is known as a NP-hard problem, mathematical program (MP) method, such as branch-and-bound (BAB), mixed integer linear program (MILP), etc, is often used to solve the sche duling problem. But as is well known, MP method is not good for combination opti mization, especially for large scale and complex optimal problem, whereas geneti c algorithm (GA) can overcome the MP method’s shortcoming and is fit for solvin g such scheduling problem. In this paper a modified genetic algorithm with speci al crossover operator and mutation operator is presented to solve this schedulin g problem. The results show such problem can be solved effectively with the pres ented method.

An Approximation Algorithm for the Common Due Date Scheduling Problem

In this paper,attention is paid to study an algorithm for the common due datetotal weighted tardiness problem of single machine scheduling. Anapproximation alsorithm is given. It performs well in the sense of worst-casebehaviour and its worst-case performance ratio is 2.

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.

工件具有相同加工时间和相同窗口交货期的单机E/T调度问题

研究工件具有相同的加工时间和相同的窗口交货期,目标函数是总费用函数的单机调度问题.给出了求解该问题的一个简洁的数学公式.

THE NP-HARDNESS OF THE SINGLE MACHINE COMMON DUE DATE WEIGHTED TARDINESS PROBLEM

In this paper we prove that the single machine common due dateweighted tardiness problem is NP-hard.

UNBOUNDED BATCH SCHEDULING WITH A COMMON DUE WINDOW ON A SINGLE MACHINE

The common due window scheduling problem with batching on a single machine is dealt with to minimize the total penalty of weighted earliness and tardiness. In this paper it is assumed that a job incurs no penalty as long as it is completed within the common due window. It is the first time for the due window scheduling to be extended to this situation so that jobs can be processed in batches. An unbounded version of batch scheduling is also considered. Hence, jobs, no matter how many there are, can be processed in a batch once the machine is free. For two cases that the location of due window is either a decision variable or a given parameter, polynomial algorithms are proposed based on several optimal properties.

THE SINGLE MACHINE STOCHASTIC SCHEDULING WITH THE WEIGHTED JOB TARDINESS MINIMIZATION

This paper considers scheduling n jobs on a single machine where the job processing times anddue dates are independent random variables with arbitrary distribution functions.We consider the casethat the weighted job tardiness in expectation is minimized.It is assumed that job's due dates arecompatible with processing times and weights.We show that the jobs should be sequenced indecreasing stochastic order of their due dates.

Scatter Search Based Particle Swarm Optimization Algorithm for Earliness/Tardiness Flowshop Scheduling with Uncertainty

Considering the imprecise nature of the data in real-world problems, the earliness/tardiness （E/T） fiowshop scheduling problem with uncertain processing time and distinct due windows is concerned in this paper. A fuzzy scheduling model is established and then transformed into a deterministic one by employing the method of maximizing the membership function of middle value. Moreover, an effective scatter search based particle swarm optimization （SSPSO） algorithm is proposed to minimize the sum of total earliness and tardiness penalties. The proposed SSPSO algorithm incorporates the scatter search （SS） algorithm into the frame of particle swarm optimization （PSO） algorithm and gives full play to their characteristics of fast convergence and high diversity. Besides, a differential evolution （DE） scheme is used to generate solutions in the SS. In addition, the dynamic update strategy and critical conditions are adopted to improve the performance of SSPSO. The simulation results indicate the superiority of SSPSO in terms of effectiveness and efficiency.

Simulated Annealing for Earliness/Tardiness Production Planning Model

To describe the earliness/tardiness production planning problems in the JIT environment, a nonlinear semi\|infinite programming model was proposed in \. Due to a nonconvex objective function and many infinite constraints, the model is difficult to be solved by traditional methods. In this paper, simulated annealing method combined with a heuristic is developed. Numerical results shows that the present approach is very efficient. Theoretically, the developed method is an attempt to solve a continuous domain problem by using simulated annealing.