Scheduling in dynamic assembly job-shops to minimize the sum of weighted earliness,weighted tardiness and weighted flowtime of jobs

In many manufacturing systems, jobs that are completed early are held as finished-goods inventory until their due-dates, and hence we incur earliness costs. Similarly, jobs that are completed after their due-dates incur penalty. The objective in such situations would, therefore, be to meet the due-dates of the respective jobs as closely as possible, and consequently minimize the sum of earliness and tardiness of jobs because earliness and tardiness of jobs greatly influence the performance of a schedule with respect to cost. In addition, a job incurs holding cost from the time of its arrival until its completion. Most studies on scheduling in such manufacturing systems assume unit earliness cost, unit tardiness cost and unit holding cost of a job. However, in reality such an assumption need not always hold and it is quite possible that there exist different costs of earliness, tardiness and holding for different jobs. In addition, most studies on job-shop scheduling assume that jobs are independent and that no assembly operations exist. The current study addresses the problem of scheduling in dynamic assembly job-shops (i.e. shops that manufacture multi-level jobs) with the consideration of jobs having different earliness, tardiness and holding costs. An attempt is made in this paper to present dispatching rules by incorporating the relative costs of earliness, tardiness and holding of jobs in the form of scalar weights. In the first phase of the study, relative costs (or weights for) earliness and tardiness of jobs are considered, and the dispatching rules are presented in order to minimize the sum of weighted earliness and weighted tardiness of jobs. In the second phase of the study, the objective considered is the minimization of the sum of weighted earliness, weighted tardiness and weighted flowtime of jobs, and the dispatching rules are presented by incorporating the relative costs of earliness, tardiness and flowtime of jobs. Simulation studies have been conducted separately for both phases of the current study, the performance of the scheduling rules have been observed independently, and the results of the simulation study have been reported. The proposed rules are found to be effective in minimizing the mean and maximum values of the measures of performance.     

Scheduling in dynamic assembly job-shops to minimize the sum of weighted earliness,weighted tardiness and weighted flowtime of jobs

In many manufacturing systems, jobs that are completed early are held as finished-goods inventory until their due-dates, and hence we incur earliness costs. Similarly, jobs that are completed after their due-dates incur penalty. The objective in such situations would, therefore, be to meet the due-dates of the respective jobs as closely as possible, and consequently minimize the sum of earliness and tardiness of jobs because earliness and tardiness of jobs greatly influence the performance of a schedule with respect to cost. In addition, a job incurs holding cost from the time of its arrival until its completion. Most studies on scheduling in such manufacturing systems assume unit earliness cost, unit tardiness cost and unit holding cost of a job. However, in reality such an assumption need not always hold and it is quite possible that there exist different costs of earliness, tardiness and holding for different jobs. In addition, most studies on job-shop scheduling assume that jobs are independent and that no assembly operations exist. The current study addresses the problem of scheduling in dynamic assembly job-shops (i.e. shops that manufacture multi-level jobs) with the consideration of jobs having different earliness, tardiness and holding costs. An attempt is made in this paper to present dispatching rules by incorporating the relative costs of earliness, tardiness and holding of jobs in the form of scalar weights. In the first phase of the study, relative costs (or weights for) earliness and tardiness of jobs are considered, and the dispatching rules are presented in order to minimize the sum of weighted earliness and weighted tardiness of jobs. In the second phase of the study, the objective considered is the minimization of the sum of weighted earliness, weighted tardiness and weighted flowtime of jobs, and the dispatching rules are presented by incorporating the relative costs of earliness, tardiness and flowtime of jobs. Simulation studies have been conducted separately for both phases of the current study, the performance of the scheduling rules have been observed independently, and the results of the simulation study have been reported. The proposed rules are found to be effective in minimizing the mean and maximum values of the measures of performance.     

Generating efficient points of bicriteria scheduling problem by using compromise programming

In this paper, we examine a bicriteria scheduling problem with objective of minimizing total tardiness and earliness vs mean flow time and also minimizing total tardiness vs total earliness. Since they have conflicting results we will use compromise programming in order to generate the efficient point     

解决并行多机提前/拖后调度问题的混合遗传算法方法

研究了带有公共交货期的并行多机提前/拖后调度问题.提出了一种混合遗传算法 方法,以便于确定公共交货期和每台机器上加工的任务代号及其加工顺序,即找到一个最优 公共交货期和最优调度,使加工完所有任务后交货期安排的成本、提前交货成本和拖后交货 成本的总和最小.数值计算结果表明了该混合遗传算法优于启发式算法,并能适用于较大规 模并行多机提前/拖后调度问题.算法计算量小,鲁棒性强.     

Genetic algorithms for the optimal common due date assignment and the optimal scheduling policy in parallel machine earliness/tardiness scheduling problems

Earliness/tardiness scheduling problems with undetermined common due date which have wide application background in textile industry, mechanical industry, electronic industry and so on, are very important in the research fields such as industry engineering and CIMS. In this paper, a kind of genetic algorithm based on sectional code for minimizing the total cost of assignment of due date, earliness and tardiness in this kind of scheduling problem is proposed to determine the optimal common due date and the optimal scheduling policy for determining the job number and their processing order on each machine. Also, simulated annealing mechanism and the iterative heuristic fine-tuning operator are introduced into the genetic algorithm so as to construct three kinds of hybrid genetic algorithms with good performance. Numerical computational results focusing on the identical parallel machine scheduling problem and the general parallel machine scheduling problem shows that these algorithms outperform heuristic procedures, and fit for larger scale parallel machine earliness/tardiness scheduling problem. Moreover, with practical application data from one of the largest cotton colored weaving enterprises in China, numerical computational results show that these genetic algorithms are effective and robust, and that especially the performance of the hybrid genetic algorithm based on simulated annealing and the iterative heuristic fine-tuning operator is the best among them.     

Benchmarks for scheduling on a single machine against restrictive and unrestrictive common due dates

We consider the NP-hard problem of scheduling jobs on a single machine against common due dates with respect to earliness and tardiness penalties. The paper covers two aspects: Firstly, we develop a problem generator and solve 280 instances with two new heuristics to obtain upper bounds on the optimal objective function value. Secondly, we demonstrate computationally that our heuristics are efficient in obtaining near-optimal solutions for small problem instances. The generated problem instances in combination with the upper bounds can be used as benchmarks for future approaches in the field of common due-date scheduling.Scope and purposeIn connection with just-in-time production and delivery, earliness as well as tardiness penalties are of interest. Thus scheduling against common due dates has received growing attention during the last decade. Many algorithms have been developed to solve the different variants of this problem. But whenever a new algorithm for scheduling against common due dates is proposed, its quality is assessed only on a few self-generated examples. Hence it is difficult to evaluate the various approaches, particularly in comparison with each other. Therefore the goal of this paper is to present numerous benchmark problems together with some upper bounds on the optimal objective function value.     

Scheduling rules for dynamic shops that manufacture multi-level jobs

The problem of scheduling in dynamic conventional jobshops has been extensively investigated over many years. However, the problem of scheduling in assembly jobshops (i.e. shops that manufacture multi-level jobs with components and subassemblies) has been relatively less investigated in spite of the fact that assembly jobshops are frequently encountered in real life. A survey of literature on dynamic assembly jobshop scheduling has revealed that the TWKR-RRP rule is the best one for minimizing the mean flowtime and staging delay, and the job due-date (JDD) rule is the best for minimizing the mean tardiness of jobs. However, the objectives of minimizing the maximum flowtime (and maximum staging delay) and standard deviation of flowtime (and standard deviation of staging delay) are as important as the minimization of mean flowtime and mean staging delay. Likewise, the objectives of minimizing the maximum tardiness and standard deviation of tardiness are also as important as the minimization of mean tardiness. The reason is that the maximum and standard deviation values of a performance measure indicate the worst-case performance of a dispatching rule. The present study seeks to develop efficient dispatching rules to minimize the maximum and standard deviation of flowtime and staging delay, and the maximum and the standard deviation of conditional tardiness of jobs. The dispatching rules are based on the computation of the earliest completion time of a job and consequently determining the latest finish time of operations on components/subassemblies of a job. An extensive simulation-based investigation of the performance evaluation of the existing dispatching rules and the proposed dispatching rules has been carried out by randomly generating jobs with different structures and different shop utilization levels. It has been found from the simulation study that the proposed rules are quite effective in minimizing the maximum and standard deviation of flowtime and staging delay, and the maximum conditional tardiness and standard deviation of conditional tardiness.     

Minimizing maximum earliness on parallel identical machines

This paper addresses the scheduling problem of minimizing maximum earliness (or more generally — maximizing minimum lateness) on parallel identical machines. We prove that the two-machine case is NP-hard in the ordinary sense, and introduce a pseudo-polynomial dynamic programming algorithm for this case. When the number of machines is arbitrary, the problem is shown to be NP-hard in the strong sense. Then we introduce an efficient heuristic and two simple upper bounds on the optimal minimum lateness value. Finally we provide an extensive numerical study which indicates that the heuristic performs well in various job and machine settings.Scope and purposeIn recent years many researchers have focused on minimizing both earliness and tardiness costs. Only a few studies have considered problems with (maximum or total) earliness as the sole performance measure. We believe that the earliness measure is appropriate for many real-life settings, where the main cost component is the earliness (inventory) cost, and the tardiness (positive lateness) cost component is negligible. Our paper studies the scheduling problem of minmax earliness on parallel identical machines: we analyze the complexity of the problem, and introduce an efficient heuristic and simple bounds on the optimal cost.     

Single-machine scheduling with a common due window

We study several single-machine non-preemptive scheduling problems to minimize the sum of weighted earliness–tardiness, weighted number of early and tardy jobs, common due window location, and flowtime penalties. We allow the due window location to be either a decision variable or a given parameter. We assume that the due window location has a tolerance and the window size is a given parameter. We further make the assumption that the ratios of the job processing times to the earliness–tardiness weights are agreeable for the first problem. We propose pseudo-polynomial dynamic programming algorithms to optimally solve the problems. We also provide polynomial time algorithms for several special cases.Scope and purpose The widespread use of Just-In-Time philosophy in manufacturing to eliminate inventories leads to a new class of scheduling problems in which the earliness and/or number of early jobs are penalized as well as the tardiness and/or tardy jobs. In this type of environments, the jobs are sometimes associated with a period of time within which they incur no penalty since the customers will generally allow a time interval for the delivery of the products. This time period is called a due window. There are a variety of applications with due windows in factory automation, production maintenance, and so on. In this paper, we consider the common due window problems to minimize the weighted earliness–tardiness, weighted number of early–tardy jobs and weighted flowtime on a single machine. The main contributions of this paper are identifying the computational complexity of the problems, developing dynamic programming algorithms to optimally solve them, and providing efficient and exact polynomial algorithms for the special cases.     

提前/延期惩罚最小化互替机床调度算法

对经提前/延期（E/T）惩罚最小为目标的互替机床调度问题进行了分析，对互替机床E/T调度问题进行了描述，提出了解决调度问题的具体策略，在此基础上，建立了基于启发式的互替机床E/T调度算法，最后通过仿真实验验证了本算法的有效性和实用性。     

Multiagent scheduling method with earliness and tardiness objectives in flexible job shops.

Flexible job-shop scheduling problems are an important extension of the classical job-shop scheduling problems and present additional complexity. Such problems are mainly due to the existence of a considerable amount of overlapping capacities with modern machines. Classical scheduling methods are generally incapable of addressing such capacity overlapping. We propose a multiagent scheduling method with job earliness and tardiness objectives in a flexible job-shop environment. The earliness and tardiness objectives are consistent with the just-in-time production philosophy which has attracted significant attention in both industry and academic community. A new job-routing and sequencing mechanism is proposed. In this mechanism, two kinds of jobs are defined to distinguish jobs with one operation left from jobs with more than one operation left. Different criteria are proposed to route these two kinds of jobs. Job sequencing enables to hold a job that may be completed too early. Two heuristic algorithms for job sequencing are developed to deal with these two kinds of jobs. The computational experiments show that the proposed multiagent scheduling method significantly outperforms the existing scheduling methods in the literature. In addition, the proposed method is quite fast. In fact, the simulation time to find a complete schedule with over 2000 jobs on ten machines is less than 1.5 min.     

解并行多机提前/拖后调度问题的并行遗传算法

为有效地解决带有公共交货期的非等同并行多机提前/拖后调度问题,设计了一种分段扩展排列编码的混合遗传算法,使遗传编码能同时反映调度方案和公共交货期,并对其初始种群产生、交叉和变异方法也进行了研究。同时为了更好地适应调度实时性和解大规模此类问题的需要,基于遗传算法自然并行性特点的基础上,实现了主从式控制网络模式下并行混合遗传算法。计算结果表明,此算法是有效的,优于启发式算法和遗传算法,有着较高的并行性,并能适用于大规模非等同并行多机提前/拖后调度问题。     

A differential evolution approach for the common due date early/tardy job scheduling problem

The problem of scheduling multiple jobs on a single machine so that they are completed by a common specified date is addressed in this paper. This type of scheduling set costs depend on whether a job is finished before (earliness) or after (tardiness) the specified due date. The objective is to minimize a summation of earliness and tardiness penalty costs. Minimizing these costs pushes the completion time of each job as close as possible to the due date. The use of differential evolution as the optimization heuristic to solve this problem is investigated in this paper. Computational experiments over multiple (280 in total) public benchmark problems with up to 1000 jobs to be scheduled show the effectiveness of the proposed approach. The results obtained are of high quality putting new upper bounds to 60% of the benchmark instances.     

交货期窗口下带有附加惩罚的单机提前/拖期调度问题

交货期窗口下的交货期确定和排序问题是调度领域研究的一个方面,本文对交货期口下的单机作业问题进行了研究,目标函数不仅考虑提前／拖期惩罚,还考虑附加惩罚,假设如果任务在交货期窗口内完工,则不受提前／拖期片罚;如果在交货期窗口外完工,将导致提前／拖期惩罚,本文确定了最优公共交货期,给出了相庆的最优排序,并提出了一个多项式时间算法确定了使目标函数为最小的最优调度,最后的数值例子说明了算法的有效性。     

A note on “schedule of n jobs on two identical machines to minimize weighted mean flor time”

In a recent paper, Alidaee [Computers ind. Engng 24, 53–55 (1993)] notes the similarity between the scheduling problems of minimizing weighted mean flow time (WMFT) on two parallel machines and minimmizing weighted earliness/tardiness (WET) about a common due date on a single machine. Based on this similarity, Alidaee descirbes how a dynamic programming algorithm proposed by Hall and Posner [Opns Res. 39, 836–846 (1991)] for the WET problem can be modified and applied to the WMFT problem. The work is an important extension of earlier results on an equivalence relationship between the WMFT and WET problems. This Note helps consolidate the literature by recognizing Rothkopf [Mgmt Sci. 12, 437–447 (1966)] as the originator of algorithm described in [Computers ind. Engng 24 53–55 (1993)].     

Scatter search based particle swarm optimization algorithm for earliness/tardiness flowshop scheduling with uncertainty

Considering the imprecise nature of the data in real-world problems, the earliness/tardiness (E/T) flowshop scheduling problem with uncertain processing time and distinct due windows is concerned in this paper. A fuzzy scheduling model is established and then transformed into a deterministic one by employing the method of maximizing the membership function of middle value. Moreover, an effective scatter search based particle swarm optimization (SSPSO) algorithm is proposed to minimize the sum of total earliness and tardiness penalties. The proposed SSPSO algorithm incorporates the scatter search (SS) algorithm into the frame of particle swarm optimization (PSO) algorithm and gives full play to their characteristics of fast convergence and high diversity. Besides, a differential evolution (DE) scheme is used to generate solutions in the SS. In addition, the dynamic update strategy and critical conditions are adopted to improve the performance of SSPSO. The simulation results indicate the superiority of SSPSO in terms of effectiveness and efficiency.     

Impact of permutation enforcement when minimizing total weighted tardiness in dynamic flowshops with uncertain processing times

This paper is motivated by the problem of meeting due dates in a flowshop production environment with jobs with different weights and uncertain processing times. Enforcement of a permutation schedule to varying degrees for dynamic flowshops is investigated with the goal of minimizing total weighted tardiness (TWT). The approaches studied are categorized as follows: (1) pure permutation scheduling (2) shift-based scheduling (3) pure dispatching (which leads to non-permutation sequences). A simulation-based experimental study was carried out to study the performance of the above methods with respect to minimizing TWT when new jobs arrive to the flowshop at every shift change. Results indicate significant gains in performance are possible when the permutation requirement is relaxed and shift-based scheduling is allowed. Shift-based scheduling yields competitive results with respect to the pure dispatching approach, even though dispatching has the advantage of a full relaxation of the permutation requirement.     

Fast neighborhood search for the single machine earliness–tardiness scheduling problem

This paper addresses the one machine scheduling problem in which n jobs have distinct due dates with earliness and tardiness costs. Fast neighborhoods are proposed for the problem. They are based on a block representation of the schedule. A timing operator is presented as well as swap and extract-and-reinsert neighborhoods. They are used in an iterated local search framework. Two types of perturbations are developed based, respectively, on random swaps and earliness and tardiness costs. Computational results show that very good solutions for instances with significantly more than 100 jobs can be derived in a few seconds.     

带有交货期的比例流水车间调度问题的合作博弈

针对具有多个客户订单的比例流水车间调度问题,在考虑有交货期及提前和拖期惩罚下,以客户支出成本为优化指标,在客户通过合作结成联盟的方式下,以联盟内成员进行重新调度所获得的最大成本节省为联盟的价值,建立合作博弈模型.该合作博弈是具有无外部性的平衡博弈,从而有非空核.考虑到客户对提前加工和延迟加工的迫切程度不同,提出基于提前及拖期惩罚的β规则分配方法,该方法能得到带有交货期的比例流水车间调度合作博弈的一个核分配.通过混合差分进化算法求解最优调度顺序,实验结果验证了基于合作博弈模型的调度方法及成本分配方法的有效性.     

On the equivalence of single machine earliness/tardiness problems with job rejection

We present optimal algorithms for single-machine scheduling problems with earliness criteria and job rejection and compare them with the algorithms for the corresponding problems with tardiness objectives. We present an optimal O(n log n) algorithm for minimizing the maximum earliness on a single machine with job rejection. Our algorithm also solves the bi-criteria scheduling problem is which the objective is to simultaneously minimize the maximum earliness of the scheduled jobs and the total rejection cost of the rejected jobs. We also show that the optimal pseudo-polynomial time algorithm for the total tardiness problem with job rejection can be used to solve the corresponding total earliness problem with job rejection.