This chapter presents a novel idea for the general case of the Common Due-Date (CDD) scheduling problem. The problem is about scheduling a certain number of jobs on a single or parallel machines where all the jobs possess different processing times but a common due-date. The objective of the problem is to minimize the total penalty incurred due to earliness or tardiness of the job completions. This work presents exact polynomial algorithms for optimizing a given job sequence for single and identical parallel machines with the run-time complexities of O(nlogn) for both cases, where n is the number of jobs. Besides, we show that our approach for the parallel machine case is also suitable for non-identical parallel machines. We prove the optimality for the single machine case and the run-time complexities of both. Henceforth, we extend our approach to one particular dynamic case of the CDD and conclude the chapter with our results for the benchmark instances provided in the OR library.
Cheng again considered the same problem with slight variations and presented a linear programming formulation @cite_13 . In @math Cheng and Kahlbacher and Hall studied the CDD problem extensively, presenting some useful properties for the general case @cite_10 @cite_1 . A pseudo polynomial algorithm of O( @math ) (where, @math is the common due-date) complexity was presented by Hoogeveen and Van de Velde for the restrictive case with one machine when the earliness and tardiness penalty weights are symmetric for all the jobs @cite_2 . In @math Hall studied the unweighted earliness and tardiness problem and presented a dynamic programming algorithm @cite_1 . Besides these earlier works, there has been some research on heuristic algorithms for the general common due date problem with asymmetric penalty costs. James presented a tabu search algorithm for the general case of the problem in @math @cite_18 .
@cite_13 @cite_18 @cite_1 @cite_2 @cite_10
2043295707 2062701203 2091164478 2056177557 2084068443
This paper considers the problem of scheduling jobs on single and parallel machines where all the jobs possess different processing times but a common due date. There is a penalty involved with each job if it is processed earlier or later than the due date. The objective of the problem is to find the assignment of jobs to machines, the processing sequence of jobs and the time at which they are processed, which minimizes the total penalty incurred due to tardiness or earliness of the jobs. This work presents exact polynomial algorithms for optimizing a given job sequence for single and parallel machines with the run-time complexities of O(n log n) and O(mn2 log n) respectively, where n is the number of jobs and m the number of machines. The algorithms take a sequence consisting of all the jobs (J_i, i = 1,2,...,n) as input and distribute the jobs to machines (for m>1) along with their best completion times so as to get the least possible total penalty for this sequence. We prove the optimality for the single machine case and the runtime complexities of both. Henceforth, we present the results for the benchmark problems and compare with previous work for both single and parallel machine cases, up to 200 jobs. A companion paper Part I considers the problem of minimizing the weighted earliness and tardiness of jobs scheduled on a single machine around a common due date, d, which is unrestrictively late. This paper Part II considers the problem of minimizing the unweighted earliness and tardiness of jobs, allowing the possibility that d is early enough to constrain the scheduling decision. We describe several optimality conditions. The recognition version of the problem is shown to be NP-complete in the ordinary sense, confirming a well known conjecture. Moreover, this complexity definition is precise, since we describe a dynamic programming algorithm which runs in pseudopolynomial time. This algorithm is also extremely efficient computationally, providing an improvement over earlier procedures, of almost two orders of magnitude in the size of instance that can be solved. Finally, we describe a special case of the problem which is polynomially solvable. This article uses tabu search to solve the restricted, common-due-date, early tardy machine scheduling problem generalised earliness and tardiness penalties. Different forms of the tabu search are tested, including one based on a sequence of jobs solution space and another based on an early tardy solution space. Results show that a search which uses an early tardy solution space with a neighbourhood scheme which eliminates infeasible areas of the solution space is the most efficient and effective solution method. We consider a one-machine scheduling problem with earliness and tardiness penalties. All jobs are assigned a common due date and the objective is to minimize the total penalty due to job earliness and tardiness. We are interested in finding the optimal combination of the common due-date value and the job sequence. Despite the fact that this problem in general is very hard to solve, we prove that there exists at least a common property for all optimal solutions: The first job in an optimal sequence is one of the longest jobs. We also prove that this property holds for a general class of unimodal penalty functions. Abstract 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 purpose In 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. This paper investigates the single-machine multiple common due dates assignment and scheduling problems in which the processing time of a job depends on its position in a job sequence and its resource allocation. We examine the general position-dependent deterioration effect and two models of resource allocation. The objective function is to minimize a total penalty function containing earliness, tardiness, due date, and resource consumption costs. We introduce two polynomial time algorithms to solve the considered problems. Since the two algorithms solve the problems in polynomial time, they can solve large-scale instances of the problem under study in little time. Given processing times of n jobs on a single machine with penalties for earliness and tardiness and penalties associated with assignment of due-dates, the objective is to select optimal due-dates and optimal sequence. Scheduling procedure for the solution of this problem is presented along with proof of optimality and illustrative numerical examples. We consider an n job, one machine scheduling problem in which all jobs have a common due date. The objective is to determine the optimal value of this due date and an optimal sequence to minimize a total penalty function. This penalty function is based on the due date value and on the earliness or the lateness of each job in the selected sequence. We present a polynomial bound scheduling algorithm for the solution of this problem along with the proof of optimality, a numerical example and discuss some extensions. This paper addresses the single machine scheduling problem with a common due date aiming to minimize earliness and tardiness penalties. Due to its complexity, most of the previous studies in the literature deal with this problem using heuristics and metaheuristics approaches. With the intention of contributing to the study of this problem, a branch-and-bound algorithm is proposed. Lower bounds and pruning rules that exploit properties of the problem are introduced. The proposed approach is examined through a computational comparative study with 280 problems involving different due date scenarios. In addition, the values of optimal solutions for small problems from a known benchmark are provided. Mathematical subject classification: 90C11, 62P30, 90B35. We investigate the minimization of Newton's functional for the problem of the body of minimal resistance with maximal height @math cite butt in the class of convex developable functions defined in a disc. This class is a natural candidate to find a (non-radial) minimizer in accordance with the results of cite lrp2. We prove that the minimizer in this class has a minimal set in the form of a regular polygon with @math sides centered in the disc, and numerical experiments indicate that the natural number @math is a non-decreasing function of @math . The corresponding functions all achieve a lower value of the functional than the optimal radially symmetric function with the same height @math . We study inherent structural properties of a strongly NP-hard problem of scheduling @math jobs with release times and due dates on a single machine to minimize the number of late jobs. Our study leads to two polynomial-time algorithms. The first algorithm with the time complexity @math solves the problem if during its execution no job with some special property occurs. The second algorithm solves the version of the problem when all jobs have the same length. The time complexity of the latter algorithm is @math , which is an improvement over the earlier known algorithm with the time complexity @math . We address the problem of scheduling n jobs on a batching machine to minimize regular scheduling criteria that are non-decreasing in the job completion times. A batching machine is a machine that can handle up to b jobs simultaneously. The jobs that are processed together form a batch, and all jobs in a batch start and complete at the same time. The processing time of a batch is equal to the largest processing time of any job in the batch. We analyse two variants: the unbounded model, where b⩾n; and the bounded model, where b<n. For the unbounded model, we give a characterization of a class of optimal schedules, which leads to a generic dynamic programming algorithm that solves the problem of minimizing an arbitrary regular cost function in pseudopolynomial time. The characterization leads to more efficient dynamic programming algorithms for specific cost functions: a polynomial algorithm for minimizing the maximum cost, an O(n3) time algorithm for minimizing the number of tardy jobs, an O(n2) time algorithm for minimizing the maximum lateness, and an O(n log n) time algorithm for minimizing the total weighted completion time. Furthermore, we prove that minimizing the weighted number of tardy jobs and the total weighted tardiness are NP-hard problems. For the bounded model, we derive an O(nb(b−1)) time dynamic programming algorithm for minimizing total completion time when b>1; for the case with m different processing times, we give a dynamic programming algorithm that requires O(b2m22m) time. Moreover, we prove that due date based scheduling criteria give rise to NP-hard problems. Finally, we show that an arbitrary regular cost function can be minimized in polynomial time for a fixed number of batches. © 1998 John Wiley & Sons, Ltd. A citing sentence is one that appears in a scientific article and cites previous work. Citing sentences have been studied and used in many applications. For example, they have been used in scientific paper summarization, automatic survey generation, paraphrase identification, and citation function classification. Citing sentences that cite multiple papers are common in scientific writing. This observation should be taken into consideration when using citing sentences in applications. For instance, when a citing sentence is used in a summary of a scientific paper, only the fragments of the sentence that are relevant to the summarized paper should be included in the summary. In this paper, we present and compare three different approaches for identifying the fragments of a citing sentence that are related to a given target reference. Our methods are: word classification, sequence labeling, and segment classification. Our experiments show that segment classification achieves the best results. This paper considers earliness tardiness (ET) scheduling problem on a parallel machine environment with common due-date under the effects of time-dependent learning and linear and nonlinear deterioration. In this paper, the effects of learning and deterioration are considered simultaneously. By the effects of learning and deterioration, we mean that the processing time of a job is defined by increasing function of its execution start time and position in the sequence. This study shows that optimal solution for ET scheduling problem under effects of learning and deterioration is V-shape schedule under certain agreeable conditions. Furthermore, we present a mathematical model for the problem under study and an algorithm for solving large test problems. The algorithm can solve problems of 1000 jobs and four machines within 3s on average. Citation relationship between scientific publications has been successfully used for scholarly bibliometrics, information retrieval and data mining tasks, and citation-based recommendation algorithms are well documented. While previous studies investigated citation relations from various viewpoints, most of them share the same assumption that, if paper1 cites paper2 (or author1 cites author2), they are connected, regardless of citation importance, sentiment, reason, topic, or motivation. However, this assumption is oversimplified. In this study, we employ an innovative "context-rich heterogeneous network" approach, which paves a new way for citation recommendation task. In the network, we characterize 1) the importance of citation relationships between citing and cited papers, and 2) the topical citation motivation. Unlike earlier studies, the citation information, in this paper, is characterized by citation textual contexts extracted from the full-text citing paper. We also propose algorithm to cope with the situation when large portion of full-text missing information exists in the bibliographic repository. Evaluation results show that, context-rich heterogeneous network can significantly enhance the citation recommendation performance. In a document network such as a citation network of scientific documents, web-logs, etc., the content produced by authors exhibits their interest in certain topics. In addition some authors influence other authors' interests. In this work, we propose to model the influence of cited authors along with the interests of citing authors. Moreover, we hypothesize that apart from the citations present in documents, the context surrounding the citation mention provides extra topical information about the cited authors. However, associating terms in the context to the cited authors remains an open problem. We propose novel document generation schemes that incorporate the context while simultaneously modeling the interests of citing authors and influence of the cited authors. Our experiments show significant improvements over baseline models for various evaluation criteria such as link prediction between document and cited author, and quantitatively explaining unseen text. Purpose – The purpose of this paper is to suggest an alternative to the widely used Times Cited criterion for analysing citation networks. The approach involves taking account of the natures of the papers that cite a given paper, so as to differentiate between papers that attract the same number of citations.Design methodology approach – ArticleRank is an algorithm that has been derived from Google's PageRank algorithm to measure the influence of journal articles. ArticleRank is applied to two datasets – a citation network based on an early paper on webometrics, and a self‐citation network based on the 19 most cited papers in the Journal of Documentation – using citation data taken from the Web of Knowledge database.Findings – ArticleRank values provide a different ranking of a set of papers from that provided by the corresponding Times Cited values, and overcomes the inability of the latter to differentiate between papers with the same numbers of citations. The difference in rankings between Times Cited ... This paper considers a single-machine scheduling problem in which penalities occur when a job is completed early or late. The objective is to minimize the total penalty subject to restrictive assumptions on the due dates and penalty functions for jobs. A procedure is presented for finding an optimal schedule. We present a new class of randomized approximation algorithms for unrelated parallel machine scheduling problems with the average weighted completion time objective. The key idea is to assign jobs randomly to machines with probabilities derived from an optimal solution to a linear programming (LP) relaxation in time-indexed variables. Our main results are a @math -approximation algorithm for the model with individual job release dates and a @math -approximation algorithm if all jobs are released simultaneously. We obtain corresponding bounds on the quality of the LP relaxation. It is an interesting implication for identical parallel machine scheduling that jobs are randomly assigned to machines, in which each machine is equally likely. In addition, in this case the algorithm has running time O(n log n) and performance guarantee 2. Moreover, the approximation result for identical parallel machine scheduling applies to the on-line setting in which jobs arrive over time as well, with no difference in performance guarantee. Abstract This paper considers due-date assignments and sequencing of n jobs in a single- machine shop in which each job is given a constant waiting allowance. The objective is to find the optimal value of the waiting allowance and the optimal job sequence to minimize a cost function based on the waiting allowance and the job earliness and tardiness values. We formulate the problem as an LP and find the optimal solution via considering the LP dual problem and show that the optimal waiting allowance is independent of the job sequence.