Single-machine scheduling with deteriorating jobs and setup times to minimize the maximum tardiness

In many realistic production situations, a job processed later consumes more time than the same job when it is processed earlier. Production scheduling in such an environment is known as scheduling with deteriorating jobs. However, research on scheduling problems with deteriorating jobs has rarely considered explicit (separable) setup time (cost). In this paper, we consider a single-machine scheduling problem with deteriorating jobs and setup times to minimize the maximum tardiness. We provide a branch-and-bound algorithm to solve this problem. Computational experiments show that the algorithm can solve instances up to 1000 jobs in reasonable time.     

小批量多类型PCB板组装生产调度算法研究

文章针对目前电子制造业中常见的小批量、多类型PCB板组装生产过程,研究如何进行生产调度以缩短总生产时间。文章着重考虑了不同PCB板类型转换生产时的调整时间对生产效率的影响,提出了一种能够有效缩短PCB生产调整时间的生产调度启发式算法。仿真数据表明,该算法能够给出较好的生产调度方案,提高PCB组装生产效率。     

Deteriorating job scheduling to minimize the number of late jobs with setup times

Deteriorating jobs scheduling problems have been widely studied recently. However, research on scheduling problems with deteriorating jobs has rarely considered explicit setup times. With the current emphasis on customer service and meeting the promised delivery dates, we consider a single-machine scheduling problem to minimize the number of late jobs with deteriorating jobs and setup times in this paper. We derive some dominance properties, a lower bound, and an initial upper bound by using a heuristic algorithm to speed up the search process of the branch-and-bound algorithm. Computational experiments show that the algorithm can solve instances up to 1000 jobs in a reasonable amount of time.     

考虑柔性机器检修的钢管热轧批量调度方法

本文从无缝钢管生产管理中提取并定义了周期性机器柔性检修环境下的钢管热轧批量调度问题,针对无缝钢管热轧阶段的生产特点,将其抽象为一类考虑序列相关设置成本和机器柔性检修的单机调度问题,建立了以最小化机器闲置时间和机器调整时间为优化目标的数学模型。分析闲置时间和检修时点的关系,证明了闲置时间最小化性质,结合问题特征设计了两阶段启发式算法。算法第一阶段采用最小轧机调整时间规则获取具有最小机器调整时间的初始批量轧制序列,第二阶段对初始轧制序列进行全局寻优搜索。基于实际生产数据设计了多种问题规模的对比实验,实验结果表明模型和算法对求解该类问题具有较好效果。     

A numerical method in optimal production and setup scheduling ofstochastic manufacturing systems

In this paper, we consider optimal production and setup scheduling in a failure-prone manufacturing system consisting of a single machine. The system can produce several types-of products, but at any given time it can only produce one type of product. A setup is required if production is to be switched from one type of product to another. The decision variables are a sequence of setups and a production plan. The objective of the problem is to minimize the cost of setup, production, and surplus. An approximate optimality condition is given together with a computational algorithm for solving the optimal control problem     

Scheduling with dependent setups and maintenance in a textile company

This paper deals with a scheduling problem with machine maintenance in a textile company. In the production system, the sequence-dependent setup time of a job cannot be ignored when a switch between two different jobs occurs. This study presents a heuristic to minimize the completion time, or equivalently the total setup time subject to periodic maintenance and due dates. The performance of the heuristic is evaluated by comparing its solution with the solution of the branch-and-bound algorithm. The real data are used to demonstrate the effectiveness of the heuristic.     

制造系统的递阶滚动优化调度模型

研究的对象是只有一台不可靠（failure-prone)机器的非完全柔性制造系统，该系统能生产多种产品，但在同一时刻只能生产一种产品，并且当机器由生产一种产品向生产另一种产品切换时，需要考虑setup时间及其成本，待决策变量是setup序列及产品生产率，本文基于非完全柔性制造系统的特点，引入递阶层控的思想，采用新的递阶结构框架和阈值控制策略，对问题进行分解，建立了考虑setup时间及成本的递阶流率控制最优化调度模型，并给出了递阶的滚动优化算法，仿真结果表明，这种调度策略更易于工程实现。     

考虑机器检修的热轧钢管批量计划方法

本文从无缝钢管生产实际中提取并定义了周期性机器检修环境下的钢管热轧批量计划问题,基于无缝钢管生产的特殊性,将该问题抽象为一类考虑机器检修和机器调整时间的单机调度问题,并建立了以最小化机器闲置和机器调整时间为目标的数学模型.针对批量间的机器调整时间取决于钢管规格的变化这一特性,提出了最小调整时间排序规则,证明了该规则在不考虑检修计划时具有最优性.进而,以此为基础建立了循环求解框架,并设计了两阶段启发式算法.基于实际生产数据设计了多种问题规模的实验,验证了算法的有效性,并从实际应用角度对结果进行了分析.     

Makespan minimization for scheduling unrelated parallel machines with setup times

This study considers the problem of scheduling jobs on unrelated parallel machines with machine-dependent and job sequence-dependent setup times. In this study, a restricted simulated annealing (RSA) algorithm which incorporates a restricted search strategy is presented to minimize the makespan. The proposed RSA algorithm can effective reduce the search effort required to find the best neighborhood solution by eliminating ineffective job moves. The effectiveness and efficiency of the proposed RSA algorithm is compared with the basic simulated annealing and existing meta-heuristics on a benchmark problem dataset used in earlier studies. Computational results indicate that the proposed RSA algorithm compares well with the state-of-the-art meta-heuristic for small-sized problems, and significantly outperforms basic simulated annealing algorithm and existing algorithms for large-sized problems.     

A heuristic approach for single-machine scheduling with due dates and class setups

The single-machine sequence-independent class setup scheduling problem is examined in this paper. It is assumed that jobs are classified into classes and a setup is required between jobs of different classes, but not of the same class. Furthermore, this setup time is fixed and depends only on the current job. Since the problem is NP-hard, a heuristic algorithm is proposed to find an approximate schedule that minimizes the maximum lateness on a set of jobs. The algorithm can easily be modified to solve the maximum tardiness problems as well. The accuracy of the heuristic algorithm in generating near optimal solutions is empirically evaluated.Scope and purposeFor batch manufacturing, it maybe desirable to produce many items of the same type, or class, at the same run in order to save the setup cost. However, committing facilities to long production runs for one product may inevitably make others tardy. Small batch size may conform urgent jobs to their delivery date, but one of the consequences would be the loss of productive efficiency due to numerous setups. Therefore, scheduling is basically a trade-off between the inherently conflicting efficiency measure and due-date compliance. This paper considers a single-machine scheduling problem in which jobs are classified into classes and a setup is required between jobs of different classes. The setup time is fixed and depends only on the current job. This problem is called a sequence-independent class setup problem and is NP-complete.     

Bi-criteria flexible job-shop scheduling with sequence-dependent setup times—Variable neighborhood search approach

In scheduling problems, taking the sequence-dependent setup times into account is one of the important issues that have recently been considered by researchers in the production scheduling field. In this paper, we consider flexible job-shop scheduling problem (FJSP) with sequence-dependent setup times to minimize makespan and mean tardiness. The FJSP consists of two sub-problems from which the first one is to assign each operation to a machine out of a set of capable machines, and the second one deals with sequencing the assigned operations on all machines. To solve this problem, a variable neighborhood search (VNS) algorithm based on integrated approach is proposed. In the presented optimization method, the external loop controlled the stop condition of algorithm and the internal loop executed the search process. To search the solution space, the internal loop used two main search engines, i.e. shake and local search procedures. In addition, neighborhood structures related to the sequencing problem and the assignment problem were employed to generate neighboring solutions. To evaluate the performance of the proposed algorithm, 20 test problems in different sizes are randomly generated. Consequently, computational results and comparisons validate the quality of the proposed approach.     

Dynamic programming algorithms for scheduling parallel machines with family setup times

We address the problem of scheduling jobs with family setup times on identical parallel machines to minimize total weighted flowtime. We present two dynamic programming algorithms — a backward algorithm and a forward algorithm — and we identify characteristics of problems where each algorithm is best suited. We also derive two properties that improve the computational efficiency of the algorithms.Scope and purposeWhile most production schedulers must balance conflicting goals of high system efficiency and timely completion of individual jobs, consideration of this conflict is underdeveloped in the scheduling literature. This paper examines a model that incorporates a fundamental cause of the efficiency/timeliness conflict in practice. We propose solution methodologies and properties of an optimal solution for the purpose of exposing insights that may ultimately be useful in research on more complex models.     

A parallel matching algorithm for convex bipartite graphs and applications to scheduling

An efficient parallel algorithm to obtain maximum matchings in convex bipartite graphs is developed. This algorithm can be used to obtain efficient parallel algorithms for several scheduling problems. Some examples are: job scheduling with release times and deadlines; scheduling to minimize maximum cost; and preemptive scheduling to minimize maximum completion time.     

Notes on “some single-machine scheduling problems with general position-dependent and time-dependent learning effects”

This paper provides a continuation of the idea presented by Yin et al. [Yin et al., Some scheduling problems with general position-dependent and time-dependent learning effects, Inform. Sci. 179 (2009) 2416-2425]. For each of the following three objectives, total weighted completion time, maximum lateness and discounted total weighted completion time, this paper presents an approximation algorithm which is based on the optimal algorithm for the corresponding single-machine scheduling problem and analyzes its worst-case bound. It shows that the single-machine scheduling problems under the proposed model can be solved in polynomial time if the objective is to minimize the total lateness or minimize the sum of earliness penalties. It also shows that the problems of minimizing the total tardiness, discounted total weighted completion time and total weighted earliness penalty are polynomially solvable under some agreeable conditions on the problem parameters.     

基于规则的平行机台生产调度系统

针对某电器生产的平行机台调度系统，描述了该系统的组成结构与数据接口界定。     

Dual-Objective Mixed Integer Linear Program and Memetic Algorithm for an Industrial Group Scheduling Problem

Group scheduling problems have attracted much attention owing to their many practical applications. This work proposes a new bi-objective serial-batch group scheduling problem considering the constraints of sequence-dependent setup time, release time, and due time. It is originated from an important industrial process, i.e., wire rod and bar rolling process in steel production systems. Two objective functions, i.e., the number of late jobs and total setup time, are minimized. A mixed integer linear program is established to describe the problem. To obtain its Pareto solutions, we present a memetic algorithm that integrates a population-based nondominated sorting genetic algorithm II and two single-solution-based improvement methods, i.e., an insertion-based local search and an iterated greedy algorithm. The computational results on extensive industrial data with the scale of a one-week schedule show that the proposed algorithm has great performance in solving the concerned problem and outperforms its peers. Its high accuracy and efficiency imply its great potential to be applied to solve industrial-size group scheduling problems.      

A simulated annealing algorithm approach to hybrid flow shop scheduling with sequence-dependent setup times

One of the scheduling problems with various applications in industries is hybrid flow shop. In hybrid flow shop, a series of n jobs are processed at a series of g workshops with several parallel machines in each workshop. To simplify the model construction in most research on hybrid flow shop scheduling problems, the setup times of operations have been ignored, combined with their corresponding processing times, or considered non sequence-dependent. However, in most real industries such as chemical, textile, metallurgical, printed circuit board, and automobile manufacturing, hybrid flow shop problems have sequence-dependent setup times (SDST). In this research, the problem of SDST hybrid flow shop scheduling with parallel identical machines to minimize the makespan is studied. A novel simulated annealing (NSA) algorithm is developed to produce a reasonable manufacturing schedule within an acceptable computational time. In this study, the proposed NSA uses a well combination of two moving operators for generating new solutions. The obtained results are compared with those computed by Random Key Genetic Algorithm (RKGA) and Immune Algorithm (IA) which are proposed previously. The results show that NSA outperforms both RKGA and IA.     

Preemptive scheduling on two parallel machines with a single server

This paper addresses a preemptive scheduling problem on two parallel machines with a single server. Each job has to be loaded (setup) by the server before being processed on the machines. The preemption is allowed in this paper. The goal is to minimize the makespan. We first show that it is no of use to preempt the job during its setup time. Namely, every optimal preemptive schedule can be converted to another optimal schedule where all the setup times are non-preemptively performed on one machine. We then present an algorithm with a tight bound of 4/3 for the general case. Furthermore, we show that the algorithm can produce optimal schedules for two special cases: equal processing times and equal setup times, which are NP-hard in the non-preemptive version.     

基于多班教学优化的多目标分布式混合流水车间调度

单工厂环境下的混合流水车间调度问题已受到广泛关注,而多工厂环境下的分布式混合流水车间调度问题(distributed hybrid flow shop scheduling problem,DHFSP)研究进展则较小.针对考虑顺序相关准备时间的DHFSP,提出一种多班教学优化(multi-class teaching-...     

The total completion time open shop scheduling problem with a given sequence of jobs on one machine

This paper addresses the open shop scheduling problem to minimize the total completion time, provided that one of the machines has to process the jobs in a given sequence. The problem is NP-hard in the strong sense even for the two-machine case. A lower bound is derived based on the optimal solution of a relaxed problem in which the operations on every machine may overlap except for the machine with a given sequence of jobs. This relaxed problem is NP-hard in the ordinary sense, however it can be quickly solved via a decomposition into subset-sum problems. Both heuristic and branch-and-bound algorithm are proposed. Experimental results show that the heuristic is efficient for solving large-scaled problems, and the branch-and-bound algorithm performs well on small-scaled problems.Scope and purposeShop scheduling problems, widely used in the modeling of industrial production processes, are receiving an increasing amount of attention from researchers. To model practical production processes more closely, additional processing restrictions can be introduced, e.g., the resource constraints, the no-wait in process requirement, the precedence constraints, etc. This paper considers the total completion time open shop scheduling problem with a given sequence of jobs on one machine. This model belongs to a new class of shop scheduling problems under machine-dependent precedence constraints. This problem is NP-hard in the strong sense. A heuristic is proposed to efficiently solve large-scaled problems and a branch-and-bound algorithm is presented to optimally solve small-scaled problems. Computational experience is also reported.