Maximization of solution flexibility for robust shop scheduling

We consider the problem of introducing flexibility in the schedule determination phase, for shop scheduling problems with release dates and deadlines. The flexibility is provided by generating a family of schedules, instead of a unique one. We represent a family of schedules by an ordered group assignment defining for each machine a sequence of groups where the operations within a group are totally permutable. We propose a polynomial time algorithm to evaluate the worst case completion time of operations in an ordered group assignment. We then consider the single machine problem with heads and deadlines associated to operations, as a sub-problem of the job shop problem. We propose polynomial time dynamic programming algorithms for minimizing the number of groups and for maximizing the number of characterized sequences, under specific constraints. Finally, computational experiences on job shop benchmarks, show the impact of grouping operations on the solution makespan value.     

重入排序问题综述

重入排序问题打破传统假设：工件在加工过程中不止一次地访问某台机器,是一种新型的排序问题. 重入的特点源于半导体生产, 并广泛存在于其他领域. 对重入排序问题已有文献中的成果进行梳理和分析,按问题所处机器环境的不同, 对内容和方法进行分类介绍和总结：包括单机问题、流水作业问题、混合流水作业问题及其他机器环境下的重入排序问题. 最后展望未来的趋势和研究方向.     

Scheduling job families on non-identical parallel machines with time constraints

This paper studies the scheduling of lots (jobs) of different product types (job family) on parallel machines, where not all machines are able to process all job families (non-identical machines). A special time constraint, associated to each job family, should be satisfied for a machine to remain qualified for processing a job family. This constraint imposes that the time between the executions of two consecutive jobs of the same family on a qualified machine must not exceed the time threshold of the family. Otherwise, the machine becomes disqualified. This problem comes from semiconductor manufacturing, when Advanced Process Control constraints are considered in scheduling problems. To solve this problem, two Mixed Integer Linear Programming models are proposed that use different types of variables. Numerical experiments show that the second model is much more effective, and that there is a trade-off between optimizing the scheduling objective and maximizing the number of machines that remain qualified for the job families. Two heuristics are also presented and studied in the numerical experiments.     

Single-machine scheduling with time window-dependent processing times

In the one-machine scheduling problems analysed in this paper, the processing time of a job depends on the time at which the job is started. More precisely, the horizon is divided into time windows and with each one a coefficient is associated that is used to determine the actual processing time of a job starting in it. Two models are introduced, and one of them has direct connections with models considered in previous papers on scheduling problems with time-dependent processing times. Various computational complexity results are presented for the makespan criterion, which show that the problem is NP-hard, even with two time windows. Solving procedures are also proposed for some special cases.     

Single-machine scheduling of multi-operation jobs without missing operations to minimize the total completion time

We consider the problem of scheduling multi-operation jobs on a singe machine to minimize the total completion time. Each job consists of several operations that belong to different families. In a schedule each family of job operations may be processed as batches with each batch incurring a set-up time. A job is completed when all of its operations have been processed. We first show that the problem is strongly NP-hard even when the set-up times are common and each operation is not missing. When the operations have identical processing times and either the maximum set-up time is sufficiently small or the minimum set-up time is sufficiently large, the problem can be solved in polynomial time. We then consider the problem under the job-batch restriction in which the operations of each batch is partitioned into operation batches according to a partition of the jobs. We show that this case of the problem can be solved in polynomial time under a certain condition.     

Learning and forgetting effects on a group scheduling problem

This paper proposes to investigate learning and forgetting effects on the problem of scheduling families of jobs on a single machine to minimize total completion time of jobs. A setup time is incurred whenever the single machine transfers job processing from a family to another family. To analyze the impact of learning and forgetting on this group scheduling problem, we structure three basic models and make some comparisons through computational experiments. The three models, including no forgetting, total forgetting and partial forgetting, assume that the processing time of a job is dependent on its position in a schedule. Some scheduling rules and a lower bound are derived in order to constitute our branch-and-bound algorithm for searching an optimal sequence. In addition, an efficient and simply-structured heuristic is also built to find a near-optimal schedule.     

Fuzzy scheduling of job orders in a two-stage flowshop with batch-processing machines

In this paper, we present a mixed-integer fuzzy programming model and a genetic algorithm (GA) based solution approach to a scheduling problem of customer orders in a mass customizing furniture industry. Independent job orders are grouped into multiple classes based on similarity in style so that the required number of setups is minimized. The family of jobs can be partitioned into batches, where each batch consists of a set of consecutively processed jobs from the same class. If a batch is assigned to one of available parallel machines, a setup is required at the beginning of the first job in that batch. A schedule defines the way how the batches are created from the independent jobs and specifies the processing order of the batches and that of the jobs within the batches. A machine can only process one job at a time, and cannot perform any processing while undergoing a setup. The proposed formulation minimizes the total weighted flowtime while fulfilling due date requirements. The imprecision associated with estimation of setup and processing times are represented by fuzzy sets.     

Single Machine Group Scheduling with Two Ordered Criteria

The problem of scheduling jobs on a single machine is considered. It is assumed that the jobs are classified into several groups and the jobs of the same group have to be processed contiguously. A sequence independent set-up time is incurred between each two consecutively scheduled groups. A schedule is specified by a sequence for the groups and a sequence for the jobs in each group. The quality of a schedule is measured by two critera ordered by their relative importance. The objective is to minimize the maximum cost, the secondary criterion, subject to the schedule is optimal with respect to total weighted completion time, the primary criterion. A polynomial time algorithm is presented to solve this bicriterion group scheduling problem. It is shown that this algorithm can also be modified to solve the single machine group scheduling problem with several ordered maximum cost criteria and arbitrary precedence constraints.     

Single machine group scheduling with resource dependent setup and processing times

A single machine scheduling problem is studied. There is a partition of the set of n jobs into g groups on the basis of group technology. Jobs of the same group are processed contiguously. A sequence independent setup time precedes the processing of each group. Two external renewable resources can be used to linearly compress setup and job processing times. The setup times are jointly compressible by one resource, the job processing times are jointly compressible by another resource and the level of the resource is the same for all setups and all jobs. Polynomial time algorithms are presented to find an optimal job sequence and resource values such that the total weighted resource consumption is minimum, subject to meeting job deadlines. The algorithms are based on solving linear programming problems with two variables by geometric techniques.     

An Ant Colony Optimization Algorithm for Shop Scheduling Problems

We deal with the application of ant colony optimization to group shop scheduling, which is a general shop scheduling problem that includes, among others, the open shop scheduling problem and the job shop scheduling problem as special cases. The contributions of this paper are twofold. First, we propose a neighborhood structure for this problem by extending the well-known neighborhood structure derived by Nowicki and Smutnicki for the job shop scheduling problem. Then, we develop an ant colony optimization approach, which uses a strong non-delay guidance for constructing solutions and which employs black-box local search procedures to improve the constructed solutions. We compare this algorithm to an adaptation of the tabu search by Nowicki and Smutnicki to group shop scheduling. Despite its general nature, our algorithm works particularly well when applied to open shop scheduling instances, where it improves the best known solutions for 15 of the 28 tested instances. Moreover, our algorithm is the first competitive ant colony optimization approach for job shop scheduling instances.     

需要安装时间的平行多功能机排序问题的启发式算法

考虑需要安装时间的平行多功能机排序问题。在该模型中,每个工件对应机器集合的一个子集,其只能在这个子集中的任一台机器上加工,称这个子集为该工件的加工集合;工件分组,同组工件具有相同的加工时间和加工集合,不同组中的工件在同一台机器上连续加工需要安装时间,目标函数为极小化最大完工时间。对该问题NP-难的一般情况设计启发式算法:首先按照特定的规则将所有工件组都整组地安排到各台机器上,然后通过在各机器间转移工件不断改进当前最大完工时间。通过与下界的比较检验算法的性能,大量的计算实验表明,算法是实用而有效的。     

工件具有子工件工期的排序问题

研究了工件具有子工件工期的排序问题.需要在一台单机上加工若干个给定的工件.每个工件由若干个子工件组成,每个子工件都有各自的工期.只有当工件的每个子工件都按时完成,才能称该工件是按时完工工件,否则,称该工件产生延误.目标是最大化按时完工的工件个数.证明当每个工件都被分成两个子工件时,该问题是NP-难的,而且不存在完全多项式时间近似方案(fully polynomial time approximation scheme,简记为FPTAS).提出两个启发式算法,利用数值模拟比较它们的性能,并且将这两个启发式算法的解与最优解的上界进行比较.     

An iterative approach for the serial batching problem with parallel machines and job families

In this paper, we consider a parallel machine scheduling problem to minimize the total completion time. Each job belongs to a certain family. All jobs of one family have identical processing times. Major setups occur between jobs of different families, and we include sequence dependencies. Batches of jobs belonging to the same family can be formed to avoid these setups. Furthermore, we assume serial batching and batch availability. Therefore, the processing time of a batch is the sum of the processing times of all jobs grouped into the corresponding batch. An iterative method is developed for solving this specific problem. This approach alternates between varying batch sizes using an efficient heuristic and sequencing batches based on variable neighborhood search (VNS). Computational results demonstrate that the iterative heuristic outperforms heuristics based on a fixed batch size and list scheduling.     

Resource-constrained job scheduling with recyclable resources

In resource-constrained project scheduling problems, resources are typically classified as being either renewable, non-renewable, or doubly-constrained. A new resource classification, recyclable, is introduced. Notation and a generalized problem formulation are developed for resource-constrained job scheduling problems where resources are recyclable. This foundation is then used for studying the single-machine scheduling problem with tooling constraints. For a given set of jobs, the problem is to find the job sequence, tool type quantities, and tool recycling schedule such that the sum of job completion times and quantity of tools allocated are both minimized. Two solution approaches are developed, and examples are used to compare and contrast the approaches. The results indicate that the ‘traditional’ job scheduling approach (i.e. schedule jobs first, then tools) can lead to sub-optimal solutions. Furthermore, by scheduling jobs and tools simultaneously, it may be possible to attain a given level of performance with fewer tools.     

Solving the serial batching problem in job shop manufacturing systems

This paper addresses the serial batch scheduling problem embedded in a job shop environment to minimize makespan. Sequence dependent family setup times and a job availability assumption are also taken into account. In consideration of batching decisions, we propose a tabu search algorithm which consists of various neighborhood functions, multiple tabu lists and a sophisticated diversification structure. Computational experiments show that our algorithm outperforms a well-known tabu search approach which is developed for solving the traditional job shop problem. These results also confirm the benefits of batching.     

带有退化效应和序列相关运输时间的排序问题

考虑带有退化效应和序列相关运输时间的单机排序问题. 工件的加工时间是其开工时间的简单线性增加函数. 当机器单个加工工件时, 极小化最大完工时间、(加权)总完工时间和总延迟问题被证明是多项式可解的, EDD序对于极小化最大延迟问题不是最优排序, 另外, 就交货期和退化率一致情形给出了一最优算法. 当机器可分批加工工件时, 分别就极小化最大完工时间和加权总完工时间问题提出了多项式时间最优算法.     

Computing lower and upper bounds for a large-scale industrial job shop scheduling problem

In this paper we present a case study from the lighting industry concerned with the scheduling of a set of job families each representing the production of a particular end-item in a given quantity. It is a job shop type problem, where each job family has a number of routing alternatives, and the solution has to respect batching and machine availability constraints. All jobs of the same job family have a common release date and a common due date, and they differ only in size. The objective is to minimize the total tardiness of the job families, rather than that of individual jobs. We propose a two-phase method based on solving a mixed-integer linear program and then improving the initial solution by tabu search. We evaluate our method on real-world as well as generated instances.     

同时具有学习效应和退化效应的单机排序问题

本文给出了一种同时具有一般化学习效应和退化效应的单机排序模型。在此模型中,工件的实际加工时间既与工件所在位置又与其开工时间有关,且工件在加工之后具有一个配送时间。其中学习效应是工件所在位置的函数,退化效应是工件开工时间的函数。证明了极小化最大完工时间和极小化总完工时间问题是多项式可解的,在满足一定的条件下,极小化加权总完工时间和极小化最大延误问题也是多项式可解的。推广了一些已有文献中的结论。     

Multi-family scheduling in a two-machine reentrant flow shop with setups

This paper considers a two-machine multi-family scheduling problem with reentrant production flows. The problem consists of two machines, M₁ and M₂, and each job has the processing route (M₁, M₂, M₁, M₂). There are identical jobs in the same family and the jobs in the same family are processed in succession. Each machine needs a setup time before the first job in a family is processed. The objective is to minimize the maximum completion time. Examples of such a problem occur in the bridge construction, semiconductor industry and job processing on numerical controlled machines, where they usually require that the jobs are reprocessed once and there are identical jobs in the same family. This problem is shown to be NP-hard. A branch-and-bound algorithm is proposed, and computational experiments are provided.     

Isomorphic scheduling problems

We consider general properties of isomorphic scheduling problems that constitute a new class of pairs of mutually related scheduling problems. Any such a pair is composed of a scheduling problem with fixed job processing times and its time-dependent counterpart with processing times that are proportional-linear functions of the job starting times. In order to introduce the class formally, first we formulate a generic scheduling problem with fixed job processing times and define isomorphic problems by a one-to-one transformation of instances of the generic problem into instances of time-dependent scheduling problems with proportional-linear job processing times. Next, we prove basic properties of isomorphic scheduling problems and show how to convert polynomial algorithms for scheduling problems with fixed job processing times into polynomial algorithms for proportional-linear counterparts of the original problems. Finally, we show how are related approximation algorithms for isomorphic problems. Applying the results, we establish new worst-case results for time-dependent parallel-machine scheduling problems and prove that many single- and dedicated-machine time-dependent scheduling problems with proportional-linear job processing times are polynomially solvable.