共查询到20条相似文献,搜索用时 31 毫秒
1.
We study the problem of scheduling n jobs in a no-wait flow shop consisting of m batching machines. Each job has to be processed by all the machines. All jobs visit the machines in the same order. A job completed on an upstream machine should be immediately transferred to the downstream machine. Batching machines can process several jobs simultaneously in a batch so that all jobs of the same batch start and complete together. The processing time of a batch is equal to the maximum processing time of the jobs in this batch. We assume that the capacity of any batch is unbounded. The problem is to find an optimal batch schedule such that the maximum job completion time, that is the makespan, is minimized. For m = 2, we prove that there exists an optimal schedule with at most two batches and construct such a schedule in O(n log n) time. For m = 3, we prove that the number of batches can be limited to nine and give an example where all optimal schedules have seven batches. Furthermore, we prove that the best schedules with at most one, two and three batches are 3-, 2- and 3/2-approximate solutions, respectively. The first two bounds are tight for corresponding schedules. Finally, we suggest an assignment method that solves the problem with m machines and at most r batches in O(nm(r-2)+1+[m/r]) time, if m and r are fixed. The method can be generalized to minimize an arbitrary maximum cost or total cost objective function. 相似文献
2.
Single machine batch scheduling with sequential job processing 总被引:1,自引:0,他引:1
The problem of scheduling n jobs on a single machine in batches to minimize some regular cost functions is studied. Jobs within each batch are processed sequentially so that the processing time of a batch is equal to the sum of the processing times of the jobs contained in it. Jobs in the same batch are completed at the same time when the last job of the batch has finished its processing. A constant set-up time precedes the processing of each batch. The number of jobs in each batch is bounded by some value b. If b < n, then the problem is called bounded. Otherwise, it is unbounded. For both the bounded and unbounded problems, dynamic programming algorithms are presented for minimizing the maximum lateness, the number of late jobs, the total tardiness, the total weighted completion time, and the total weighted tardiness when all due dates are equal, which are polynomial if there is a fixed number of distinct due dates or processing times. More efficient algorithms are derived for some special cases of both the bounded and unbounded problems in which all due dates and/or processing times are equal. Several special cases of the bounded problem are shown to be NP-hard. Thus, a comprehensive classification of the computational complexities of the special cases is provided. 相似文献
3.
Ernesto G. Birgin 《工程优选》2013,45(10):1197-1208
The single machine scheduling problem with a common due date and non-identical ready times for the jobs is examined in this work. Performance is measured by the minimization of the weighted sum of earliness and tardiness penalties of the jobs. Since this problem is NP-hard, the application of constructive heuristics that exploit specific characteristics of the problem to improve their performance is investigated. The proposed approaches are examined through a computational comparative study on a set of 280 benchmark test problems with up to 1000 jobs. 相似文献
4.
5.
We consider the permutation flow shop scheduling problem with earliness and tardiness penalties (E/T) and common due date for jobs. We show that the problem can be sub-divided into three cases: (i) the due date is such that all jobs are necessarily tardy; (ii) the due date is unrestricted; and (iii) the due date is between the two. Based on analytical results we provide partial characterisation of the optimal solution and develop a comprehensive approach for solving the problem over the entire range of due dates. Our approach, which draws upon the existing literature and results for the single machine problem, successfully exploits the properties of the optimal solution. Limited computational results indicate that the performance of the heuristic is reasonable and has the potential to significantly improve performance. This approach has been incorporated as part of the scheduling module of the production planning and scheduling system we developed for a medium-sized bulk drug manufacturer. 相似文献
6.
We consider batch delivery scheduling on a single machine, where a common due-date is assigned to all the jobs and a rate-modifying activity on the machine may be scheduled, which can change the processing rate of the machine. Thus the actual processing time of a job is variable depending on whether it is processed before or after the rate-modifying activity. The objective is to determine the optimal job sequence, the optimal partition of the job sequence into batches, the optimal assigned common due-date, and the optimal location of the rate-modifying activity simultaneously to minimize the total cost of earliness, job holding, weighted number of tardy jobs, due-date assignment, and batch delivery. We derive some structural properties of the problem, based on which we design polynomial-time algorithms to solve some special cases of the problem. 相似文献
7.
This note considers single machine scheduling and due date assignment in which a job’s processing time depends on its position in a sequence. The objective functions include the cost of changing the due dates, the total cost of discarded jobs that cannot be completed by their due dates and the total earliness of the scheduled jobs. We analyse these problems with three different due date assignment methods. We provide a generic polynomial-time dynamic programming algorithm to solve the problems. 相似文献
8.
In this paper, we consider the problem of scheduling a set of n jobs on two identical machines with preparation constraints. Each job requires before its execution a set of resources and a non-negligible preparation time. The objective is to minimise the makespan. This problem is NP-hard. We prove the NP-hardness of two specific cases where in the first case preparation times take only three values, whereas in the second case preparation times and the release dates take only two values, respectively. Then, we present some special cases and heuristic algorithms along with an experimental study. 相似文献
9.
In this paper a novel evolutionary-based approach is utilised for efficiently solving the NP-hard problem of scheduling numerous common-due-date jobs on a single machine. Minimising the sum of earliness and tardiness penalties for all jobs is considered as the target function. The performance of the proposed approach is examined through a computational comparative study with 280 benchmark problems with up to 1000 jobs where the numerical results indicate that it can produce ‘better’ solutions in less computational time when compared to benchmark results and the methods available in the literature, namely genetic algorithm (GA), Tabu search (TS) and differential evolution (DE). 相似文献
10.
Ali Elyasi 《国际生产研究杂志》2013,51(8):2352-2362
This paper considers two different due date assignment and sequencing problems in single machine where the processing times of jobs are random variables. The first problem is to minimise the maximum due date so that all jobs are stochastically on time. It is shown that sequencing the jobs in decreasing service level (DSL) order optimally solves the problem. The results are then extended for two special cases of flow shop problem. The other problem is to minimise a total cost function which is a linear combination of three penalties: penalty on job earliness, penalty on job tardiness, and penalty associated with long due date assignment. The assignment of a common due date and distinct due dates are investigated for this problem. It is shown that the optimal sequence for the case of common due date is V-shaped. 相似文献
11.
In this paper, we investigate the unbounded version of scheduling jobs with release dates and deadlines on a batch processing machine. NP-completeness is established for the case where all jobs have agreeable processing times and deadlines. Polynomial time algorithms are presented for the following cases: agreeable release dates and deadlines; agreeable release dates and processing times; a fixed number of distinct release dates, distinct processing times or distinct deadlines. 相似文献
12.
Fabrication and assembly scheduling in a two-machine flowshop 总被引:2,自引:0,他引:2
This paper considers a fabrication scheduling problem to minimize the makespan in a two-machine flowshop. Each job has a unique component and a common component to be processed on the first machine. On machine 1, the common components of the jobs are grouped into batches for processing with a setup cost incurred whenever a batch is formed. A job is ready for its assembly operation on the second machine if both its unique and common components are finished on machine 1. The problems with batch availability and item availability are known as NP-hard. In this paper, we give proofs for the strong NP-hardness of the two problems. The results suggest that it is very unlikely to develop polynomial- or pseudo-polynomial-time algorithm for finding exact solutions for the two problems. 相似文献
13.
A branch and bound algorithm for scheduling unit size jobs on parallel batching machines to minimize makespan 总被引:1,自引:0,他引:1
In this paper, we present a branch and bound algorithm for the parallel batch scheduling of jobs having different processing times, release dates and unit sizes. There are identical machines with a fixed capacity and the number of jobs in a batch cannot exceed the machine capacity. All batched jobs are processed together and the processing time of a batch is given by the greatest processing time of jobs in that batch. We compare our method to a mixed integer program as well as a method from the literature that is capable of optimally solving instances with a single machine. Computational experiments show that our method is much more efficient than the other two methods in terms of solution time for finding the optimal solution. 相似文献
14.
Scheduling problems with earliness and tardiness penalties are commonly encountered in today's manufacturing environment due to the current emphasis on the just-in-time (JIT) production philosophy. The problem studied in this work is the parallel machine earliness-tardiness non-common due date sequence-dependent set-up time scheduling problem (PETNDDSP) for jobs with varying processing times, where the objective is to minimize the sum of the absolute deviations of job completion times from their corresponding due dates. The research presented provides a first step towards obtaining near optimal solutions for this problem using local search heuristics in the framework of a meta-heuristic technique known as simulated annealing (SA). The computational study shows that, using the SA methodology, significant improvements to the local search heuristic solutions can be achieved for problems of this type. 相似文献
15.
Scheduling parallel batch processing machines with arbitrary job sizes and incompatible job families
Motivated by a bottleneck operation in an MLCC (multi-layer ceramic capacitor) production line, we study the scheduling problem of parallel batch processing machines in which a number of jobs can be processed simultaneously in a machine as a batch. Volumes of the jobs are different from each other and each job belongs to the family in which all jobs have the same processing time. In this situation, we analyse three kinds of problems whose performance measures are makespan, total completion time, and total weighted completion time, respectively. Since these problems are known to be NP-hard, we propose a number of heuristics and design genetic algorithms for the problems. Through some computational experiments, we evaluate the performances of the heuristic algorithms proposed, including the genetic algorithms for each of three problems. 相似文献
16.
Two-agent scheduling has gained a lot of research attention recently. Two competing agents who have their own objective functions have to perform their respective set of jobs on one or more shared machines. This study considers a two-agent single-machine earliness and tardiness scheduling problem where jobs have distinct due dates and unforced idleness in between any two consecutive jobs is allowed. The objective is to minimize the total earliness and tardiness of jobs from one agent given that the maximum earliness–tardiness of jobs from the other agent cannot exceed an upper bound. In other words, each job from the second agent has a hard due window, whereas each job from the first agent will incur a penalty if completed either before or after its due date. Two mathematical models of the problem are presented, and several necessary optimality conditions are derived. By exploiting the established dominance properties, heuristic algorithms are developed for the problem. Finally, computational experiments are conducted to assess the models and heuristic procedures. 相似文献
17.
We study a problem of scheduling customized jobs on a single-machine. Each job requires two operations: one standard and one specific. Standard operations are processed in batches under item availability, and each batch requires a set-up time. Based on structural properties of the optimal solution, we introduce a generic dynamic programming scheme that builds an optimal schedule by alternately inserting blocks of operations of two distinct types. Our approach yields efficient algorithms for the sum of completion times problem with agreeable processing times and the maximum lateness problem. The number of late jobs problem is shown to be NP-hard in the ordinary sense, but is pseudo-polynomially solvable. A polynomial algorithm is also given for a special case of this problem. Our results indicate the differences between this problem and its counterpart under batch availability. 相似文献
18.
The burn-in test scheduling problem (BTSP) is a variation of the complex batch processing machine scheduling problem, which is also a generalisation of the liquid crystal injection scheduling problem with incompatible product families and classical identical parallel machine problem. In the case we investigated on the BTSP, the jobs are clustered by their product families. The product families can be clustered by different product groups. In the same product group, jobs with different product families can be processed as a batch. The batch processing time is dependent on the longest processing time of those jobs in that batch. Setup times between two consecutive batches of different product groups on the same batch machine are sequentially dependent. In addition, the unequal ready times are considered in the BTSP which involves the decisions of batch formation and batch scheduling in order to minimise the total machine workload without violating due dates and the limited machine capacity restrictions. Since the BTSP involves constraints on unequal ready time, batch dependent processing time, and sequence dependent setup times, it is more difficult to solve than the classical parallel batch processing machine scheduling problem with compatible product families or incompatible product families. These restrictions mean that the existing methods cannot be applied into real-world factories directly. Consequently, this paper proposes a mixed integer programming model to solve the BTSP exactly. In addition, two efficient solution procedures which solve the BTSP are also presented. 相似文献
19.
Production volume in the specialized agricultural chemical industry is typically too small to justify the capital expenditure required for continuous processing. As such, there is a trend towards building chemical processing plants for this market segment that are batch plants. Scheduling of this type of chemical plant under just-in-time operations, where both earliness and lateness penalties are included, is critical to the efficient operation of these plants. In this paper, a heuristic scheduling procedure is developed for the problem of minimizing the total weighted earliness and tardiness costs as well as the total set-up cost for the single-stage batch chemical manufacturing environment. 相似文献
20.
The problem we study in this paper arises from the washing step of hospital sterilisation services. Washers in the washing step are capable of handling more than one medical device set as long as their capacity is not exceeded. The medical device set sizes and arrival times to the sterilisation service may be different, but they all have the same washing duration. Thus, we model the washing step as a batch scheduling problem where medical device sets are treated as jobs with non-identical sizes and release dates, but equal processing times. The main findings we present in this paper are the following. First, we study two special cases for which polynomial algorithms are presented. We then develop a 2-approximation algorithm for the general problem. Finally, we develop a MILP model and compare it with another MILP model from the literature. Computational results show that our MILP model outperforms the model from the literature. 相似文献