Papers by Keyword: Single-Machine

Abstract: This paper explored single-machine rescheduling of new orders with both learning and deterioration effects consideration. According to the literature research, rescheduling means that a set of original jobs has already been scheduled to minimize classical objective, and later a new set of jobs arrives and creates a disruption. Two kinds of constraints, the maximum sequence disruption of the original jobs cannot exceed a fixed number and the maximum time disruption of the original jobs cannot exceed a known value, were examined. The objectives of this paper were to minimize total completion time based on the constraints respectively. We proved that both problems are solved in polynomial time algorithms.

Abstract: This paper studies the issue of rescheduling to allow for the unexpected arrival of new jobs, taking into account the effect of the disruptions on a previously planned optimal schedule. We consider the single-machine rescheduling problems with deteriorating jobs. Rescheduling means that a set of original jobs has already been scheduled to minimize some classical objective, then a new set of jobs arrives and creates a disruption. The objective is to minimize the total tardiness costs under a limit of the disruptions from the original scheduling. We propose polynomial time algorithms or some dynamic programming algorithms for each problem.

Abstract: The paper considers the due-date assignment problem with a non-linear deterioration in which the due dates are determined by the equal slack method. Here, the processing time of a job is defined by a non-linear function of total normal processing time of jobs in front of it in the sequence. The objective is to minimize the total tardiness penalties. According to the needs from the real world, the problem is divided into two cases, i.e., allowing with early jobs and no early jobs respectively. The related lemma, corollary and theorems for the problems are proposed and proved. At the same time, it shows that the problems in this paper can be solved in the polynomial times.

Abstract: In today’s highly competitive market, laser cutting which has a characteristic of “make to order” and high product variety is under pressure to reduce costs, to increase productivity and to respond to the rapidly changing demands from customers. To maintain the competitive advantage, companies need to have a real-time dynamic scheduling system, which can handle large combinations of jobs, allowing sequencing of jobs to achieve multi-objective goals. Motivated by a real-life scheduling problem in a sheet metal processing company in Malaysia, this research addressed single machine scheduling problem with sequence-dependent setup times and group technology assumption to minimize makespan and with the secondary objective of minimizing setup times. The focus of this paper is on developing a simple heuristic algorithm based dynamic scheduling system. This algorithm has been coded in vb.net and is integrated with a database system. The scheduling system developed is verified and validated by comparing to the actual production run. Results show that the algorithm model can find good solutions within short computational time.

Abstract: This paper considers single machine scheduling problem. The objective is to determine sum of earliness and tardiness cost has been minimized. The memetic algorithm is developed to solve this problem. To evaluate performance of memetic algorithm, the solution of propose method is compare with the optimal solution. The results show that the average percentage deviation is less than 10. Here, the computational time required by the MA is significantly less than the time required by the optimal solution method. This result is more emphasized as the problem size is getting larger.

Abstract: This paper considers the bicriteria scheduling problem of minimizing the total earliness and the total tardiness on a single machine with release dates. In view of the fact that the problem has been characterized as NP-Hard, we propose two approximation algorithms (labeled as ETA1 and ETA2) for solving the problem. The proposed algorithms were compared with the MA heuristic selected from the literature. The two criteria (the total earliness and the total tardiness) were aggregated together into a linear composite objective function (LCOF). The performances of the algorithms were evaluated based on both effectiveness and efficiency. The algorithms were tested on a set of 1200 randomly generated single machine scheduling problems. Experimental results show that both the ETA1 and ETA2 algorithms outperformed (in terms of effectiveness and efficiency) the MA heuristic under all the considered problem sizes. Also, the ETA1 algorithm outperformed the ETA2 algorithm when the number of jobs (n) ranges between 20 and 500.

Abstract: In this paper, a single-machine scheduling problem with simple linear deterioration was explored. By simple linear deterioration, we mean that the processing time of a job is a simple linear function of its execution starting time and its deterioration rate. The objective of this study was to find a schedule that minimizes the absolute value of maximum lateness, where the due date of jobs are a common due date. Given that the cases of common due date is a given constant and variable, we showed that the problem can be solved in polynomial time, respectively. Some extensions of the problem were also delineated.