Search

To link to full-text access for this article, visit this link: http://dx.doi.org/10.1016/j.ejor.2005.10.054 Byline: Ji-Bo Wang (a), Zun-Quan Xia (b) Keywords: Scheduling; Single machine; Controllable processing times Abstract: In this paper, we consider single machine scheduling problem in which job processing times are controllable variables with linear costs. We concentrate on two goals separately, namely, minimizing a cost function containing total completion time, total absolute differences in completion times and total compression cost; minimizing a cost function containing total waiting time, total absolute differences in waiting times and total compression cost. The problem is modelled as an assignment problem, and thus can be solved with the well-known algorithms. For the case where all the jobs have a common difference between normal and crash processing time and an equal unit compression penalty, we present an O(n log n) algorithm to obtain the optimal solution. Author Affiliation: (a) Department of Science, Shenyang Institute of Aeronautical Engineering, Shenyang 110034, People's Republic of China (b) Department of Applied Mathematics, Dalian University of Technology, Dalian 116024, People's Republic of China Article History: Received 3 March 2005; Accepted 5 October 2005

To link to full-text access for this article, visit this link: http://dx.doi.org/10.1016/j.ejor.2008.12.029 Byline: Linhui Sun (a), Linyan Sun (a), Kai Cui (a), Ji-Bo Wang (b) Keywords: Scheduling; Flow shop; Deteriorating jobs; Dominant machines Abstract: The main results in a recent paper [M. Cheng, S. Sun, L. He, Flow shop scheduling problems with deteriorating jobs on no-idle dominant machines, European Journal of Operational Research 183 (2007) 115-124] are incorrect because job processing times are variable due to deteriorating effect, which is not taken into account by the authors. In this note, we show first by counter-examples that the published results are incorrect, and then we provide corrected results. Author Affiliation: (a) Management School, The State Key Laboratory for Manufacturing System Engineering, Xi'an Jiaotong University, Xi'an 710049, People's Republic of China (b) School of Science, Shenyang Institute of Aeronautical Engineering, Shenyang 110136, People's Republic of China Article History: Received 3 September 2007; Accepted 22 December 2008

This paper deals with single machine scheduling problems with simple linear deterioration in which the processing time of a job is a simple linear function of its execution starting time. The objective is to determine the optimal schedule to minimize the weighted sum of the θ th ( θ is a positive integer number) power of waiting times. It is proved that the general problem can be solved in polynomial time. In addition, for the jobs with weak (strong) parallel chains and a series–parallel digraph precedence constraints, it is also proved that these problems can be solved in polynomial time, respectively. [ABSTRACT FROM AUTHOR]

Abstract: We study a single-machine scheduling and due window assignment problem, in which job processing times are defined by functions of their starting times (deteriorating effect) and positions in the sequence (learning effect). The problem is to determine the optimal due windows and the processing sequence simultaneously to minimize costs for earliness, tardiness, the window location, window size and makespan. We show that the problem remains polynomially solvable under the proposed model for two popular due window assignment methods: The slack due date assignment method (usually referred to as SLK) and the unrestricted due date assignment method (usually referred to as DIF). [Copyright &y& Elsevier]

Abstract: The single-machine scheduling problems with position and sum-of-processing-time based processing times are considered. The actual processing time of a job is defined by function of its scheduled position and total normal processing time of jobs in front of it in the sequence. We provide optimal solutions in polynomial time for some special cases of the makespan minimization and the total completion time minimization. We also show that an optimal schedule to be a V-shaped schedule in terms of the normal processing times of jobs for the total completion time minimization problem and the makespan minimization problem. [Copyright &y& Elsevier]

Abstract: The paper deals with machine scheduling problems with a general learning effect. By the general learning effect, we mean that the actual processing time of a job is not only a non-increasing function of the total weighted normal processing times of the jobs already processed, but also a non-increasing function of the job’s position in the sequence, where the weight is a position-dependent weight. We show that even with the introduction of a general learning effect to job processing times, some single machine scheduling problems are still polynomially solvable under the proposed model. We also show that some special cases of the flow shop scheduling problems can be solved in polynomial time. [Copyright &y& Elsevier]

Abstract: The purpose of this study is to explore the single-machine scheduling with the effects of exponential learning and general deterioration. By the effects of exponential learning and general deterioration, we meant that job processing time is decided by the functions of their starting time and positions in the sequence. Results showed that with the introduction of learning effect and deteriorating jobs to job processing time, single-machine makespan, and sum of completion time (square) minimization problems remained polynomially solvable, respectively. But for the following objective functions: the weighted sum of completion time and the maximum lateness, this paper proved that the weighted smallest basic processing time first (WSPT) rule and the earliest due date first (EDD) rule constructed the optimal sequence under some special cases, respectively. [Copyright &y& Elsevier]

Abstract: In this paper we consider single-machine scheduling problems with position-dependent processing times, i.e., jobs whose processing times are an increasing or decreasing function of their positions in a processing sequence. In addition, the jobs are related by parallel chains and a series–parallel graph precedence constraints, respectively. It is shown that for the problems of minimization of the makespan polynomial algorithms exist. [Copyright &y& Elsevier]

Abstract: We consider single-machine scheduling problems in which the processing time of a job is a function of its starting time and its resource allocation. The objective is to find the optimal sequence of jobs and the optimal resource allocation separately. We concentrate on two goals separately, namely, minimizing a cost function containing makespan, total completion time, total absolute differences in completion times and total resource cost; minimizing a cost function containing makespan, total waiting time, total absolute differences in waiting times and total resource cost. We show that the problems remain polynomially solvable under the proposed model. [Copyright &y& Elsevier]

Abstract: In this paper we consider a single-machine common due-window assignment scheduling problem with learning effect and deteriorating jobs. In this model, job processing times are defined by functions of their starting times and positions in the sequence. The window location and size, along with the associated job schedule that minimizes a certain cost function, are to be determined. This function is made up of costs associated with the window location, window size, earliness and tardiness. We show that the problem remains polynomially solvable under the proposed model. [Copyright &y& Elsevier]

Abstract: In this paper we consider identical parallel machines scheduling problems with a deteriorating maintenance activity. In this model, each machine has a deteriorating maintenance activity, that is, delaying the maintenance increases the time required to perform it. We need to make a decision on when to schedule the rate-modifying activities and the sequence of jobs to minimize some objective function. We concentrate on two goals separately, namely, minimizing the total absolute differences in completion times (TADC) and the total absolute differences in waiting times (TADW). We show that the problems remain polynomially solvable under the proposed model. [Copyright &y& Elsevier]

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 consider the single machine past-sequence-dependent (p-s-d) setup times scheduling problems with general position-dependent and time-dependent learning effects. By the general position-dependent and time-dependent learning effects, we mean that the actual processing time of a job is not only a function of the total normal processing times of the jobs already processed, but also a function of the job’s scheduled position. The setup times are proportional to the length of the already processed jobs. We consider the following objective functions: the makespan, the total completion time, the sum of the θth (θ ⩾0) power of job completion times, the total lateness, the total weighted completion time, the maximum lateness, the maximum tardiness and the number of tardy jobs. We show that the problems of makespan, the total completion time, the sum of the θth (θ ⩾0) power of job completion times and the total lateness can be solved by the smallest (normal) processing time first (SPT) rule, respectively. We also show that the total weighted completion time minimization problem, the maximum lateness minimization problem, maximum tardiness minimization problem and the number of tardy jobs minimization problem can be solved in polynomial time under certain conditions. [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 show that the main results in a recent paper by Zhang and Yan [X. Zhang and G. Yan, Machine scheduling problems with a general learning effect, Mathematical and Computer Modelling 51 (2010) 84–90] are incorrect as an important reason is missing, that is, the processing time of a job is variable according to a general learning effect. Here we point out these wrong results by a counter-example. In addition, we give a revised model with a general learning effect. We show that some single machine scheduling problems are still polynomially solvable under the revised model. We also show that some special cases of the flowshop scheduling problems can be solved in polynomial time under the revised model. [ABSTRACT FROM AUTHOR]

Abstract: In this paper, we consider the problem of simultaneous determination of optimal due dates and optimal schedule for the single machine problem with multiple common due dates. The penalty for a job is assumed to be a linear function of the due date and the earliness/tardiness for the job. The objective function is to minimize the total penalty for all jobs. We show that with the introduction of learning to job processing times the problem remains polynomially solvable for a given number of multiple common due dates. [Copyright &y& Elsevier]

Abstract: In this paper we consider single-machine scheduling problems with an exponential sum-of-actual-processing-time-based learning effect. By the exponential sum-of-actual-processing-time-based learning effect, we mean that the processing time of a job is defined by an exponential function of the sum of the actual processing times of the already processed jobs. For the proposed learning model, we show that under certain conditions, the makespan minimization problem, the sum of the th () powers of completion times minimization problem, and some special cases of the total weighted completion time minimization problem and the maximum lateness minimization problem all remain polynomially solvable. [ABSTRACT FROM AUTHOR]

Abstract: This paper considers single machine scheduling problems with group technology (GT) and deteriorating jobs. We consider the case of jobs whose processing times are a simple linear function of their starting time. The two objectives of scheduling problems are to minimize the weighted sum of squared completion times and the weighted sum of squared waiting times, respectively. We also provide polynomial time algorithms to solve these problems. [Copyright &y& Elsevier]

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 paper we consider the single machine scheduling problems with exponential sum-of-logarithm-processing-times based learning effect. By the exponential sum-of-logarithm-processing-times based learning effect, we mean that the processing time of a job is defined by an exponent function of the sum of the logarithm of the processing times of the jobs already processed. We consider the following objective functions: the makespan, the total completion time, the sum of the quadratic job completion times, the total weighted completion time and the maximum lateness. We show that the makespan minimization problem, the total completion time minimization problem and the sum of the quadratic job completion times minimization problem can be solved by the smallest (normal) processing time first (SPT) rule, respectively. We also show that the total weighted completion time minimization problem and the maximum lateness minimization problem can be solved in polynomial time under certain conditions. [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]

Abstract: In this paper we consider a single-machine scheduling problem with the effects of learning and deterioration. In this model, job processing times are defined by functions of their starting times and positions in the sequence. The problem is to determine an optimal combination of the due-date and schedule so as to minimize the sum of earliness, tardiness and due-date. We show that the problem remains polynomially solvable under the proposed model. [Copyright &y& Elsevier]

Abstract: In this note we consider some single-machine scheduling problems with decreasing time-dependent job processing times. Decreasing time-dependent job processing times means that its processing time is a non-increasing function of its execution start time. We present polynomial solutions for the sum of squared completion times minimization problem, and the sum of earliness penalties minimization problem subject to no tardy jobs, respectively. We also study two resource constrained scheduling problems under the same decreasing time-dependent job processing times model and present algorithms to find their optimal solutions. [Copyright &y& Elsevier]

Abstract: This paper studies the single machine scheduling problems with learning effect and deteriorating jobs simultaneously. In this model, the processing times of jobs are defined as functions of their starting times and positions in a sequence. It is shown that even with the introduction of learning effect and deteriorating jobs to job processing times, the makespan, the total completion time and the sum of the th power of completion times minimization problems remain polynomially solvable, respectively. But for the following objective functions: the total weighted completion time and the maximum lateness, this paper proves that the shortest weighted processing time first (WSPT) rule and the earliest due-date first (EDD) rule can construct the optimal sequence under some special cases, respectively. [Copyright &y& Elsevier]

Abstract: This paper deals with single-machine scheduling problems with decreasing linear deterioration, i.e., jobs whose processing times are a decreasing function of their starting times. In addition, the jobs are related by parallel chains and a series–parallel graph precedence constraints, respectively. It is shown that for the problems of minimization of the makespan, polynomial algorithms exist. [Copyright &y& Elsevier]

Abstract: In this paper we consider the single machine scheduling problem with exponential time-dependent learning effect and past-sequence-dependent (p-s-d) setup times. By the exponential time-dependent learning effect, we mean that the processing time of a job is defined by an exponent function of the total normal processing time of the already processed jobs. The setup times are proportional to the length of the already processed jobs. We consider the following objective functions: the makespan, the total completion time, the sum of the quadratic job completion times, the total weighted completion time and the maximum lateness. We show that the makespan minimization problem, the total completion time minimization problem and the sum of the quadratic job completion times minimization problem can be solved by the smallest (normal) processing time first (SPT) rule, respectively. We also show that the total weighted completion time minimization problem and the maximum lateness minimization problem can be solved in polynomial time under certain conditions. [Copyright &y& Elsevier]

Abstract: In this study we consider the single-machine scheduling problem 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 times of the already processed jobs. We prove that the shortest processing time (SPT) rule is optimal for the sum of completion times square minimization problem. We also show by examples that the optimal schedule for the classical version of the problem is not optimal in the presence of a sum-of-processing-times-based learning effect for the following three objective functions: the weighted sum of completion times, the maximum lateness and the number of tardy jobs. But for some special cases, we prove that the weighted shortest processing time (WSPT) rule, the earliest due date (EDD) rule and Moore’s algorithm can construct an optimal schedule for the problem to minimize these objective functions, respectively. [Copyright &y& Elsevier]

Abstract: This paper deals with some special cases of general, no-wait and no-idle permutation flow shop scheduling problems, respectively. Special cases means that the machines form an increasing series of dominant machines, a decreasing series of dominant machines, an increasing–decreasing series of dominant machines and a decreasing–increasing series of dominant machines. Efficient polynomial time algorithms for finding the optimal schedules to minimize discounted total weighted completion time are developed. [Copyright &y& Elsevier]

Abstract: This paper considers a two-machine flow shop scheduling problem with deteriorating jobs. By a deteriorating job, we mean that the processing time of a job is an increasing function of its execution start time. A simple linear deterioration function is assumed. The objective is to find a sequence that minimizes total completion time. Optimal solutions 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 results show that the proposed heuristic algorithm performs effectively and efficiently. [Copyright &y& Elsevier]

Abstract: In this paper, we consider a single machine scheduling problem with a common due date. Job processing times are controllable to the extent that they can be reduced, up to a certain limit, at a cost proportional to the reduction. The common due date, along with the associated job schedule that minimizes a certain cost function, are to be determined. This function is made up of costs associated with the common due date, processing time reduction as well as job absolute value in lateness. We show that the problem can be formulated as an assignment problem and thus can be solved with well-known algorithms. For the case that where all the jobs have a common difference between normal and crash processing time and an equal unit compression penalty, we present an O(n log n) algorithm to obtain the optimal solution. [Copyright &y& Elsevier]

Peripheral gangrene, characterized by distal ischemia of the extremities, is a rare complication in patients with tuberculosis (TB). We diagnosed a female patient with gangrene of her left toe caused by TB infection. She presented with fever, lymphadenectasis, and peripheral gangrene of the left toe. Lymph node biopsy confirmed tuberculous lymphadenitis and the computer tomography angiography showed vasculitis. The patient underwent antituberculous therapy and her condition was gradually improved. Although it is rare, TB should be considered as a possible cause of peripheral gangrene. [Copyright &y& Elsevier]

Abstract: In this paper we investigate a single machine scheduling problem with decreasing time-dependent processing times and group technology assumption. By the decreasing time-dependent processing times and group technology assumption, we mean that the group setup times and job processing times are both decreasing linear functions of their starting times. We want to minimize the makespan subject to release dates. We show that the problem can be solved in polynomial time. [Copyright &y& Elsevier]

Abstract: In this paper we consider several single-machine scheduling problems with general learning effects. By general learning effects, we mean that the processing time of a job depends not only on its scheduled position, but also on the total normal processing time of the jobs already processed. We show that the scheduling problems of minimization of the makespan, the total completion time and the sum of the θth () power of job completion times can be solved in polynomial time under the proposed models. We also prove that some special cases of the total weighted completion time minimization problem and the maximum lateness minimization problem can be solved in polynomial time. [Copyright &y& Elsevier]

Abstract: In this paper we consider the scheduling problem with a general exponential learning effect and past-sequence-dependent (p-s-d) setup times. By the general exponential learning effect, we mean that the processing time of a job is defined by an exponent function of the total weighted normal processing time of the already processed jobs and its position in a sequence, where the weight is a position-dependent weight. The setup times are proportional to the length of the already processed jobs. We consider the following objective functions: the makespan, the total completion time, the sum of the δ ⩾0th power of completion times, the total weighted completion time and the maximum lateness. We show that the makespan minimization problem, the total completion time minimization problem and the sum of the quadratic job completion times minimization problem can be solved by the smallest (normal) processing time first (SPT) rule, respectively. We also show that the total weighted completion time minimization problem and the maximum lateness minimization problem can be solved in polynomial time under certain conditions. [Copyright &y& Elsevier]

Abstract: In this paper we consider the single-machine scheduling problems with both learning and deterioration effects. By the effects of learning and deterioration, we mean that job processing times are defined by functions of their starting times and positions in the sequence. It is shown that even with the introduction of learning effect and deteriorating jobs to job processing times, single-machine makespan minimization problem and the sum of the θth power of job completion times minimization problem remain polynomially solvable, respectively. But for the following objective functions: the weighted sum of completion times and the maximum lateness, this paper proves that the WSPT rule and the EDD rule can construct the optimal sequence under some special cases, respectively. [Copyright &y& Elsevier]

Abstract: We consider a single-machine scheduling problem with linear decreasing deterioration in which the due dates are determined by the equal slack (SLK) method. By the linear decreasing deterioration, we mean that the job’s processing time is a decreasing function of its starting time. The objective is to minimize the total weighted earliness penalty subject to no tardy jobs. We prove that two special cases of the problem remain polynomially solvable. The first case is the problem with equally weighted monotonous penalty objective function and the other case is the problem with weighted linear penalty objective function. [Copyright &y& Elsevier]

A variety of 3-iodoindole and 3-iodobenzo[ b ]furan derivatives were conveniently prepared from the corresponding 2-alkynylanilines and 2-alkynylphenols through Ph 3 P-catalyzed iodocyclization in the presence of N -iodosuccinimide (NIS). This protocol provides a rapid access to 3-iodoindoles and 3-iodobenzo[ b ]furans in good to excellent yields under mild conditions. [ABSTRACT FROM AUTHOR]