COMMON DUE-WINDOW SCHEDULING

In this paper, we solve common due-window scheduling problems within the just-in-time window concept, i.e., scheduling problems including both earliness and tardiness penalties. We assume that jobs share the same due window and incur no penalty as long as they are completed within the due window. We further assume that the earliness and tardiness penalty factors are constant and that the size of the window is a given parameter. For cases where the location of the due window is a decision variable, we provide a polynomial algorithm with complexity O(n * log (n)) to solve the problem. For cases where the location of the due window is a given parameter, we use dynamic programming with pseudopolynomial complexity to solve the problem.     

MINIMIZING ABSOLUTE AND SQUARED DEVIATION OF COMPLETION TIMES FROM DUE DATES

This is a study of a single-machine scheduling problem with the objective of minimizing the sum of a function of earliness and tardiness called the earliness and tardiness (ET) problem. I will show that if priority weights of jobs are proportional to their processing times, and if earliness and tardiness cost functions are linear, the problem will be equivalent to the total weighted tardiness problem. This proves that the et problem is np -hard. In addition, I present a heuristic algorithm with worst case bound for the et problem based on the equivalence relation between the two. When earliness and tardiness cost functions are quadratic, I consider the problem for a common due date for all jobs and for different job due dates. In general, the et problem with quadratic earliness and tardiness cost functions and all job weights equal to one is np -hard. I show that in many cases, when weights of jobs are proportional to their processing times, the problem can be solved efficiently. In the published results on the et problem with quadratic earliness and tardiness cost functions other researchers have assumed a zero starting time for the schedule. I discuss the advantages of a nonzero starting time for the schedule.     

A FRAMEWORK FOR MACHINE SCHEDULING PROBLEMS WITH CONTROLLABLE PROCESSING TIMES

This is a study of single and parallel machine scheduling problems with controllable processing time for each job. The processing time for job j depends on the position of the job in the schedule and is a function of the number of resource units allocated to its processing. Processing time functions and processing cost functions are allowed to be nonlinear. The scheduling problems considered here have important applications in industry and include many of the existing scheduling models as special cases. For the single machine problem, the objective is minimization of total compression costs plus a scheduling measure. The scheduling measures include makespan, total flow time, total differences in completion times, total differences in waiting times, and total earliness and tardiness with a common due date for all jobs. Except when the total earliness and tardiness measure is involved, each case the problem is solved efficiently. Under an assumption typically satisfied in just-in-time systems, the problem with total earliness and tardiness measure is also solved efficiently. Finally, for a large class of processing time functions; parallel machine problems with total flow time and total earliness and tardiness measures are solved efficiently. In each case we reduce the problem to a transportation problem.     

混合离散差分进化算法在单机批处理调度中的应用

本文研究单机批处理调度问题,批处理机有批次容量限制,批处理时间由每个批次所含作业中的最长作业处理时间决定。每个作业具有不同的大小、处理时间、提前拖期惩罚权重,所有作业具有公共交货期,且交货期无限晚。目标函数为最小化所有作业的加权提前拖期惩罚之和。该问题已被证明为NP难题,本研究找到了其最优解具有的一些性质,在此基础上利用它们提出了一种动态规划(DP)与差分进化(DE)算法相结合的混合离散差分进化(HDDE)算法来求解该问题,通过与传统的遗传算法、模拟退火算法和迭代贪婪算法进行对比,HDDE算法显示了更加强大的全局搜索能力。     

Single-machine batch delivery scheduling with an assignable common due window

This paper addresses a batch delivery single-machine scheduling problem in which jobs have an assignable common due window. Each job will incur an early (tardy) penalty if it is early (tardy) with respect to the common due window under a given schedule. There is no capacity limit on each delivery batch, and the cost per batch delivery is fixed and independent of the number of jobs in the batch. The objective is to find the optimal size and location of the window, the optimal dispatch date for each job, as well as an optimal job sequence to minimize a cost function based on earliness, tardiness, holding time, window location, window size, and batch delivery. We show that the problem can be optimally solved in O(n⁸)$O(n^8)$ time by a dynamic programming algorithm under a reasonable assumption on the relationships among the cost parameters. A computational experiment is also conducted to evaluate the performance of the proposed algorithm. We also show that some special cases of the problem can be optimally solved by lower order algorithms.     

A note on pre-emptive scheduling with earliness and tardiness costs

The option of pre-emption seems to have escaped the attention of existing literature on scheduling problems with earliness and tardiness costs. This note presents an attempt to accommodate pre-emption in such settings. The focus is on models with a common due date for all jobs under different cost structures ( job dependent versus job independent), and different objectives ( minsum and minmax). It appears that only one of these cases is not polynomially solvable: the case of minsum objective and job-dependent ( linear) cost. An exact dynamic programming algorithm is introduced for this problem, as well as an efficient heuristic, which is shown to perform extremely well in our numerical tests.     

Minimizing the Number of Late Jobs under the Group Technology Assumption

We consider the one-machine scheduling problem to minimize the number of late jobs under the group technology assumption, where jobs are classified into groups and all jobs from the same group must be processed contiguously. This problem is shown to be strongly NP-hard, even for the case of unit processing time and zero set-up time. A polynomial time algorithm is developed for the restricted version in which the jobs in each group have the same due date. However, the problem is proved to be ordinarily NP-hard if the jobs in a group have the same processing time as well as the same due date.     

A bicriteria approach to scheduling a single machine with job rejection and positional penalties

Single machine scheduling problems have been extensively studied in the literature under the assumption that all jobs have to be processed. However, in many practical cases, one may wish to reject the processing of some jobs in the shop, which results in a rejection cost. A solution for a scheduling problem with rejection is given by partitioning the jobs into a set of accepted and a set of rejected jobs, and by scheduling the set of accepted jobs among the machines. The quality of a solution is measured by two criteria: a scheduling criterion, F1, which is dependent on the completion times of the accepted jobs, and the total rejection cost, F2. Problems of scheduling with rejection have been previously studied, but usually within a narrow framework—focusing on one scheduling criterion at a time. This paper provides a robust unified bicriteria analysis of a large set of single machine problems sharing a common property, namely, all problems can be represented by or reduced to a scheduling problem with a scheduling criterion which includes positional penalties. Among these problems are the minimization of the makespan, the sum of completion times, the sum and variation of completion times, and the total earliness plus tardiness costs where the due dates are assignable. Four different problem variations for dealing with the two criteria are studied. The variation of minimizing F1+F2 is shown to be solvable in polynomial time, while all other three variations are shown to be $\mathcal{NP}$ -hard. For those hard problems we provide a pseudo polynomial time algorithm. An FPTAS for obtaining an approximate efficient schedule is provided as well. In addition, we present some interesting special cases which are solvable in polynomial time.     

A fast FPTAS for single machine scheduling problem of minimizing total weighted earliness and tardiness about a large common due date

We address the single machine scheduling problem to minimize the total weighted earliness and tardiness about a nonrestrictive common due date. This is a basic problem with applications to the just-in-time manufacturing. The problem is linked to a Boolean programming problem with a quadratic objective function, known as the half-product. An approach to developing a fast fully polynomial-time approximation scheme (FPTAS) for the problem is identified and implemented. The running time matches the best known running time for an FPTAS for minimizing a half-product with no additive constant.     

SIMULTANEOUS BATCHING AND SCHEDULING FOR CHEMICAL PROCESSING WITH EARLINESS AND TARDINESS PENALTIES

We consider the problem of determining the allocation of demand from different customer orders to production batches and the schedule of resulting batches to minimize the total weighted earliness and tardiness penalties in context of batch chemical processing. The problem is formulated as a mixed-integer nonlinear programming model. An iterative heuristic procedure that makes use of the network nature of the problem formulation is presented to approximate an optimal solution. An algorithm polynomial in the number of batches to produce is also presented that optimally solves the problem under special cost structures.     

A two-agent single machine scheduling problem with due-window assignment and a common flow-allowance

We study a single-machine scheduling model combining two competing agents and due-date assignment. The basic setting involves two agents who need to process their own sets of jobs, and compete on the use of a common processor. Our goal is to find the joint schedule that minimizes 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. The scheduling measure considered in this paper is minimum total (earliness, tardiness and due-date) cost, based on common flow allowance, i.e., due-dates are defined as linear functions of the job processing times. We introduce a simple polynomial time solution for this problem (linear in the number of jobs), as well as to its extension to a multi-agent setting. We further extend the model to that of a due-window assignment based on common flow allowance.     

Experimental earliness/tardiness production planning with the due window system

In order to use the philosophy of JIT to improve the production planning method of MRP-II, we propose the experimental software system of the earliness/tardiness produc tion planning problem with due window. By means of the approaches and model reported in this paper, the optimal production planning can be achieved. The recommended model extends the problem of due window from the shop scheduling level into the aggregated planning level of mass manufacturing systems. Simulation results have demonstrated that the experimental software is a useful tool for the production management of repetitive manufacturing enterprises.     

Single-machine scheduling with periodic due dates to minimize the total earliness and tardy penalty

We consider a single-machine scheduling problem such that the due dates are assigned to each job depending on its order, and the lengths of the intervals between consecutive due dates are identical. The objective is to minimize the total penalty for the earliness and tardiness of each job. The early penalty proportionally increases according to the earliness amount, while the tardy penalty increases according to the step function. We show that the problem is strongly NP-hard, and furthermore, polynomially solvable if the two types of processing times exist.

     

Approximation algorithms for the makespan minimization with positive tails on a single machine with a fixed non-availability interval

In this article, we consider the non-resumable case of the single machine scheduling problem with a fixed non-availability interval. We aim to minimize the makespan when every job has a positive tail. We propose a polynomial approximation algorithm with a worst-case performance ratio of 3/2 for this problem. We show that this bound is tight. We present a dynamic programming algorithm and we show that the problem has an FPTAS (Fully Polynomial Time Approximation Algorithm) by exploiting the well-known approach of Ibarra and Kim (J. ACM 22:463–468, 1975). Such an FPTAS is strongly polynomial. The obtained results outperform the previous polynomial approximation algorithms for this problem.     

Online scheduling with chain precedence constraints of equal-length jobs on parallel machines to minimize makespan

We study the online scheduling problem on m identical parallel machines to minimize makespan, i.e., the maximum completion time of the jobs, where m is given in advance and the jobs arrive online over time. We assume that the jobs, which arrive at some nonnegative real times, are of equal-length and are restricted by chain precedence constraints. Moreover, the jobs arriving at distinct times are independent, and so, only the jobs arriving at a common time are restricted by the chain precedence constraints. In the literature, a best possible online algorithm of a competitive ratio 1.3028 is given for the case \(m=2\). But the problem is unaddressed for \(m\ge 3\). In this paper, we present a best possible online algorithm for the problem with \(m\ge 3\), where the algorithm has a competitive ratio of 1.3028 for \(3\le m\le 5\) and 1.3146 for \(m\ge 6\).     

Maximum latency scheduling problem on two-person cooperative games

This paper studies a two-person cooperative game in which a set of jobs has to be processed jointly by two people. Each of them has a single machine and his processing cost is defined as the minimum value of the maximum latency of his negotiably assigned jobs. The objective is to maximize the multiplication of their rational positive cooperative profits. In the case where all jobs have the same processing time, if they have a common due date, the problem is polynomial-time solvable; if due dates can be different, there exits an optimal schedule in which the jobs assigned to each person are scheduled in Earlier Due Date first (EDD) order and a polynomial-time dynamic programming is further proposed. In the case where processing times can be different, the NP-completeness of this problem is proved, and a pseudo-polynomial-time dynamic programming algorithm is developed.     

带工期指派的产品服务系统订单随机调度问题研究

针对由一个制造工厂和多个区域服务中心组成的服务型制造企业，研究了考虑生产时间和服务时间均具有随机性且工期可指派的产品服务系统（PSS）订单调度问题。首先以最小化订单提前、误工和工期指派费用的期望总额为目标构建问题的优化模型，然后分析目标函数近似值的最优性条件，据此提出加权最短平均生产时间排序规则，并结合该规则与插入邻域局部搜索设计了启发式算法对问题进行求解，最后通过数值仿真验证算法的可行性和有效性。研究表明，提前费用偏差对PSS订单调度与工期指派决策的影响很小，因此企业管理者无需准确估计库存费用也能制定出比较有效的PSS订单调度策略；而工期指派费用偏差对决策结果的影响非常大，因此企业管理者在决策时必须谨慎估计该项费用。     

Optimal Policy for a Stochastic Scheduling Problem with Applications to Surgical Scheduling

We consider the stochastic, single‐machine earliness/tardiness problem (SET), with the sequence of processing of the jobs and their due‐dates as decisions and the objective of minimizing the sum of the expected earliness and tardiness costs over all the jobs. In a recent paper, Baker ( 2014 ) shows the optimality of the Shortest‐Variance‐First (SVF) rule under the following two assumptions: (a) The processing duration of each job follows a normal distribution. (b) The earliness and tardiness cost parameters are the same for all the jobs. In this study, we consider problem SET under assumption (b). We generalize Baker's result by establishing the optimality of the SVF rule for more general distributions of the processing durations and a more general objective function. Specifically, we show that the SVF rule is optimal under the assumption of dilation ordering of the processing durations. Since convex ordering implies dilation ordering (under finite means), the SVF sequence is also optimal under convex ordering of the processing durations. We also study the effect of variability of the processing durations of the jobs on the optimal cost. An application of problem SET in surgical scheduling is discussed.     

Heterogeneous dispatching rules in job and flow shops

This paper reports the results of a study of the use of heterogeneous dispatching rules for the scheduling of work in a job shop. The methodology employed included discrete event simulation, using rule combinations determined by prior genetic algorithm searches and generalization using neural networks. Eight dispatching rules were considered, including first in first out (FIFO), earliest due date ( EDD), shortest processing time (SPT), slack/ number of operations (SLK), critical ratio (CR), modified due date (MDD), modified operation due date (MOD), and apparent tardiness cost (ATC). A three-machine job shop was studied, in which three work organizations were employed, pure flow (fixed sequence), pure job shop ( random sequence), and a hybrid shop where flow is random but with unequal probabilities. Three levels of machine loading were used and average tardiness was used as the performance measure. In most cases, modified due date and apparent tardiness cost were the best rules. The application of the best rules effected the results primarily when applied to bottleneck machines or the first machine in a pure flow shop. Nearly any other rule was acceptable on non-botdeneck machines except FIFO and CR, which consistently perform poorly. No major advantage of mixing rules was found.     

A genetic algorithm for scheduling on a single machine with set-up times and due dates

This paper presents a genetic algorithm for a single machine-scheduling problem with the objective of minimizing total tardiness. Each job has its own due date and the set-up times are sequence dependent. The parameters of the genetic algorithm are determined by a statistical method. For small problems, the solutions given by the proposed method are compared with solutions provided by a commercial package, and for larger problems, with those obtained by a heuristic proposed in the literature.