订单带多工类工件时的极小迟后范围问题

本文考虑下述由多工类工件组成的订单的单机排序问题：每一个客户提供一个由若干工件组成的订单,总共n个工件又分成k个类．当机器从加工某类中的工件转向加工不同于它的第i类工件时,需一调整时间si．每一订单有一给定的应交工时间,订单的完工时间定义为该定单所含全部工件完工时的时间．我们希望适当排列这n个工件,使得订单的迟后范围最小．相应这一排序问题,文中依不同的背景给出了以下二种模式：同类工件一起连续加工,工件的完工时间为其所属类中全部工件完工时的时间,用GT,Ba来表示；同类工件一起连续加工,工件的完工时间为其本身的完工时间,用GT,Ja来表示．对于这两种模式的排序同题,我们均证明了其NP-hard性并给出了对应的分枝定界算法．     

Column generation heuristics for multiple machine, multiple orders per job scheduling problems

Front opening unified pods (FOUPs) are used to store and transport silicon wafers in 300-mm semiconductor wafer fabs. To achieve production efficiencies, wafers are grouped together in FOUPs without regard to the originating customer placing the order. In the resulting multiple orders per job (moj) scheduling problem, scheduling is performed at the FOUP (i.e., aggregated order) level, while scheduling performance is assessed per individual customer order. Column generation heuristics are presented for single and parallel machine moj scheduling problems to minimize total weighted order completion time. The proposed heuristics obtain near-optimal solutions very quickly, outperforming competing approaches in the literature.     

Precedence constrained parallel-machine scheduling of position-dependent jobs

We consider parallel-machine job scheduling problems with precedence constraints. Job processing times are variable and depend on positions of jobs in a schedule. The objective is to minimize the maximum completion time or the total weighted completion time. We specify certain conditions under which the problem can be solved by scheduling algorithms applied earlier for fixed job processing times.     

A combined approach for two-agent scheduling with sum-of-processing-times-based learning effect

This paper considers a scheduling model involving two agents, job release times, and the sum-of-processing-times-based learning effect. The sum-of-processing-times-based learning effect means that the actual processing time of a job of either agent is a decreasing function of the sum of the processing times of the jobs already scheduled in a given schedule. The goal is to seek for an optimal schedule that minimizes the total weighted completion time of the first agent, subject to no tardy job for the second agent. We first provide a branch-and-bound method to solve the problem. We then develop an approach that combines genetic algorithm and simulated annealing to seek for approximate solutions for the problem. We carry on extensive computational tests to assess the performance of the proposed algorithms.     

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

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

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.     

Some single-machine scheduling with sum-of-processing-time-based and job-position-based processing times

The single-machine scheduling problems with position and sum-of-processing-time based processing times are considered. The actual processing time of a job is defined by function of its scheduled position and total normal processing time of jobs in front of it in the sequence. We provide optimal solutions in polynomial time for some special cases of the makespan minimization and the total completion time minimization. We also show that an optimal schedule to be a V-shaped schedule in terms of the normal processing times of jobs for the total completion time minimization problem and the makespan minimization problem.     

The wafer probing scheduling problem (WPSP)

The wafer probing scheduling problem (WPSP) is a variation of the parallel-machine scheduling problem, which has many real-world applications, particularly, in the integrated circuit (IC) manufacturing industry. In the wafer probing factories, the jobs are clustered by their product types, which must be processed on groups of identical parallel machines and be completed before the due dates. Further, the job processing time depends on the product type, and the machine setup time is sequence dependent on the orders of jobs processed. Since the wafer probing scheduling problem involves constraints on job clusters, job-cluster dependent processing time, due dates, machine capacity, and sequence dependent setup time, it is more difficult to solve than the classical parallel-machine scheduling problem. In this paper, we formulate the WPSP as an integer programming problem. We also transform the WPSP into the vehicle routing problem with time windows (VRPTW), a well-known network routing problem which has been investigated extensively. An illustrative example is given to demonstrate the proposed transformation. Based on the provided transformation, we present three efficient algorithms to solve the WPSP near-optimally.     

Preemptive scheduling of equal length jobs with release dates on two uniform parallel machines

We consider a problem of scheduling n jobs on two uniform parallel machines. For each job we are given its release date when the job becomes available for processing. All jobs have equal processing requirements. Preemptions are allowed. The objective is to find a schedule minimizing total completion time. We suggest an O(n³) algorithm to solve this problem.     

安装、加工和拆卸时间分离的两台机器混合作业问题

混合作业是经典的自由作业和异序作业的一种综合,其中一些工件可以按任意的机器顺序进行处理,而另一些工件必须遵守预先指定的机器顺序.本文研究安装、加工和拆卸时间分离的两台机器混合作业排序问题,该问题已经被知道是强NP困难的,本文把流水作业中的同顺序作业概念推广到混合作业,并得到这个混合作业问题在同顺序意义下的最优解,这个解对于一般情形是3/2近似解,但对于一些有意义的特殊情形是整体最优的.     

Two-agent scheduling with position-based deteriorating jobs and learning effects

Scheduling with deteriorating jobs and learning effects has been widely studied. However, multi-agent scheduling with simultaneous considerations of deteriorating jobs and learning effects has hardly been considered until now. In view of this, we consider a two-agent single-machine scheduling problem involving deteriorating jobs and learning effects simultaneously. In the proposed model, given a schedule, we assume that the actual processing time of a job of the first agent is a function of position-based learning while the actual processing time of a job of the second agent is a function of position-based deterioration. The objective is to minimize the total weighted completion time of the jobs of the first agent with the restriction that no tardy job is allowed for the second agent. We develop a branch-and-bound and several simulated annealing algorithms to solve the problem. Computational results show that the proposed algorithms are efficient in producing near-optimal solutions.     

Two-parallel machines scheduling with rate-modifying activities to minimize total completion time

This paper considers the two-parallel machines scheduling problem with rate-modifying activities. In this model, each machine has a rate-modifying activity that can change the processing rate of machine under consideration. Hence the actual processing times of jobs vary depending on whether the job is scheduled before or after the rate-modifying activity. We need to make a decision on when to schedule the rate-modifying activities and the sequence of jobs to minimize some objective function. We provide polynomial and pseudo-polynomial time algorithms to solve the total completion time minimization problem and total weighted completion time minimization problem under agreeable ratio condition.     

Generalized Pinwheel Problem

This paper studies a non-preemptive infinite-horizon scheduling problem with a single server and a fixed set of recurring jobs. Each job is characterized by two given positive numbers: job duration and maximum allowable time between the job completion and its next start. We show that for a feasible problem there exists a periodic schedule. We also provide necessary conditions for the feasibility, formulate an algorithm based on dynamic programming, and, since this problem is NP-hard, formulate and study heuristic algorithms. In particular, by applying the theory of Markov Decision Process, we establish natural necessary conditions for feasibility and develop heuristics, called frequency based algorithms, that outperform standard scheduling heuristics.     

An approximation algorithm for parallel machine scheduling with a common server

In this paper we study the scheduling of a given set of jobs on several identical parallel machines tended by a common server. Each job must be processed on one of the machines. Prior to processing, the server has to set up the relevant machine. The objective is to schedule the jobs so as to minimize the total weighted job completion times. We provide an approximation algorithm to tackle this intractable problem and analyze the worst-case performance of the algorithm for the general, as well as a special, case of the problem.     

Multi-objective genetic algorithm for single machine scheduling problem under fuzziness

This paper presents a new multi-objective approach to a single machine scheduling problem in the presence of uncertainty. The uncertain parameters under consideration are due dates of jobs. They are modelled by fuzzy sets where membership degrees represent decision maker’s satisfaction grade with respect to the jobs’ completion times. The two objectives defined are to minimise the maximum and the average tardiness of the jobs. Due to fuzziness in the due dates, the two objectives become fuzzy too. In order to find a job schedule that maximises the aggregated satisfaction grade of the objectives, a hybrid algorithm that combines a multi-objective genetic algorithm with local search is developed. The algorithm is applied to solve a real-life problem of a manufacturing pottery company.     

Coordination mechanisms with hybrid local policies

We study coordination mechanisms for scheduling n jobs on m parallel machines where agents representing the jobs interact to generate a schedule. Each agent acts selfishly to minimize the completion time of his/her own job, without considering the overall system performance that is measured by a central objective. The performance deterioration due to the lack of a central coordination, the so-called price of anarchy, is determined by the maximum ratio of the central objective function value of an equilibrium schedule divided by the optimal value. In the first part of the paper, we consider a mixed local policy with some machines using the SPT rule and other machines using the LPT rule. We obtain the exact price of anarchy for the problem of minimizing the makespan and some bounds for the problem of minimizing the total completion time. In the second part of the paper, we consider parallel machine scheduling subject to eligibility constraints. We devise new local policies based on the flexibilities and the processing times of the jobs. We show that the newly devised local policies outperform both the SPT and the LPT rules.     

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.     

Some single-machine scheduling problems with actual time and position dependent learning effects

In this paper we study some single-machine scheduling problems with learning effects where the actual processing time of a job serves as a function of the total actual processing times of the jobs already processed and of its scheduled position. We show by examples that the optimal schedules for the classical version of problems are not optimal under this actual time and position dependent learning effect model for the following objectives: makespan, sum of kth power of the completion times, total weighted completion times, maximum lateness and number of tardy jobs. But under certain conditions, we show that the shortest processing time (SPT) rule, the weighted shortest processing time (WSPT) rule, the earliest due date (EDD) rule and the modified Moore’s Algorithm can also construct an optimal schedule for the problem of minimizing these objective functions, respectively.     

Complexity of the job insertion problem in multi-stage scheduling

The job insertion problem in multi-stage scheduling is: given a schedule for n jobs and an additional job, find a feasible insertion of the additional job into the schedule that minimizes the resulting makespan. We prove that finding the optimal job insertion is NP-hard for flow shops and open shops.     

Single-machine scheduling with nonlinear deterioration

In this paper, we consider the single-machine scheduling problems with nonlinear deterioration. By the nonlinear deterioration effect, we mean that the processing times of jobs are nonlinear functions of their starting times. We show that even with the introduction of nonlinear deterioration to job processing times, single machine makespan minimization problem remains polynomially solvable. We also show that an optimal schedule of the total completion time minimization problem is V-shaped with respect to job normal processing times. A heuristic algorithm utilizing the V-shaped property is proposed, and computational experiments show that it performs effectively and efficiently in obtaining near-optimal solutions.