Single machine scheduling with general job-dependent aging effect and maintenance activities to minimize makespan

This paper considers single machine scheduling with an aging effect in which the processing time of a job depends on its position in a sequence. It is assumed that aging ratios are job-dependent and machine can be maintained some times in a schedule. After a maintenance activity, machine will be restored to its initial condition. The processing of jobs and the maintenance activities of machine are scheduled simultaneously. The objective is to schedule the jobs and the maintenance activities, so as to minimize the makespan. We provide a polynomial time algorithm to solve the problem.     

Minimizing total flow time in the single-machine scheduling problem with periodic maintenance

This paper deals with a single-machine scheduling problem with limited machine availability. The limited availability of machine results from periodic maintenance activities. In our research, a periodic maintenance schedule consists of several maintenance periods. Each maintenance period is scheduled after a periodic time interval. The objective is to find a schedule that minimizes the total flow time subject to periodic maintenance and nonresumable jobs. Some important theorems are proved for the problem. A branch-and-bound algorithm that utilizes several theorems is proposed to find the optimal schedule. We also develop a heuristic to solve large sized problems. In this paper, computational results show that the proposed heuristic is highly accurate and efficient.     

Order acceptance and due-date quotation in low machine rates

In real manufacturing environments, some customer orders include multiple jobs. However, a single due-date should be assigned to each order. Further, machine processing rate is not constant at all times. In effect, in many manufacturing operations, the machine processing rate decreases to a subnormal level during time and needs a special type of maintenance to bring the normal state back. Due to this reduction in capacity, production schedulers may decide to reject some orders. In this paper, the novel extensive problem of selecting a subset of orders, assigning due-dates to selected orders, scheduling the selected orders and jobs within each one, and scheduling the rate-modifying maintenance is studied. The objective function is minimizing total cost of lost-sales of rejected orders together with due-date length and maximum of earliness and tardiness of selected orders. The problem is proved polynomial and an optimal approach is developed.     

Scheduling a single machine with multiple job processing ability to minimize makespan

This paper investigates a new problem, called single machine scheduling with multiple job processing ability, which is derived from the production of the continuous walking beaming reheating furnace in iron and steel industry. In this problem, there is no batch and the jobs enter and leave the machine one by one and continuously, which is different from general single machine batch scheduling problem where the jobs in a batch share the same start and departure time. Therefore, the start time and the departure time of a job depend on not only the job sequence but also the machine capacity. This problem is also different from the single semi-continuous batching machine scheduling recently studied in the literature, where the jobs are processed in batch mode and a new batch cannot be started for processing until the processing of the previous batch is completed though jobs in the same batch enter and leave the machine one by one. The objective of this problem is to minimize the makespan. We formulate this problem as a mixed integer linear programming model and propose a particle swarm optimization (PSO) algorithm for this problem. Computational results on randomly generated instances show that the proposed PSO algorithm is effective.     

Single machine scheduling to minimize weighted earliness subject to no tardy jobs

This paper considers the single machine scheduling problem where the objective is to minimize the total weighted earliness subject to no tardy jobs. Known results for a well researched single machine scheduling problem where the objective is to minimize the weighted completion time subject to no tardy jobs have been used in analyzing this problem. Several important results are proved and both exact and approximate methods are developed to solve this problem.     

Parallel machines scheduling with a deteriorating maintenance activity

In this paper, we consider parallel identical machines scheduling problems with a deteriorating maintenance activity. In this model, each machine has a deteriorating maintenance activity, that is, delaying the maintenance increases the time required to perform it. We need to make a decision on when to schedule the deteriorating maintenance activities and the sequence of jobs to minimize total completion time. We provide a polynomial time algorithm to solve the total completion time minimization problem.     

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

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

工期窗口安排与具有退化效应和维修活动的单机排序

考虑具有工件相关的退化效应和维修活动的单机排序模型,讨论了工期窗口安排问题.在这一模型中,机器在加工过程中产生退化使效率降低,工件的实际加工时间不仅与其所在排序中的位置有关并且与其本身的退化率有关;然而,维修活动能使机器的加工效率得到恢复.工期窗口的开始时间是已给定的常量,而工期窗口的结束时间是需要确定的变量.目标是得到安排维修活动的最佳时间、最佳工期窗口的大小和最优排序以便最小化流时间、提早、延误和工期窗口大小的总处罚函数.对这一问题,给出了一多项式算法.     

Joint production and preventive maintenance scheduling for a single degraded machine by considering machine failures

Production scheduling and maintenance planning are two interdependent issues that most often have been investigated independently. Although both preventive maintenance (PM) and minimal repair affect availability and failure rate of a machine, only a few researchers have considered this interdependency in the literature. Furthermore, most of the existing joint production and preventive maintenance scheduling methods assume that machine is available during the planning horizon and consider only a possible level for PM. In this research, an integrated model is proposed that coordinates preventive maintenance planning with single-machine scheduling to minimize the weighted completion time of jobs and maintenance cost, simultaneously. This paper not only considers multiple PM levels with different costs, times and reductions in the hazard rate of the machine, but also assumes that a machine failure may occur at any time. To illustrate the effectiveness of the suggested method, it is compared to two situations of no PM and a single PM level. Eventually, to tackle the suggested problem, multi-objective particle swarm optimization and non-dominated sorting genetic algorithm (NSGA-II) are employed and their parameters are tuned Furthermore, their performances are compared in terms of three metrics criteria.     

具有退化工件和老化效应的单机可拒绝排序问题

研究同时具有退化工件和老化效应的单机可拒绝排序问题,即工件的实际加工时间是与其开工时间和所在位置有关的函数,同时生产商可以通过支付一定的处罚费用而拒绝加工某些工件。在生产加工过程中,考虑对机器进行选择性维修活动来提高加工的效率;机器进行维修活动后将恢复到初始状态,老化效应也将重新开始。目标是确定拒绝哪些工件、何时进行维修活动以及接受工件集中工件的次序,以便极小化接受加工工件的最大完工时间与拒绝加工工件总处罚费用的和。证明得到了所研究的问题是NP-难解的,并给出了解决问题的一个全多项式时间近似方案(FPTAS)算法。     

Single machine scheduling problem with two synergetic agents and piece-rate maintenance

This paper attempts to study on the single machine scheduling problems with two synergetic agents, each has a set of nonpreemptive jobs and a regular objective function depending on the completion times of its jobs only. It is not only necessary to satisfy the constraints of each agents objective function, it is necessary to minimize an aggregate increasing objective function of two agents’ objective function. Furthermore, this paper proposes a new kind of machine maintenance: piece-rate maintenance, which depicts the scenario that machine maintenance is implemented once every a fixed number of jobs is completed. Hence, it explores into the single machine scheduling problems with two synergetic agents and piece-rate maintenance. If the regular objective function of each job is polynomial, it can be observed that these problems are all polynomially solvable.     

On scheduling an unbounded batch machine

A batch machine is a machine that can process up to c jobs simultaneously as a batch, and the processing time of the batch is equal to the longest processing time of the jobs assigned to it. In this paper, we deal with the complexity of scheduling an unbounded batch machine, i.e., c=+∞. We prove that minimizing total tardiness is binary NP-hard, which has been an open problem in the literature. Also, we establish the pseudopolynomial solvability of the unbounded batch machine scheduling problem with job release dates and any regular objective. This is distinct from the bounded batch machine and the classical single machine scheduling problems, most of which with different release dates are unary NP-hard. Combined with the existing results, this paper provides a nearly complete mapping of the complexity of scheduling an unbounded batch machine.     

一类变工时的单机排序问题

提出了一类可变加工时间的单台机器排序问题,着重考虑如下的目标函数：最小化工件排序长度、完工时间之和误工工件数等等,且用受束的等规模划分问题证明了可变加工时间的单台机器排序问题是ＮＰ－完全的。     

A hybrid genetic algorithm for an identical parallel-machine problem with maintenance activity

The scheduling of maintenance activities has been extensively studied, with most studies focusing on single-machine problems. In real-world applications, however, multiple machines or assembly lines process numerous jobs simultaneously. In this paper, we study a parallel-machine scheduling problem in which the objective is to minimize the total tardiness given that there is a maintenance activity on each machine. We develop a branch-and-bound algorithm to solve the problem with a small problem size. In addition, we propose a hybrid genetic algorithm to obtain the approximate solutions when the number of jobs is large. The performance of the proposed algorithms is evaluated based mainly on computational results.     

Single machine unbounded parallel-batch scheduling with forbidden intervals

In this paper we consider the single machine parallel-batch scheduling with forbidden intervals. There are some forbidden intervals in which the machine cannot be available. The jobs are processed in batches form in the remaining free time-slots without preemption, where the processing time of a batch is defined to be the maximum processing time of the jobs in this batch. We show that, when the objective is bottleneck form, maximum lateness, or makespan with release dates of jobs, the considered problem can be solved in polynomial time.     

Scheduling a deteriorating maintenance activity on a single machine

We study a problem of scheduling a maintenance activity on a single machine. Following several recent papers, the maintenance is assumed to be deteriorating, that is, delaying the maintenance increases the time required to perform it. The following objective functions are considered: makespan, flowtime, maximum lateness, total earliness, tardiness and due-date cost, and number of tardy jobs. We introduce polynomial time solutions for all these problems.     

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.     

具有两个不相容工件族单位工件的有界分批在线排序问题

研究具有两个不相容工件族单位工件单机有界平行分批的在线排序问题.工件按时在线到达,目标是最小化最大完工时间.在有界平行分批排序中,容量有限制机器最多可将b个工件形成一批同时加工,每个工件及每一批的加工时间为1.不相容工件族是指来自不同工件组的工件不能放在同一批加工.对该问题提供了一个竞争比为√17+3/4的最好可能的在线算法.     

Single-machine scheduling with maintenance and repair rate-modifying activities

Most papers in the scheduling field are based on the assumption that machines are always available at constant speed. However, in industry applications, it is very common for a machine to be in subnormal condition after running for a certain period of time. Motivated by a problem commonly found in the surface-mount technology of electronic assembly lines, this paper deals with scheduling problems involving repair and maintenance rate-modifying activities. When a machine is running at less than an efficient speed, a production planner can decide to stop the machine and maintain it or wait and maintain it later. If the choice is made to continue running the machine without fixing it, it is possible that the machine will break down and repair will be required immediately. Both maintenance and repair activities can change the machine speed from a sub-normal production rate to a normal one. Hence, we call them rate-modifying activities. Our purpose here is to simultaneously sequence jobs and schedule maintenance activity to optimize regular performance measures. In this paper, we assume that processing time is deterministic, while machine break down is a random process following certain distributions. We consider two types of processing cases: resumable and nonresumable. We study problems with objective functions such as expected makespan, total expected completion time, maximum expected lateness, and expected maximum lateness, respectively. Several interesting results are obtained, especially for the nonresumable case.     

工作有到达时间且拒绝工件总个数受限的单机平行分批排序问题的近似算法

考虑了工件有到达时间且拒绝工件总个数不超过某个给定值的单机平行分批排序问题.在该问题中,给定一个工件集和一台可以进行批处理加工的机器.每个工件有它的到达时间和加工时间;对于每个工件来说要么被拒绝要么被接受安排在机器的某一个批次里进行加工;一个工件如果被拒绝,则需支付该工件对应的拒绝费用.为了保证一定的服务水平,要求拒绝工件的总个数不超过给定值.目标是如何安排被接受工件的加工批次和加工次序使得其最大完工时间与被拒绝工件的总拒绝费用之和最小.该问题是NP-难的,对此给出了伪多项式时间动态规划精确算法,2-近似算法和完全多项式时间近似方案.