Search

This paper studies the single-machine scheduling problem with truncated learning effect, time-dependent processing time, and past-sequence-dependent delivery time. The delivery time is the time that the job is delivered to the customer after processing is complete. The goal is to determine an optimal job schedule to minimize the total weighted completion time and maximum tardiness. In order to solve the general situation of the problem, we propose a branch-and-bound algorithm and other heuristic algorithms. Computational experiments also prove the effectiveness of the given algorithms. [ABSTRACT FROM AUTHOR]

In this paper, we consider two single-machine scheduling problems with deteriorating jobs and controllable processing time. The job processing time is a function of its starting time and resource allocation. For the convex resource function, a bicriteria analysis is provided, where the first (respectively, second) criteria is to minimize total weighted completion time (respectively, total resource consumption cost). The first problem is to minimize the weighted sum of the total weighted completion time and the total resource consumption cost. The second problem is to minimize the total weighted completion time subject to the total resource consumption cost is bound. These both problems are NP-hard, we propose some heuristic algorithms and a branch-and-bound algorithm to solve the problems. [ABSTRACT FROM AUTHOR]

In order to increase the efficiency of production in a deteriorating environment through competition amongst the individual agents, this study explores a two-agent scheduling problem with one deterioration rate for each job, where the processing time of a job is a function of the position-dependent workload, resource allocation, and deterioration rate (the range of the deterioration rate is non-negative). The optimal processing sequence and resource allocation for the jobs are found by giving an upper bound of an agent to minimize the maximum value of earliness, tardiness and decision variable of another agent under slack due-date assignment. It is verified that the problem cannot be solved in polynomial time, for which various heuristic algorithms and a branch-and-bound algorithm are proposed to simulate the data to find a better range in the deterioration rate parameter. [ABSTRACT FROM AUTHOR]

This paper studies the single machine scheduling problems with truncated logarithm processing times and exponential past-sequence-dependent delivery times. We prove that the makespan and total completion time minimizations are polynomially solvable. For the total weighted completion time minimization, we illustrate that it remains polynomially solvable under a special case; under the general case, this paper proposes heuristic, tabu search and branch-and-bound algorithms. Computational experiments indicate that the heuristic algorithm is more effective than tabu search algorithm. [ABSTRACT FROM AUTHOR]

Green scheduling that aims to enhance efficiency by optimizing resource allocation and job sequencing concurrently has gained growing academic attention. To tackle such problems with the consideration of scheduling and resource allocation, this paper considers a single-machine group scheduling problem with common/slack due-date assignment and a controllable processing time. The objective is to decide the optimized schedule of the group/job sequence, resource allocation, and due-date assignment. To solve the generalized case, this paper proves several optimal properties and presents a branch-and-bound algorithm and heuristic algorithms. Numerical experiments show that the branch-and-bound algorithm is efficient and the heuristic algorithm developed based on the analytical properties outruns the tabu search. [ABSTRACT FROM AUTHOR]

In this paper, we study a single-machine green scheduling problem with learning effects and past-sequence-dependent delivery times. The problem can be properly applied to tackle green manufacturing where production and delivery time are variable and highly subject to process-reengineering. Our goal is to determine the optimal sequence such that total weighted completion time and maximum tardiness are minimized. For the general case, we provide the analysis procedure of lower bound, and also propose the heuristic and branch-and-bound algorithms. Furthermore, computational experiments are conducted to demonstrate the effectiveness of our algorithms. [ABSTRACT FROM AUTHOR]

This paper investigates the single-machine resource allocation scheduling problem with learning effects and group technology. The objective is to determine the optimal job and group schedules, and resource allocations such that total completion time is minimized subject to limited resource availability. For some special cases, we show that the problem remains polynomially solvable. For general case of the problem, we propose the heuristic algorithm, tabu search algorithm and branch-and-bound algorithm. Numerical experiments are tested to evaluate the performance of the heuristic and branch-and-bound algorithms. [ABSTRACT FROM AUTHOR]

This paper considers a group scheduling problem with shorten (i.e., a proportional linear shortening) job processing times and ready times on a single machine. If the jobs are in the same group, they have independent and constant ready times. The setup time of a group is independent constant setup time between each group. The goal is to determine the optimal group sequence and the job sequence within the groups such that the makespan (i.e., the maximum completion time) is minimized. For the general case of the problem, an initial heuristic algorithm (an upper bound) and some lower bounds are proposed, and then a branch-and-bound algorithm can be developed to solve the problem. [ABSTRACT FROM AUTHOR]

This article addresses how to minimize total completion time on a single machine with a position-weighted learning effect. Under non-zero job release dates, a lower bound on the objective function, a number of dominance properties, and an initial solution (i.e. an NEH-based heuristic) are derived, which are used to expedite the elimination process of a branch-and-bound solution procedure. The performance of the branch-and-bound algorithm and the heuristic algorithm are evaluated on a set of randomly generated problem instances. [ABSTRACT FROM AUTHOR]

The permutation flow shop problems with truncated exponential sum of logarithm processing times based and position‐based learning effects are considered in this study. The objective is to minimize makespan and total weighted completion time, respectively. Several heuristics and a branch‐and‐bound algorithm are proposed in this paper. The tight worst‐case bounds of some simple heuristics are also given. Numerical experiments are tested to evaluate the performance of the heuristics and branch‐and‐bound algorithm. [ABSTRACT FROM AUTHOR]

This study considers a single machine group scheduling problem with deteriorating jobs and resource allocation (controllable processing times). The objective is to have the resource availability limited within a given range, and to minimize the maximum completion time (i.e. the makespan). For two special cases, it is proved that the problem can be solved in polynomial time. For the general case, an heuristic algorithm and a branch-and-bound algorithm are proposed. Computational results show that the proposed heuristic algorithm is generally effective. [ABSTRACT FROM AUTHOR]

In this article, single-machine group scheduling with learning effects and convex resource allocation is studied. The goal is to find the optimal job schedule, the optimal group schedule, and resource allocations of jobs and groups. For the problem of minimizing the makespan subject to limited resource availability, it is proved that the problem can be solved in polynomial time under the condition that the setup times of groups are independent. For the general setup times of groups, a heuristic algorithm and a branch-and-bound algorithm are proposed, respectively. Computational experiments show that the performance of the heuristic algorithm is fairly accurate in obtaining near-optimal solutions. [ABSTRACT FROM AUTHOR]

In this study, we consider a permutation flow shop scheduling problem on a three-machine with deteriorating jobs (a deteriorating job means that the job's processing time is an increasing function of its starting time) so as to minimize the makespan. We model job deterioration as a function that is proportional to a linear function of time. For some special cases, we prove that the problem can be solved in polynomial time. We develop branch-and-bound and heuristic procedures for the general case. Computational experiments for the branch-and-bound algorithm and heuristic algorithm are presented. [ABSTRACT FROM AUTHOR]

In this paper, we consider a two-machine flow shop scheduling problem with decreasing linear deterioration. By decreasing linear deterioration, we mean that the processing time is a decreasing function of its execution start time. The objective is to find a sequence that minimizes the total weighted completion time. Several dominance properties and some lower bounds are derived to speed up the elimination process of a branch-and-bound algorithm. Two heuristic algorithms are also proposed to overcome the inefficiency of the branch-and-bound algorithm. Computational results for randomly generated problem instances are presented. [ABSTRACT FROM AUTHOR]

Copyright of Journal of the Chinese Institute of Industrial Engineers is the property of Taylor & Francis Ltd and its content may not be copied or emailed to multiple sites or posted to a listserv without the copyright holder's express written permission. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.)

In this article, we consider a single machine scheduling problem with a time-dependent learning effect and deteriorating jobs. By the effects of time-dependent learning and deterioration, we mean that the job processing time is defined by a function of its starting time and total normal processing time of jobs in front of it in the sequence. The objective is to determine an optimal schedule so as to minimize the total completion time. This problem remains open for the case of −1 < a < 0, where a denotes the learning index; we show that an optimal schedule of the problem is V-shaped with respect to job normal processing times. Three heuristic algorithms utilising the V-shaped property are proposed, and computational experiments show that the last heuristic algorithm performs effectively and efficiently in obtaining near-optimal solutions. [ABSTRACT FROM PUBLISHER]

A real industrial production phenomenon, referred to as learning effects, has drawn increasing attention. However, most research on this issue considers only single machine problems. Motivated by this limitation, this paper considers flow shop scheduling problems with a general position-dependent learning effects. By the general position-dependent learning effects, we mean that the actual processing time of a job is defined by a general non-increasing function of its scheduled position. The objective is to minimize one of the five regular performance criteria, namely, the total completion time, the makespan, the total weighted completion time, the total weighted discounted completion time, and the sum of the quadratic job completion times. We present heuristic algorithms by using the optimal permutations for the corresponding single machine scheduling problems. We also analyze the worst-case bound of our heuristic algorithms. [ABSTRACT FROM AUTHOR]

Abstract: In this paper, we consider the single-machine scheduling problems with a time-dependent deterioration. By the time-dependent deterioration, we mean that the processing time of a job is defined by an increasing function of total normal processing time of jobs in front of it in the sequence. The objective is to minimize the total completion time. We develop a mixed integer programming formulation for the problem. The complexity status of this problem remains open. Hence, we use the smallest normal processing time (SPT) first rule as a heuristic algorithm for the general cases and analyze its worst-case error bound. Two heuristic algorithms utilize the V-shaped property are also proposed to solve the problem. Computational results are presented to evaluate the performance of the proposed algorithms. [ABSTRACT FROM AUTHOR]

Abstract: In this paper, we address a two-machine flow shop scheduling problem under simple linear deterioration. By a simple linear deterioration function, we mean that the processing time of a job is a simple linear function of its execution start time. The objective is to find a sequence that minimizes total weighted completion time. Optimal schedules are obtained for some special cases. For the general case, several dominance properties and two lower bounds are derived to speed up the elimination process of a branch-and-bound algorithm. A heuristic algorithm is also proposed to overcome the inefficiency of the branch-and-bound algorithm. Computational analysis on randomly generated problems is conducted to evaluate the branch-and-bound algorithm and heuristic algorithm. [ABSTRACT FROM AUTHOR]

Abstract: In this paper we consider the single-machine scheduling problems with job-position-based and sum-of-processing-times based processing times. The real processing time of a job is a function of its position and the total processing time of the jobs that are in front of it in the sequence. The objective is to minimize the makespan, and to minimize the mean finish time. We prove that some special cases are polynomially solvable under some restrictions of the parameters. In addition, for some another special cases of minimization of the mean finish time and the makespan, we show that an optimal schedule is V-shaped with respect to job normal processing times. Then, we propose a heuristic based on the V-shaped property, and show through a computational experiment that it performs efficiently. [Copyright &y& Elsevier]

Abstract: In this study we consider the single-machine scheduling problems with a sum of-processing-times-based learning effect. The sum of-processing-times-based learning effect of a job is assumed to be a function of the sum of the normal processing time of the already processed jobs. The objective is to minimize one of two regular objective functions, namely the weighted sum of completion times and the maximum lateness. We use the weighted shortest processing time (WSPT) rule and the earliest due date (EDD) rule as heuristics for the general cases and analyze their worst-case error bounds. We also provide computational results to evaluate the performance of the heuristics. [Copyright &y& Elsevier]