1,721,105 research outputs found
The coordination of scheduling and batch deliveries
No full textThis paper considers several scheduling problems where deliveries are made in batches with each batch delivered to the customer in a single shipment. Various scheduling costs, which are based on the delivery times of the jobs, are considered. The objective is to minimize the scheduling cost plus the delivery cost, and both single and parallel machine environments are considered. For many combinations of these, we either provide efficient algorithms that minimize total cost or show that the problem is intractable. Our work has implications for the coordination of scheduling with batch delivery decisions to improve customer service
Rescheduling for new orders
No full textThis paper considers scheduling problems where a set of original jobs has already been scheduled to minimize some cost objective, when a new set of jobs arrives and creates a disruption. The decision maker needs to insert the new jobs into the existing schedule without excessively disrupting it. Two classes of models are considered. First, we minimize the scheduling cost of all the jobs, subject to a limit on the disruption caused to the original schedule, where this disruption is measured in various ways. In the second class, a total cost objective, which includes both the original cost measure and the cost of disruption, is minimized. For both classes and various costs based on classical scheduling objectives, and for almost all problems, we provide either an efficient algorithm or a proof that such an algorithm is unlikely to exist. We also show how to extend both classes of models to deal with multiple disruptions in the form of repeated arrivals of new jobs. Our work refocuses the extensive literature on scheduling problems towards issues of rescheduling, which are important because of the frequency with which disruptions occur in manufacturing practice
Supply chain scheduling: batching and delivery
No full textAlthough the supply chain management literature is extensive, the benefits and challenges of coordinated decision making within supply chain scheduling models have not been studied. We consider a variety of scheduling, batching, and delivery problems that arise in an arborescent supply chain where a supplier makes deliveries to several manufacturers, who also make deliveries to customers. The objective is to minimize the overall scheduling and delivery cost, using several classical scheduling objectives. This is achieved by scheduling the jobs and forming them into batches, each of which is delivered to the next downstream stage as a single shipment. For each problem, we either derive an efficient dynamic programming algorithm that minimizes the total cost of the supplier or that of the manufacturer, or we demonstrate that this problem is intractable. The total system cost minimization problem of a supplier and manufacturer who make cooperative decisions is also considered. We demonstrate that cooperation between a supplier and a manufacturer may reduce the total system cost by at least 20%, or 25%, or by up to 100%, depending upon the scheduling objective. Finally, we identify incentives and mechanisms for this cooperation, thereby demonstrating that our work has practical implications for improving the efficiency of supply chains.<br/
Online production planning to maximize the number of on-time orders
No full textWe consider a production planning problem with two planning periods. Detailed planning occurs in the first period, when complete information is known about a set of orders that are initially available. An additional set of orders becomes available at the start of the second planning period. The objective is to maximize the number of on-time orders. We derive an upper bound on the competitive ratio of any deterministic online algorithm, relative to the performance of an algorithm with perfect information about the second set of orders. This ratio depends on the relative lengths of the two planning periods. We also describe an efficient algorithm that delivers a solution which asymptotically achieves this upper bound ratio as the number of jobs becomes large
Going Beyond Counting First Authors in Author Co-citation Analysis
Full text linkThe present study examines one of the fundamental aspects of author co-citation analysis (ACA) - the way co-citation
counts are defined. Co-citation counting provides the data on which all subsequent statistical analyses and mappings
are based, and we compare ACA results based on two different types of co-citation counting - the traditional type that
only counts the first one among a cited work's authors on the one hand and a non-traditional type that takes into
account the first 5 authors of a cited work on the other hand. Results indicate that the picture produced through this non-traditional author co-citation counting contains more coherent author groups and is therefore considerably clearer. However, this picture represents fewer specialties in the research field being studied than that produced through the traditional first-author co-citation counting when the same number of top-ranked authors is selected and analyzed. Reasons for these effects are discussed
Online scheduling with known arrival times
No full textWe consider an online scheduling environment where decisions are made without knowledge of the data of jobs that may arrive later. However, additional jobs can only arrive at known future times. This environment interpolates between the classical offline and online scheduling environments, and approaches the classical online environment when there are many equally spaced potential job arrival times.The objective is to minimize the sum of weighted completion times, a widely used measure of work-in-process inventory cost and customer service. For a nonpreemptive single machine environment, we show that a lower bound on the competitive ratio of any online algorithm is the solution of a mathematical program. This lower bound is between $(1+SQRT(5))/2 and 2, with the exact value depending on the potential job arrival times. We also provide a "best possible" online scheduling algorithm, and show that its competitive ratio matches this lower bound. We analyze two practically motivated special cases where the potential job arrival times have a special structure. When there are many equally spaced potential job arrival times, the competitive ratio of our online algorithm approaches the best possible competitive ratio of 2 for the classical online problem
Scheduling with fixed delivery dates
No full textIn most classical scheduling models, it is assumed that a job is dispatched to a customer immediately after its processing completes. In many practical situations, however, a set of delivery dates may be fixed before any jobs are processed. This is particularly relevant where delivery is an expensive or complicated operation, for example, as with heavy machinery. A similar situation arises where customers find deliveries disruptive and thus require them to be made within a limited time interval that repeats periodically. A third possibility is that a periodic business function, for example, the supplier's billing cycle, effectively defines a delivery date, and includes all jobs that have been completed since the previous billing cycle. These situations are not adequately represented by classical scheduling models. We consider a variety of deterministic scheduling problems in which a job is dispatched to a customer at the earliest fixed delivery date that is no earlier than the completion time of its processing. Problems where the number of delivery dates is constant, and others where it is specified as part of data input, are studied. For almost all problems considered, we either provide an efficient algorithm or establish that such an algorithm is unlikely to exist. By doing so, we permit comparisons between the solvability of these fixed delivery date problems and of the corresponding classical scheduling problem
Parallel machine scheduling with a common server
No full textThis paper considers the nonpreemptive scheduling of a given set of jobs on several identical, parallel machines. Each job must be processed on one of the machines. Prior to processing, a job must be loaded (setup) by a single server onto the relevant machine. The paper considers a number of classical scheduling objectives in this environment, under a variety of assumptions about setup and processing times. For each problem considered, the intention is to provide either a polynomial- or pseudo-polynomial-time algorithm, or a proof of binary or unary NP-completeness. The results provide a mapping of the computational complexity of these problems
- …
