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.

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.

Modeling and Analysis of Single Machine Scheduling Based on Noncooperative Game Theory

Considering the independent optimization requirement for each demander of modernmanufacture, we explore the application of noncooperative game in production scheduling research,and model scheduling problem as competition of machine resources among a group of selfish jobs.Each job has its own performance objective. For the single machine, multi-jobs and non-preemptivescheduling problem, a noncooperative game model is established. Based on the model, many prob-lems about Nash equilibrium solution, such as the existence, quantity, properties of solution space,performance of solution and algorithm are discussed. The results are tested by numerical example.

Deep Cutting Plane Inequalities for Stochastic Non-Preemptive Single Machine Scheduling Problem

We study the classical single machine scheduling problem but with uncertainty. A robust optimization model is presented, and an effective deep cut is derived. Numerical experiments show effectiveness of the derived cut.

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.

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]

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 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 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.

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.

An Improved Ant Colony Algorithm for a Single-machine Scheduling Problem with Setup Times

Motivated by industrial applications we study a single-machine scheduling problem in which all the jobs are mutu- ally independent and available at time zero.The machine processes the jobs sequentially and it is not idle if there is any job to be pro- cessed.The operation of each job cannot be interrupted.The machine cannot process more than one job at a time.A setup time is needed if the machine switches from one type of job to another.The objective is to find an optimal schedule with the minimal total jobs’completion time.While the sum of jobs’processing time is always a constant,the objective is to minimize the sum of setup times.Ant colony optimization(ACO)is a meta-heuristic that has recently been applied to scheduling problem.In this paper we propose an improved ACO-Branching Ant Colony with Dynamic Perturbation(DPBAC)algorithm for the single-machine schedul- ing problem.DPBAC improves traditional ACO in following aspects:introducing Branching Method to choose starting points;im- proving state transition rules;introducing Mutation Method to shorten tours;improving pheromone updating rules and introduc- ing Conditional Dynamic Perturbation Strategy.Computational results show that DPBAC algorithm is superior to the traditional ACO algorithm.

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.

基于位置权重的窗口指派单机排序问题

研究了基于位置权重的窗口指派排序问题,机器限定为一台,其目的是在准时制环境下极小化窗口指派的窗口开始时间、窗口大小以及总延误的加权之和,以找到其最优工件加工序列以及窗口开始时间d^(1)_(k)(结束时间d^(2)_(k)),其中权重只和位置有关,而与工件无关。在共同、松弛和不同窗口指派下,通过相应最优解性质,证明此问题能够多项式时间可解。对于共同以及松弛窗口指派,算法的复杂度为O(n^(2)log n),而对不同窗口指派,问题可在O(n log n)时间内求解,其中n为给定工件数量。

考虑释放时间的单机JIT调度问题

本文主要研究二级供应链中的生产-库存-直接配送协同调度问题,其中存在一个制造商和多个零售商,制造商根据订单进行生产,然后将产品配送给零售商。该类问题可以抽象为考虑释放时间的单机JIT调度问题。借助于禁忌搜索算法,本文提出了求解问题的CTA-TS算法,并通过大量的实验数据与已有算法进行比较,说明了本文提出算法的有效性。

工件权重带限制的最小化最大加权完工时间的单机在线排序问题

本文考虑了最小化最大加权完工时间的单机在线排序问题,要求工件的权重在工件加工时间一定范围之内且工件的权重和工件加工时间具有一致性,即apj≤wj≤bpj(a≥(5√−1)/2b,b≥a)且若wi>wj则pi≥pj,如果wi=wj则pi=pj。工件以时间在线的方式到达,只有工件Jj在达到释放时间rj后,决策者才知晓工件的基本信息,如加工时间pj和权重wj。对于此问题,首先利用对手法证明了其下界为1+b/(b+a),随后给出了竞争比为1+b/(b+a)的最好可能的在线算法。特别地,当a=(5√−1)/2b时,该算法的竞争比为(5√+1)/2。

带有公共交货期窗口问询和退化工件的单机排序问题

为了研究考虑公共交货期窗口问询的退化工件排序问题,构建了极小化因提前时间、延误时间以及交货期窗口问询产生的总成本的单机排序调度决策模型。模型假定所有工件的交货期窗口一致,且窗口的开始时间、窗口大小为决策变量;工件具有差异化的退化因子;工件的实际加工时间与其开始加工时间、退化因子呈线性关系。分析了交货期窗口决策和工件排序具有的最优性质,以及最优的工件排序与工件退化因子之间的关系,并提出了最优算法。研究表明:可基于工件的退化因子确定最优工件加工顺序,最优交货期窗口的开始时间和结束时间分别对应于最优序中某个工件的完工时间,研究问题可在多项式时间内进行求解。

基于拉格朗日松弛的产能共享讨价还价研究

以制造业产能共享为背景,考虑自利的产能提供方与需求方诉求不一致和市场关系不对等因素,采用Nash讨价还价理论研究共享产能分配策略。为此,首先将传统调度模型与非对称Nash讨价还价模型相结合,构建出本质为非线性整数规划的产能共享模型。继而,设计了基于拉格朗日松弛的求解算法,给出了产能共享的讨价还价分配结果。仿真分析表明,本文方法在大部分情况下能够获得理想的讨价还价结果。当产能提供方目标为min-sum型,其关注所有客户的自利且异质的时效要求,其与客户方的冲突尤其显著;随着其讨价还价能力的增强,其改善是以牺牲客户时效要求为代价的。然而当其讨价还价能力再继续增加,反而导致系统整体效益的波动。因此,博弈各方需要保持合理的讨价还价强度。