Heterogeneous dispatching rules in job and flow shops

This paper reports the results of a study of the use of heterogeneous dispatching rules for the scheduling of work in a job shop. The methodology employed included discrete event simulation, using rule combinations determined by prior genetic algorithm searches and generalization using neural networks. Eight dispatching rules were considered, including first in first out (FIFO), earliest due date ( EDD), shortest processing time (SPT), slack/ number of operations (SLK), critical ratio (CR), modified due date (MDD), modified operation due date (MOD), and apparent tardiness cost (ATC). A three-machine job shop was studied, in which three work organizations were employed, pure flow (fixed sequence), pure job shop ( random sequence), and a hybrid shop where flow is random but with unequal probabilities. Three levels of machine loading were used and average tardiness was used as the performance measure. In most cases, modified due date and apparent tardiness cost were the best rules. The application of the best rules effected the results primarily when applied to bottleneck machines or the first machine in a pure flow shop. Nearly any other rule was acceptable on non-botdeneck machines except FIFO and CR, which consistently perform poorly. No major advantage of mixing rules was found.     

Optimum common cycle for scheduling a single-machine multiproduct system with a budgetary constraint

This paper deals with the single machine multi-product lot size scheduling problem, and has two objectives. The first objective is to minimize the maximum aggregate inventory for the common cycle (CC) scheduling policy. A simple and easy-to-apply rule has been developed which determines the optimal production sequence that achieves this objective. The second objective is to find an optimal common cycle for minimizing the average production and inventory costs per unit time, subject to a given budgetary constraint. A method has been presented that achieves this objective     

考虑交通时间与设备转换时间的跨区域就医调度优化问题

在资源共享时代背景下,跨区域就医可以很好地解决患者日益增长的就医需求与医疗资源紧张的矛盾。本论文以医疗联盟为研究对象,在关键医疗资源共享的前提下,通过患者跨区域就医实现就医诊断延误最小化,以满足患者就医需求。本研究同时考虑了患者跨区域交通时间与基于患者诊断类型的设备转换时间,以最小化患者就医总延迟为目标,分配患者就诊医院及优化患者就诊/检查顺序。针对该问题,论文首次提出以最早交货期原则（EDD rule）为基础,以患者再分配为主导的EDD-ReAss1和EDD-ReAss2启发式算法,结合局部搜索算法以进一步提高就医调度方案的质量,缩短患者诊断/检查等待时间。实验结果表明,新启发式算法EDD-ReAss1和EDD-ReAss2算法性能显著好于EDD,SPT和LPT等调度规则;在较短运算时间内Swap局部搜索算法性能最优。     

Evaluation of simple dispatching rules for dynamic single-machine earliness/tardiness problem

Abstract. This paper investigates the effects of four simple dispatching rules on just-in-time production related performance measures of mean and maximum absolute lateness. The rules used are modified due date (MDD), shortest processing time (SPT), earliest due date (EDD), and first in first out (FIFO). A single machine is used under three utilization levels. Due-dates are set according to total work content rule. The results indicate that each rule performs well under certain conditions. The MDD rule is the best one to minimize mean absolute lateness. The EDD and FIFO rules do well in minimizing the maximum absolute lateness. Economic interpretation of these performance measures are also discussed.     

混合离散差分进化算法在单机批处理调度中的应用

本文研究单机批处理调度问题,批处理机有批次容量限制,批处理时间由每个批次所含作业中的最长作业处理时间决定。每个作业具有不同的大小、处理时间、提前拖期惩罚权重,所有作业具有公共交货期,且交货期无限晚。目标函数为最小化所有作业的加权提前拖期惩罚之和。该问题已被证明为NP难题,本研究找到了其最优解具有的一些性质,在此基础上利用它们提出了一种动态规划(DP)与差分进化(DE)算法相结合的混合离散差分进化(HDDE)算法来求解该问题,通过与传统的遗传算法、模拟退火算法和迭代贪婪算法进行对比,HDDE算法显示了更加强大的全局搜索能力。     

Efficient jobshop dispatching rules: Further developments

Many dispatching rules for scheduling in dynamic jobshops have been proposed over many years. The research issues in jobshop scheduling seem to be still open in the sense that no single rule has been found to be the best under all shopfloor conditions even with respect to one single measure of performance. Added to this problem, there are several measures of performance, e.g. the minimizations of mean, maximum and variance of flowtime, percentage of tardy jobs, and mean, maximum and variance of tardiness of jobs. Recent studies have reported the development of more efficient dispatching rules than the popular rules, e.g. SPT, COVERT, MOD and ATC. This study is an attempt to improve some of the recently reported dispatching rules. An extensive simulation study reveals that the improved rules developed in the present study appear to be quite effective in minimizing mean flowtime, and maximum tardiness and variance of tardiness of jobs.     

Simple policies in the economic lot scheduling problem with zero setup costs

The economic lot scheduling problem is analysed for the case when the cost of setups, but not their duration, is assumed to be zero. This would be the case when setups are performed by the machine operators, or when management's goal is holding-cost reduction. Theoretical results are presented describing when the common cycle solution of producing one lot of every item every cycle is optimal or near optimal. Computational results using simulated data are then presented which show that the common cycle solution is nearly optimal in a wide range of practical situations.     

Scheduling to Improve Field Service Quality*

This research addresses the problem of scheduling technicians to travel from customer site to customer site to perform emergency maintenance on office machines, computers, robots, telecommunications equipment, medical equipment, heating/cooling equipment, household appliances, and other equipment. We call this the Traveling Technician Problem (TTP). In its simplest form, the TTP is a multiserver, sequence-dependent, tardiness minimization problem. This research frames the TTP as a service quality maximization problem in which service quality is defined in terms of mean tardiness, mean technician phone response time, mean promise time, and mean response time. Tardiness is defined with respect to contractually guaranteed response times. Industry practice is to use dispatching rules to assign service calls to technicians. This research proposes scheduling procedures to maximize field service quality in a dynamic environment. A simulation experiment was used to compare three dispatching rules and three scheduling procedures for the TTP. The scheduling procedures dominated the dispatching rules on all four service quality measures. The proposed scheduling procedures hold promise for improving service quality in a wide variety of field service organizations and in other scheduling environments as well.     

A note on a well-known dispatching rule to minimize total tardiness

The single machine tardiness problem is considered. We clarify and correct an earlier result related to the Modified Due Date (MDD) Rule of Baker and Bertrand and show that a heuristic does not always satisfy an optimal sequence. However, we present some interesting special cases of optimal sequences that do satisfy the MDD Rule. We believe this note is important because the MDD Rule is still considered to be one of the most efficient rules to minimize the single machine tardiness problem. Because of its dispatching nature and simplicity, the MDD Rule is found to be very practical. It is widely applied in both static and dynamic job shop and industrial settings where setup times if any are negligible or included in the job processing times and hence not an issue.     

A fast FPTAS for single machine scheduling problem of minimizing total weighted earliness and tardiness about a large common due date

We address the single machine scheduling problem to minimize the total weighted earliness and tardiness about a nonrestrictive common due date. This is a basic problem with applications to the just-in-time manufacturing. The problem is linked to a Boolean programming problem with a quadratic objective function, known as the half-product. An approach to developing a fast fully polynomial-time approximation scheme (FPTAS) for the problem is identified and implemented. The running time matches the best known running time for an FPTAS for minimizing a half-product with no additive constant.     

加权折扣单机排序干扰管理模型和算法研究

为解决机器排序中由于干扰事件的发生使初始最优加工时间表无法按计划执行的问题,构建同时考虑原目标和扰动目标的双目标干扰管理模型,对初始最优加工时间表进行调整并对未完工工件进行重排序;在双目标干扰管理模型中,原目标由所有工件的加权折扣完工时间和来度量,扰动目标由重排序后工件完工时间的变化来度量;结合量子比特在表示解的多样性方面的优点和非支配排序遗传算法在处理多目标排序问题上的优点,设计一种量子遗传算法和非支配排序遗传算法相结合的启发式进化算法对构建的模型进行求解。在数值算例中,通过比较若干项针对有效解集的性能指标发现,该混合算法求得的有效解集在多样性和与最优有效前沿的邻近性等方面优于目前得到广泛应用的非支配排序遗传算法,验证了构建的模型和算法对于求解机器排序干扰管理问题的有效性。     

Minimizing tardiness on a single processor with sequence-dependent setup times: a simulated annealing approach

In today's fast-paced Just-In-Time and mass customization manufacturing in a sequence-dependent setup environment, the challenge of making production schedules to meet due-date requirements is becoming a more complex problem. Unfortunately, much of the research on operations scheduling problems has either ignored setup times or assumed that setup times on each machine are independent of the job sequence. This paper considers the problem of minimizing tardiness, a common measure of due-date performance, in a sequence-dependent setup environment. Simulated annealing was used to solve the sequencing problem, and its performance was compared with random search. Our experimental results show that the algorithm can find a good solution fairly quickly, and thus can rework schedules frequently to react to variations in the schedule. The algorithm is invaluable for ‘on-line’ production scheduling and ‘last-minute’ changes to production schedule. The results of this research also suggest ways in which more complex and realistic job shop environments, such as multiple machines with a higher number of jobs in the sequence, and other scheduling objectives can be modeled. This research also investigates computational aspects of simulated annealing in solving complex scheduling problems.     

Total tardiness minimization on unrelated parallel machine scheduling with auxiliary equipment constraints

This research deals with scheduling jobs on unrelated parallel machines with auxiliary equipment constraints. Each job has a due date and requires a single operation. A setup for dies is incurred if there is a switch from processing one type of job to another type. For a die type, the number of dies is limited. Due to the attributes of the machines and the fitness of dies to each, the processing time for a job depends on the machine on which the job is processed, each job being restricted to processing on certain machines. In this paper, an effective heuristic based on threshold-accepting methods, tabu lists, and improvement procedures is proposed to minimize total tardiness. An extensive experiment is conducted to evaluate the computational characteristics of the proposed heuristic. Computational experiences demonstrate that the proposed heuristic is capable of obtaining optimal solutions for small-sized problems, and significantly outperforms an ATCS procedure and a simulated annealing method for problems in larger sizes.     

考虑分时电价的多目标批调度问题蚁群算法求解

对同时优化电力成本和制造跨度的多目标批处理机调度问题进行了研究,设计了两种多目标蚁群算法,基于工件序的多目标蚁群算法(J-PACO,Job-based Pareto Ant Colony Optimization)和基于成批的多目标蚁群算法(B-PACO,Batch-based Pareto Ant Colony Optimization)对问题进行求解分析。由于分时电价中电价是时间的函数,因而在传统批调度进行批排序的基础上,需要进一步确定批加工时间点以测定电力成本。提出的两种蚁群算法分别将工件和批与时间线相结合进行调度对此类问题进行求解。通过仿真实验将两种算法对问题的求解进行了比较,仿真实验表明B-PACO算法通过结合FFLPT(First Fit Longest Processing Time)启发式算法先将工件成批再生成最终方案,提高了算法搜索效率,并且在衡量算法搜索非支配解数量的Q指标和衡量非支配集与Pareto边界接近程度的HV指标上,均优于J-PACO算法。     

A heuristic for scheduling in a flowshop with the bicriteria of makespan and maximum tardiness minimization

This article deals with the development of a heuristic for scheduling in a flowshop with the objective of minimizing the makespan and maximum tardiness of a job. The heuristic makes use of the simulated annealing technique. The proposed heuristic is relatively evaluated against the existing heuristic for scheduling to minimize the weighted sum of the makespan and maximum tardiness of a job. The results of the computational evaluation reveal that the proposed heuristic performs better than the existing one.     

一种差异工件单机批调度问题的蚁群优化算法

由于在利用蚁群算法构建差异工件(即工件有尺寸差异)单机批调度问题的解时,批的加工时间是不确定的.从而不能类似于经典调度问题的蚁群算法把批加工时间的倒数作为蚁群算法中的启发式信息,引入批的利用率和批的负载均衡率作为蚁群算法中的启发式信息,提出了JACO(ant colony optimization based a job sequence)和BACO(ant colony optimization based a batch sequence)两种蚁群优化算法.在算法JACO中,解的编码为工件序列,它对应着用BF(best fit)分批规则生成的调度方案,信息素代表工件间的排列顺序;在算法BACO中,解的编码为批序列,信息素代表工件间的批相关性,由此信息素通过中间信息素量来构造相应的解,并引入特定的局部优化策略,提高了算法的搜索效率.实验表明,与以往文献中的SA(simula-ted annealing)、GA(genetic algorithm)算法以及FFLPT(first-fit longest processing time)、BFLPT (best-fit longest processing time)启发式规则相比,算法JACO和BACO明显优于它们,且BACO算法比JACO算法效果更好.     

基于图的广度搜索的进度生成机制

启发式算法是解决资源受限的项目调度问题的经典方法之一，通常用来生成元启发算法初始解，传统的串行（SSGS）和并行（PSGS）是生成项目调度方案的经典机制，本文基于图的广度优先搜索算法，提出了一种考虑任务节点位置因素的广度生成机制（BSSGS），并验证了算法的效果。借鉴广度搜索算法定义进度生成机制中的当前任务集合C、候选任务集合D以及阶段变量g等，对各任务节点进行层次划分并定义任务调度秩序；结合优先规则选择候选任务j^*并进行资源R_k（t）调度更新，进而生成完整的调度方案；案例分析表明新机制在满足优先规则和资源约束的同时兼顾了任务节点在网络中位置因素，拥有对于局部复杂网络不回避，对关键节点及时调度等明显优势；选择PSPLIB中算例，在不同优先规则下对新机制进行了测试，测试结果表明新的进度生成机制在LPT、SPT、MTS和MIS等优先规则下，在平均最短工期、平均资源利用率及最优调度方案率等方面优于串行和并行进度生成机制，且算法时间复杂度与传统机制相比并未增加，仍为O（J²，K）。     

A multiobjective genetic algorithm for job shop scheduling

In this paper, a Multi Objective Genetic Algorithm (MOGA) is proposed to derive the optimal machine-wise priority dispatching rules ( pdrs ) to resolve the conflict among the contending jobs in the Giffler and Thompson (GT) procedure applied for job shop problems. The performance criterion considered is the weighed sum of the multiple objectives minimization of makespan, minimization of total idle time of machines and minimization of total tardiness. The weights assigned for combining the objectives into a scalar fitness function are not constant. They are specified randomly for each evaluation. This in turn leads to the multidirectional search in the proposed MOGA, which in turn mitigates the solution being entrapped in local minima. The applicability and usefulness of the proposed methodology for the scheduling of job shops is illustrated with 28 benchmark problems available in the open literature.     

PRODUCTION SCHEDULING OF CONTINUOUS FLOW LINES: MULTIPLE PRODUCTS WITH SETUP TIMES AND COSTS

The problem of production planning and setup scheduling of multiple products on a single facility is studied in this paper. The facility can only produce one product at a time. A setup is required when the production switches from one type of product to another. Both setup times and setup costs are considered. The objective is to determine the setup schedule and production rate for each product that minimize the average total costs, which include the inventory, backlog, and setup costs. Under the assumption of a constant production rate, we obtain the optimal cyclic rotation schedule for the multiple products system. Besides the decision variables studied in the classical economic lot scheduling problem (ELSP), the production rate is also a decision variable in our model. We prove that our solutions improve the results of the classical ELSP.     

A tardiness-augmented approximation scheme for rejection-allowed multiprocessor rescheduling

In the multiprocessor scheduling problem to minimize the total job completion time, an optimal schedule can be obtained by the shortest processing time rule and the completion time of each job in the schedule can be used as a guarantee for scheduling revenue. However, in practice, some jobs will not arrive at the beginning of the schedule but are delayed and their delayed arrival times are given to the decision-maker for possible rescheduling. The decision-maker can choose to reject some jobs in order to minimize the total operational cost that includes three cost components: the total rejection cost of the rejected jobs, the total completion time of the accepted jobs, and the penalty on the maximum tardiness for the accepted jobs, for which their completion times in the planned schedule are their virtual due dates. This novel rescheduling problem generalizes several classic NP-hard scheduling problems. We first design a pseudo-polynomial time dynamic programming exact algorithm and then, when the tardiness can be unbounded, we develop it into a fully polynomial time approximation scheme. The dynamic programming exact algorithm has a space complexity too high for truthful implementation; we propose an alternative to integrate the enumeration and the dynamic programming recurrences, followed by a depth-first-search walk in the reschedule space. We implemented the alternative exact algorithm in C and conducted numerical experiments to demonstrate its promising performance.