Search published articles


Showing 6 results for Single Machine
A Single Machine Sequencing Problem with Idle Insert: Simulated Annealing and Branch-and-Bound Methods
R. Tavakolimoghadam, M. Vasei,
Volume 19, Issue 4 (12-2008)
Abstract

  In this paper, a single machine sequencing problem is considered in order to find the sequence of jobs minimizing the sum of the maximum earliness and tardiness with idle times (n/1/I/ETmax). Due to the time complexity function, this sequencing problem belongs to a class of NP-hard ones. Thus, a special design of a simulated annealing (SA) method is applied to solve such a hard problem. To compare the associated results, a branch-and-bound (B&B) method is designed and the upper/lower limits are also introduced in this method. To show the effectiveness of these methods, a number of different types of problems are generated and then solved. Based on the results of the test problems, the proposed SA has a small error, and computational time for achieving the best result is very small.


Minimizing Total Weighted Tardiness with Drop Dead Dates in Single Machine Scheduling Problem
Mohammad Mahdavi Mazdeh, Ali Khan Nakhjavani , Abalfazl Zareei,
Volume 21, Issue 2 (5-2010)
Abstract

  This paper deals with minimization of tardiness in single machine scheduling problem when each job has two different due-dates i.e. ordinary due-date and drop dead date. The drop dead date is the date in which jobs’ weights rise sharply or the customer cancels the order. A linear programming formulation is developed for the problem and since the problem is known to be NP-hard, three heuristic algorithms are designed for the problem based on Tabu search mechanism. Extensive numerical experiments were conducted to observe and compare the behavior of the algorithms in solving the problem..


Genetic and Improved Shuffled Frog Leaping Algorithms for a 2-Stage Model of a Hub Covering Location Network
M. Mohammadi, R. Tavakkoli-Moghaddam, A. Ghodratnama , H. Rostami ,
Volume 22, Issue 3 (9-2011)
Abstract

 

  Hub covering location problem, Network design,

  Single machine scheduling, Genetic algorithm,

  Shuffled frog leaping algorithm

 

Hub location problems (HLP) are synthetic optimization problems that appears in telecommunication and transportation networks where nodes send and receive commodities (i.e., data transmissions, passengers transportation, express packages, postal deliveries, etc.) through special facilities or transshipment points called hubs. In this paper, we consider a central mine and a number of hubs (e.g., factories) connected to a number of nodes (e.g., shops or customers) in a network. First, the hub network is designed, then, a raw materials transportation from a central mine to the hubs (i.e., factories) is scheduled. In this case, we consider only one transportation system regarded as single machine scheduling. Furthermore, we use this hub network to solve the scheduling model. In this paper, we consider the capacitated single allocation hub covering location problem (CSAHCLP) and then present the mixed-integer programming (MIP) model. Due to the computational complexity of the resulted models, we also propose two improved meta-heuristic algorithms, namely a genetic algorithm and a shuffled frog leaping algorithm in order to find a near-optimal solution of the given problem. The performance of the solutions found by the foregoing proposed algorithms is compared with exact solutions of the mathematical programming model .


Minimizing a General Penalty Function on a Single Machine via Developing Approximation Algorithms and FPTASs
Kamran Kianfar, Ghasem Moslehi,
Volume 28, Issue 3 (9-2017)
Abstract

This paper addresses the Tardy/Lost penalty minimization on a single machine. According to this penalty criterion, if the tardiness of a job exceeds a predefined value, the job will be lost and penalized by a fixed value. Besides its application in real world problems, Tardy/Lost measure is a general form for popular objective functions like weighted tardiness, late work and tardiness with rejection and hence, the results of this study are applicable for them. Initially, we present two approximation algorithms. Then, two special cases of the main problem are considered. In the first case, all jobs have the same tardiness weights where an FPTAS is developed using the technique of “structuring the execution of an algorithm". The second special case occurs when none of the jobs can be early. For this case, a 2-approximation algorithm is developed as well as a dynamic programming algorithm which is converted to an FPTAS.


Minimizing the Number of Tardy Jobs in the Single Machine Scheduling Problem under Bimodal Flexible and Periodic Availability Constraints
Ghasem Moslehi, Omolbanin Mashkani,
Volume 29, Issue 1 (3-2018)
Abstract

In single machine scheduling problems with availability constraints, machines are not available for one or more periods of time. In this paper, we consider a single machine scheduling problem with flexible and periodic availability constraints. In this problem, the maximum continuous working time for each machine increases in a stepwise manner with two different values allowed. Also, the duration of unavailability for each period depends on the maximum continuous working time of the machine in that same period, again with two different values allowed. The objective is to minimize the number of tardy jobs. In the first stage, the complexity of the problem is investigated and a binary integer programming model, a heuristic algorithm and a branch-and-bound algorithm are proposed in a second stage. Computational results of solving 1680 sample problems indicate that the branch-and-bound algorithm is capable of not only solving problems of up to 20 jobs but also of optimally solving 94.76% of the total number of problems. Based on numerical results obtained, a mean average error of 2% is obtained for the heuristic algorithm.


Single machine preemptive scheduling Considering Energy Consumption and Predicting Machine failures with Data Mining Approach
Ali Qorbani, Yousef Rabbani, Reza Kamranrad,
Volume 34, Issue 4 (12-2023)
Abstract
Prediction of unexpected incidents and energy consumption are some industry issues and problems. Single machine scheduling with preemption and considering failures has been pointed out in this study. Its aim is to minimize earliness and tardiness penalties by using job expansion or compression methods. The present study solves this problem in two parts. The first part predicts failures and obtains some rules to correct the process, and the second includes the sequence of single-machine scheduling operations. The failure time is predicted using some machine learning algorithms includes: Logistic Regression, Decision Tree, Random Forest, Support Vector Machine (SVM), Naïve Bayes, and k-nearest neighbors. Results of comparing the algorithms, indicate that the decision tree algorithm outperformed other algorithms with a probability of 70% in predicting failure. In the second part, the problem is scheduled considering these failures and machine idleness in a single-machine scheduling manner to achieve an optimal sequence, minimize energy consumption, and reduce failures. The mathematical model for this problem has been presented by considering processing time, machine idleness, release time, rotational speed and torque, failure time, and machine availability after repair and maintenance. The results of the model solving, concluded that the relevant mathematical model could schedule up to 8 jobs within a reasonable time and achieve an optimal sequence, which could reduce costs, energy consumption, and failures. Moreover, it is suggested that further studies use this approach for other types of scheduling, including parallel machine scheduling and flow job shop scheduling. Metaheuristic algorithms can be used for larger dimensions. 

Page 1 from 1