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.     

有关单机两代理排序问题的两个结果

研究了两个单机两代理排序问题. 在第一个两代理排序问题中, 代理A的目标函数为极小化所有工件的加权完工时间总和, 代理B的目标函数为极小化最大工件费用. 在第二个两代理排序问题中, 代理A的目标函数为极小化所有工件的加权完工时间总和, 代理B的目标函数为极小化所有工件的最大完工时间. 证明了第一个问题是强NP-难的, 改进了已有的一般意义NP-难的结果; 对第二个问题给出了一个与现有的动态规划算法不同的动态规划算法.     

Polynomial time solutions for scheduling problems on a proportionate flowshop with two competing agents

In scheduling problems with two competing agents, each one of the agents has his own set of jobs and his own objective function, but both share the same processor. The goal is to minimize the value of the objective function of one agent, subject to an upper bound on the value of the objective function of the second agent. In this paper we study two-agent scheduling problems on a proportionate flowshop. Three objective functions of the first agent are considered: minimum maximum cost of all the jobs, minimum total completion time, and minimum number of tardy jobs. For the second agent, an upper bound on the maximum allowable cost is assumed. We introduce efficient polynomial time solution algorithms for all cases.     

Two-agent single-machine scheduling problems under increasing linear deterioration

A new scheduling model in which both two-agent and increasing linear deterioration exist simultaneously is investigated in this paper. The processing time of a job is defined as an increasing linear function of its starting time. Two agents compete to perform their respective jobs on a common single machine and each agent has his own criterion to optimize. We introduce an increasing linear deterioration model into the two-agent single-machine scheduling, where the goal is to minimize the objective function of the first agent with the restriction that the objective function of the second agent cannot exceed a given upper bound. We study two scheduling problems with the different combinations of two agents’ objective functions: makespan, maximum lateness, maximum cost and total completion time. We propose the optimal properties and present the optimal polynomial time algorithms to solve the scheduling problems, respectively.     

Total tardiness minimization in permutation flowshop with deterioration consideration

In this paper, we consider a permutation flowshop scheduling problem with deteriorating jobs. The objective is to minimize the total tardiness of all jobs. A branch-and-bound algorithm incorporating with a dominance property and a lower bound is developed. Furthermore, two metaheuristic algorithms, the simulated annealing algorithm, and the particle swarm optimization method, are proposed. Finally, computational studies are given.     

Scheduling with deteriorating jobs and learning effects

This paper studies a single machine scheduling problem simultaneously with deteriorating jobs and learning effects. The objectives are to minimize the makespan and the number of tardy jobs, respectively. Two polynomial time algorithms are proposed to solve these problems optimally.     

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 scheduling with family setups to minimize total earliness and tardiness

This paper considers the problem of scheduling a given number of jobs on a single machine to minimize total earliness and tardiness when family setup times exist. The paper proposes optimal branch-and-bound algorithms for both the group technology assumption and if the group technology assumption is removed. A heuristic algorithm is proposed to solve larger problems with the group technology assumption removed. The proposed algorithms were empirically evaluated on problems of various sizes and parameters. The paper also explores how the choice of procedure affects total earliness and tardiness if an implementation of lean production methods has resulted in a reduction in setup times. An important finding of these empirical investigations is that scheduling jobs by removing the group technology assumption can significantly reduce total earliness and tardiness.     

Rescheduling problems with deteriorating jobs under disruptions

In this paper, we consider two single-machine rescheduling problems with linear deteriorating jobs under disruption. By a deteriorating jobs, we mean that the actual processing time of the job is an increasing function of its starting time. The two problems correspond to two different increasing linear function. Rescheduling means a set of original jobs has already been scheduled to minimize some classical objective, then a new set of jobs arrives and creates a disruption. We consider the rescheduling problem to minimize the total completion time under a limit of the disruption from the original scheduling. For each problem, we consider two versions. For each version, the polynomial algorithms are proposed, respectively.     

Considerations of single-machine scheduling with deteriorating jobs

This paper considers some scheduling problems with deteriorating jobs. The objectives are to minimize the makespan, the total completion time, the total absolute deviation of completion time, the earliness, tardiness, and due date penalty, the sum of earliness penalties subject to no tardy jobs, respectively. We also explore two resource constrained scheduling problems: how to minimize the resource consumption with makespan constraints and how to minimize the makespan with the total resource consumption constraints. Several polynomial time algorithms are proposed to optimally solve the problems with the above objective functions.     

A note on two-agent scheduling on an unbounded parallel-batching machine with makespan and maximum lateness objectives

This paper studies the two-agent scheduling on an unbounded parallel-batching machine. In the problem, there are two agents A and B with each having their own job sets. The jobs of a common agent can be processed in a common batch. Moreover, each agent has an objective function to be minimized. The objective function of agent A is the makespan of his jobs and the objective function of agent B is maximum lateness of his jobs. Yazdani Sabouni and Jolai [M.T. Yazdani Sabouni, F. Jolai, Optimal methods for batch processing problem with makespan and maximum lateness objectives, Appl. Math. Model. 34 (2010) 314–324] presented a polynomial-time algorithm for the problem to minimize a positive combination of the two agents’ objective functions. Unfortunately, their algorithm is incorrect. We then dwell on the problem and present a polynomial-time algorithm for finding all Pareto optimal solutions of this two-agent parallel-batching scheduling problem.     

Group sequencing around a common due date

The problem of scheduling groups of jobs on a single machine under the group technology assumption is studied. Jobs of the same group are processed contiguously and a sequence independent setup time precedes the processing of each group. All jobs have a common fixed due date, which can be either unrestrictively large or restrictively small. The objective is to minimize the total weighted earliness–tardiness. Properties of optimal solutions are established, and dynamic programming algorithms are derived to solve several special cases of this problem. Computational experiments show that the algorithms can easily solve problems with 500 groups of jobs and each group has 10 to 50 jobs on a standard PC.     

Meta-heuristic approaches for minimizing total earliness and tardiness penalties of single-machine scheduling with a common due date

This study addresses a class of single-machine scheduling problems involving a common due date where the objective is to minimize the total job earliness and tardiness penalties. A genetic algorithm (GA) approach and a simulated annealing (SA) approach utilizing a greedy local search and three well-known properties in the area of common due date scheduling are developed. The developed algorithms enable the starting time of the first job not at zero and were tested using a set of benchmark problems. From the viewpoints of solution quality and computational expenses, the proposed approaches are efficient and effective for problems involving different numbers of jobs, as well as different processing time, and earliness and tardiness penalties.     

同时最小化最大费用和最大完工时间的双代理无界平行分批排序

有两个代理A和B, 每个代理都各自有一个工件集. 同一个代理的工件可以在同一批中加工, 而且每一个代理都有一个需要最小化的函数. 研究在无界平行分批处理机上同时最小化代理A的最大费用和代理B的最大完工时间问题, 并给出一个算法, 它可在多项式时间内找到关于这个问题的所有Pareto最优点.     

Minimizing flow time in a flow-line manufacturing cell with family setup times

This paper considers the problem of scheduling part families and jobs within each part family in a flowline manufacturing cell with independent family setup times where parts (jobs) in each family are processed together. The objective is to minimize total flow time. A branch-and-bound algorithm capable of solving moderate sized problems is developed. Several heuristic algorithms are proposed and empirically evaluated as to their effectiveness and efficiency in finding optimal permutation schedules. These results show that several heuristic algorithms generate solutions that are better than those generated by an existing genetic algorithm.     

A scatter search algorithm for the distributed permutation flowshop scheduling problem

The distributed permutation flowshop problem has been recently proposed as a generalization of the regular flowshop setting where more than one factory is available to process jobs. Distributed manufacturing is a common situation for large enterprises that compete in a globalized market. The problem has two dimensions: assigning jobs to factories and scheduling the jobs assigned to each factory. Despite being recently introduced, this interesting scheduling problem has attracted attention and several heuristic and metaheuristic methods have been proposed in the literature. In this paper we present a scatter search (SS) method for this problem to optimize makespan. SS has seldom been explored for flowshop settings. In the proposed algorithm we employ some advanced techniques like a reference set made up of complete and partial solutions along with other features like restarts and local search. A comprehensive computational campaign including 10 existing algorithms, together with statistical analyses, shows that the proposed scatter search algorithm produces better results than existing algorithms by a significant margin. Moreover all 720 known best solutions for this problem are improved.     

Algorithms for the wafer probing scheduling problem with sequence-dependent set-up time and due date restrictions

In this paper, we consider the wafer probing scheduling problem (WPSP) to sequence families of jobs on identical parallel machines with due date restrictions. The machine set-up time is sequentially dependent on the product types of the jobs processed on the machine. The objective is to minimize the total machine workload without violating the machine capacity and job due date restrictions. The WPSP is a variation of the classical parallel-machine scheduling problem, that can be transformed into the vehicle-routing problem with time windows (VRPTW). One can therefore solve the WPSP efficiently using existing VRPTW algorithms. We apply four existing savings algorithms presented in the literature including sequential, parallel, generalized, and matching based savings, and develop three modifications called the modified sequential, the compound matching based, and the modified compound matching-based savings algorithms, to solve the WPSP. Based on the characteristics of the wafer probing process, a set of test problems is generated for testing purposes. Computational results show that the three proposed modified algorithms perform remarkably well.     

带有链优先序的分批排序问题

本文首次就带有优先序的分批排序问题进行了讨论，目标函数为最大完工时间．当优先序为链，一条链上的工件个数为饨，而其它链的工件个数为常数，分批的容量B大于等于链的条数，在这种情况下，问题为多项式可解的．文中并讨论了几种特殊情况的多项式算法．     

考虑部分工件不可打扰的多任务调度问题研究

多任务调度问题存在于各种应用领域,如因特网服务领域,医疗领域等。经典的多任务调度模型中所有工件均可被其他等待工件打扰,且仅打扰一次。然而在生产实践过程中,有些紧急工件是不允许被其他工件打扰。在此启发下,对原有模型进行扩展,研究了在单机多任务环境下部分工件不可打扰的调度问题,模型目标包括最小化最大完工时间,最小化总完工时间,最小化最大延迟以及最小化加权提前期、拖延期和共同交货期之和。对于前三个目标给出了精确算法,对于最后一个目标给出了启发式算法。最后,对今后的研究提出了建议。     

Single machine scheduling with truncated job-dependent learning effect

In this paper we consider the single machine scheduling problem with truncated job-dependent learning effect. By the truncated job-dependent learning effect, we mean that the actual job processing time is a function which depends not only on the job-dependent learning effect (i.e., the learning in the production process of some jobs to be faster than that of others) but also on a control parameter. The objectives are to minimize the makespan, the total completion time, the total absolute deviation of completion time, the earliness, tardiness and common (slack) due-date penalty, respectively. Several polynomial time algorithms are proposed to optimally solve the problems with the above objective functions.