• Previous Article
    Parameter identification techniques applied to an environmental pollution model
  • JIMO Home
  • This Issue
  • Next Article
    A modified scaled memoryless BFGS preconditioned conjugate gradient algorithm for nonsmooth convex optimization
April  2018, 14(2): 803-815. doi: 10.3934/jimo.2017076

Multi-machine scheduling with interval constrained position-dependent processing times

1. 

College of Economics and Management, Nanjing University of Aeronautics and Astronautics, Nanjing, 211106, China

2. 

Department of Information Management, National Formosa University, YunLin 63201, Taiwan

3. 

College of Economics and Management, Nanjing University of Aeronautics and Astronautics, Nanjing, 211106, China

* Corresponding author: Dar-Li Yang

Received  September 2016 Revised  December 2016 Published  September 2017

Fund Project: The first author is supported by the Fundamental Research Fund for the Central Universities No. XAA16077

This paper investigates multi-machine scheduling problems with interval constrained actual processing times. The actual processing time of each job is assumed to be restricted in a given interval otherwise the extra earliness or tardiness time should be used to patch up the flaw of job. The objectives are to find the optimal job sequence to minimize the total load of machines, the number of exceeding-interval jobs and the makespan of job schedule, respectively. This paper shows that both of the total load minimization problem and the exceeding job number minimization problem are polynomially solvable. For the makespan minimization problem, this paper proves that it is NP-hard, and proposes a fully polynomial time approximation scheme (FPTAS) for the case with two parallel machines.

Citation: Xianyu Yu, Dar-Li Yang, Dequn Zhou, Peng Zhou. Multi-machine scheduling with interval constrained position-dependent processing times. Journal of Industrial & Management Optimization, 2018, 14 (2) : 803-815. doi: 10.3934/jimo.2017076
References:
[1]

D. Biskup, Single-machine scheduling with learning considerations, European Journal of Operational Research, 115 (1999), 173-178. doi: 10.1016/S0377-2217(98)00246-X. Google Scholar

[2]

F. Bourgeois and J. C. Lassalle, An extension of the munkres algorithm for the assignment problem to rectangular matrices, Communications of the ACM, 14 (1971), 802-804. doi: 10.1145/362919.362945. Google Scholar

[3]

S. Browne and U. Yechiali, Scheduling deteriorating jobs on a single processor, Operations Research, 38 (1990), 495-498. Google Scholar

[4]

H. ChenC. Chu and J. M. Proth, Cyclic scheduling of a hoist with time window constraints, IEEE Transactions on Robotics and Automation, 14 (1998), 144-152. Google Scholar

[5]

Y. Cheng and S. Sun, Scheduling linear deteriorating jobs with rejection on a single machine, European Journal of Operational Research, 194 (2009), 18-27. doi: 10.1016/j.ejor.2007.11.047. Google Scholar

[6]

S. ChubanovM. Y. Kovalyov and E. Pesch, An fptas for a single-item capacitated economic lot-sizing problem with monotone cost structure, Mathematical Programming, 106 (2006), 453-466. doi: 10.1007/s10107-005-0641-0. Google Scholar

[7]

D. W. EngelsD. R. KargerS. G. KolliopoulosS. SenguptaR. Uma and J. Wein, Techniques for scheduling with rejection, Journal of Algorithms, 49 (2003), 175-191. doi: 10.1016/S0196-6774(03)00078-6. Google Scholar

[8]

G. FinkeA. Gara-AliM. L. EspinouseV. Jost and J. Moncel, Unified matrix approach to solve production-maintenance problems on a single machine, Omega, 66 (2017), 140-146. doi: 10.1016/j.omega.2016.02.005. Google Scholar

[9]

R. L. Graham, Bounds for certain multiprocessing anomalies, Bell System Technical Journal, 45 (1966), 1563-1581. doi: 10.1002/j.1538-7305.1966.tb01709.x. Google Scholar

[10]

J. N. D Gupta and S. K. Gupta, Single facility scheduling with nonlinear processing times, Computers & Industrial Engineering, 14 (1988), 387-393. doi: 10.1016/0360-8352(88)90041-1. Google Scholar

[11]

G. Hardy, J. Littlewood and G. Polya, Inequalities, Cambridge Univ. Press, london, 1965. Google Scholar

[12]

M. Ji and T. C. E. Cheng, Scheduling with job-dependent learning effects and multiple rate-modifying activities, Information Processing Letters, 110 (2010), 460-463. doi: 10.1016/j.ipl.2010.04.015. Google Scholar

[13]

M. JiC. J. Hsu and D.-L. Yang, Single-machine scheduling with deteriorating jobs and aging effects under an optional maintenance activity consideration, Journal of Combinatorial Optimization, 26 (2013), 437-447. doi: 10.1007/s10878-011-9415-1. Google Scholar

[14]

W. H. Kuo and D. L. Yang, Minimizing the makespan in a single-machine schedul-ing problem with the cyclic process of an aging effect, Journal of the Operational Re-search Society, 59 (2008), 416-420. Google Scholar

[15]

M. LiuF. ZhengC. Chu and J. Zhang, An fptas for uniform machine scheduling to minimize makespan with linear deterioration, Journal of Combinatorial Optimization, 23 (2012), 483-492. doi: 10.1007/s10878-010-9364-0. Google Scholar

[16]

G. Mosheiov, V-shaped policies for scheduling deteriorating jobs, Operations Re-search, 39 (1991), 979-991. doi: 10.1287/opre.39.6.979. Google Scholar

[17]

G. Mosheiov, A note: Multi-machine scheduling with general position-based de-terioration to minimize total load, International Journal of Production Economics, 135 (2012), 523-525. doi: 10.1016/j.ijpe.2011.09.005. Google Scholar

[18]

G. Mosheiov and J. B. Sidney, Scheduling with general job-dependent learning curves, European Journal of Operational Research, 147 (2003), 665-670. doi: 10.1016/S0377-2217(02)00358-2. Google Scholar

[19]

J. Munkres, Algorithms for the assignment and transportation problems, Journal of the Society for Industrial and Applied Mathematics, 5 (1957), 32-38. doi: 10.1137/0105003. Google Scholar

[20]

M. Pinedo, Scheduling, Springer-Verlag, New York, 2012. doi: 10.1007/978-1-4614-2361-4. Google Scholar

[21]

S. K. Sahni, Algorithms for scheduling independent tasks, Journal of the ACM, 23 (1976), 116-127. doi: 10.1145/321921.321934. Google Scholar

[22]

G. Steiner and R. Zhang, Revised delivery-time quotation in scheduling with tardi-ness penalties, Operations research, 59 (2011), 1504-1511. doi: 10.1287/opre.1110.0948. Google Scholar

[23]

G. J. Woeginger, When does a dynamic programming formulation guarantee the existence of a fully polynomial time approximation scheme (fptas)?, INFORMS Journal on Computing, 12 (2000), 57-74. doi: 10.1287/ijoc.12.1.57.11901. Google Scholar

[24]

P. XueY. Zhang and X. Yu, Single-machine scheduling with piece-rate mainte-nance and interval constrained position-dependent processing times, Applied Mathemat-ics and Computation, 226 (2014), 415-422. doi: 10.1016/j.amc.2013.10.034. Google Scholar

[25]

P. YanA. CheX. Cai and X. Tang, Two-phase branch and bound algorithm for robotic cells rescheduling considering limited disturbance, Computers & Operations Research, 50 (2014), 128-140. doi: 10.1016/j.cor.2014.04.002. Google Scholar

[26]

P. YanA. CheN. Yang and C. Chu, A tabu search algorithm with solution space partition and repairing procedure for cyclic robotic cell scheduling problem, International Journal of Production Research, 50 (2012), 6403-6418. doi: 10.1080/00207543.2011.645953. Google Scholar

[27]

P. YanC. ChuN. Yang and A. Che, A branch and bound algorithm for optimal cyclic scheduling in a robotic cell with processing time windows, International Journal of Production Research, 48 (2010), 6461-6480. doi: 10.1080/00207540903225205. Google Scholar

[28]

Y. YinT. ChengJ. XuS. R. Cheng and C. C. Wu, Single-machine schedul-ing with past-sequence-dependent delivery times and a linear deterioration, Journal of Industrial and Management Optimization, 9 (2013), 323-339. doi: 10.3934/jimo.2013.9.323. Google Scholar

[29]

X. Yu and Y. Zhang, Single machine scheduling with aging effect and upper-bounded actual processing times, Arabian Journal for Science and Engineering, 39 (2014), 1489-1495. doi: 10.1007/s13369-013-0716-9. Google Scholar

[30]

X. YuY. Zhang and K. Huang, Multi-machine scheduling with general position-based deterioration to minimize total load revisited, Information Processing Letters, 114 (2014), 399-404. doi: 10.1016/j.ipl.2014.02.009. Google Scholar

[31]

X. ZhangY. Yin and C. C. Wu, Scheduling with non-decreasing deterioration jobs and variable maintenance activities on a single machine, Engineering Optimization, 49 (2017), 84-97. doi: 10.1080/0305215X.2016.1163629. Google Scholar

[32]

Z. ZhouA. Che and P. Yan, A mixed integer programming approach for multi-cyclic robotic flowshop scheduling with time window constraints, Applied Mathematical Modelling, 36 (2012), 3621-3629. doi: 10.1016/j.apm.2011.10.032. Google Scholar

show all references

References:
[1]

D. Biskup, Single-machine scheduling with learning considerations, European Journal of Operational Research, 115 (1999), 173-178. doi: 10.1016/S0377-2217(98)00246-X. Google Scholar

[2]

F. Bourgeois and J. C. Lassalle, An extension of the munkres algorithm for the assignment problem to rectangular matrices, Communications of the ACM, 14 (1971), 802-804. doi: 10.1145/362919.362945. Google Scholar

[3]

S. Browne and U. Yechiali, Scheduling deteriorating jobs on a single processor, Operations Research, 38 (1990), 495-498. Google Scholar

[4]

H. ChenC. Chu and J. M. Proth, Cyclic scheduling of a hoist with time window constraints, IEEE Transactions on Robotics and Automation, 14 (1998), 144-152. Google Scholar

[5]

Y. Cheng and S. Sun, Scheduling linear deteriorating jobs with rejection on a single machine, European Journal of Operational Research, 194 (2009), 18-27. doi: 10.1016/j.ejor.2007.11.047. Google Scholar

[6]

S. ChubanovM. Y. Kovalyov and E. Pesch, An fptas for a single-item capacitated economic lot-sizing problem with monotone cost structure, Mathematical Programming, 106 (2006), 453-466. doi: 10.1007/s10107-005-0641-0. Google Scholar

[7]

D. W. EngelsD. R. KargerS. G. KolliopoulosS. SenguptaR. Uma and J. Wein, Techniques for scheduling with rejection, Journal of Algorithms, 49 (2003), 175-191. doi: 10.1016/S0196-6774(03)00078-6. Google Scholar

[8]

G. FinkeA. Gara-AliM. L. EspinouseV. Jost and J. Moncel, Unified matrix approach to solve production-maintenance problems on a single machine, Omega, 66 (2017), 140-146. doi: 10.1016/j.omega.2016.02.005. Google Scholar

[9]

R. L. Graham, Bounds for certain multiprocessing anomalies, Bell System Technical Journal, 45 (1966), 1563-1581. doi: 10.1002/j.1538-7305.1966.tb01709.x. Google Scholar

[10]

J. N. D Gupta and S. K. Gupta, Single facility scheduling with nonlinear processing times, Computers & Industrial Engineering, 14 (1988), 387-393. doi: 10.1016/0360-8352(88)90041-1. Google Scholar

[11]

G. Hardy, J. Littlewood and G. Polya, Inequalities, Cambridge Univ. Press, london, 1965. Google Scholar

[12]

M. Ji and T. C. E. Cheng, Scheduling with job-dependent learning effects and multiple rate-modifying activities, Information Processing Letters, 110 (2010), 460-463. doi: 10.1016/j.ipl.2010.04.015. Google Scholar

[13]

M. JiC. J. Hsu and D.-L. Yang, Single-machine scheduling with deteriorating jobs and aging effects under an optional maintenance activity consideration, Journal of Combinatorial Optimization, 26 (2013), 437-447. doi: 10.1007/s10878-011-9415-1. Google Scholar

[14]

W. H. Kuo and D. L. Yang, Minimizing the makespan in a single-machine schedul-ing problem with the cyclic process of an aging effect, Journal of the Operational Re-search Society, 59 (2008), 416-420. Google Scholar

[15]

M. LiuF. ZhengC. Chu and J. Zhang, An fptas for uniform machine scheduling to minimize makespan with linear deterioration, Journal of Combinatorial Optimization, 23 (2012), 483-492. doi: 10.1007/s10878-010-9364-0. Google Scholar

[16]

G. Mosheiov, V-shaped policies for scheduling deteriorating jobs, Operations Re-search, 39 (1991), 979-991. doi: 10.1287/opre.39.6.979. Google Scholar

[17]

G. Mosheiov, A note: Multi-machine scheduling with general position-based de-terioration to minimize total load, International Journal of Production Economics, 135 (2012), 523-525. doi: 10.1016/j.ijpe.2011.09.005. Google Scholar

[18]

G. Mosheiov and J. B. Sidney, Scheduling with general job-dependent learning curves, European Journal of Operational Research, 147 (2003), 665-670. doi: 10.1016/S0377-2217(02)00358-2. Google Scholar

[19]

J. Munkres, Algorithms for the assignment and transportation problems, Journal of the Society for Industrial and Applied Mathematics, 5 (1957), 32-38. doi: 10.1137/0105003. Google Scholar

[20]

M. Pinedo, Scheduling, Springer-Verlag, New York, 2012. doi: 10.1007/978-1-4614-2361-4. Google Scholar

[21]

S. K. Sahni, Algorithms for scheduling independent tasks, Journal of the ACM, 23 (1976), 116-127. doi: 10.1145/321921.321934. Google Scholar

[22]

G. Steiner and R. Zhang, Revised delivery-time quotation in scheduling with tardi-ness penalties, Operations research, 59 (2011), 1504-1511. doi: 10.1287/opre.1110.0948. Google Scholar

[23]

G. J. Woeginger, When does a dynamic programming formulation guarantee the existence of a fully polynomial time approximation scheme (fptas)?, INFORMS Journal on Computing, 12 (2000), 57-74. doi: 10.1287/ijoc.12.1.57.11901. Google Scholar

[24]

P. XueY. Zhang and X. Yu, Single-machine scheduling with piece-rate mainte-nance and interval constrained position-dependent processing times, Applied Mathemat-ics and Computation, 226 (2014), 415-422. doi: 10.1016/j.amc.2013.10.034. Google Scholar

[25]

P. YanA. CheX. Cai and X. Tang, Two-phase branch and bound algorithm for robotic cells rescheduling considering limited disturbance, Computers & Operations Research, 50 (2014), 128-140. doi: 10.1016/j.cor.2014.04.002. Google Scholar

[26]

P. YanA. CheN. Yang and C. Chu, A tabu search algorithm with solution space partition and repairing procedure for cyclic robotic cell scheduling problem, International Journal of Production Research, 50 (2012), 6403-6418. doi: 10.1080/00207543.2011.645953. Google Scholar

[27]

P. YanC. ChuN. Yang and A. Che, A branch and bound algorithm for optimal cyclic scheduling in a robotic cell with processing time windows, International Journal of Production Research, 48 (2010), 6461-6480. doi: 10.1080/00207540903225205. Google Scholar

[28]

Y. YinT. ChengJ. XuS. R. Cheng and C. C. Wu, Single-machine schedul-ing with past-sequence-dependent delivery times and a linear deterioration, Journal of Industrial and Management Optimization, 9 (2013), 323-339. doi: 10.3934/jimo.2013.9.323. Google Scholar

[29]

X. Yu and Y. Zhang, Single machine scheduling with aging effect and upper-bounded actual processing times, Arabian Journal for Science and Engineering, 39 (2014), 1489-1495. doi: 10.1007/s13369-013-0716-9. Google Scholar

[30]

X. YuY. Zhang and K. Huang, Multi-machine scheduling with general position-based deterioration to minimize total load revisited, Information Processing Letters, 114 (2014), 399-404. doi: 10.1016/j.ipl.2014.02.009. Google Scholar

[31]

X. ZhangY. Yin and C. C. Wu, Scheduling with non-decreasing deterioration jobs and variable maintenance activities on a single machine, Engineering Optimization, 49 (2017), 84-97. doi: 10.1080/0305215X.2016.1163629. Google Scholar

[32]

Z. ZhouA. Che and P. Yan, A mixed integer programming approach for multi-cyclic robotic flowshop scheduling with time window constraints, Applied Mathematical Modelling, 36 (2012), 3621-3629. doi: 10.1016/j.apm.2011.10.032. Google Scholar

[1]

Xianzhao Zhang, Dachuan Xu, Donglei Du, Cuixia Miao. Approximate algorithms for unrelated machine scheduling to minimize makespan. Journal of Industrial & Management Optimization, 2016, 12 (2) : 771-779. doi: 10.3934/jimo.2016.12.771

[2]

Cuixia Miao, Yuzhong Zhang. Scheduling with step-deteriorating jobs to minimize the makespan. Journal of Industrial & Management Optimization, 2019, 15 (4) : 1955-1964. doi: 10.3934/jimo.2018131

[3]

Ganggang Li, Xiwen Lu. Two-machine scheduling with periodic availability constraints to minimize makespan. Journal of Industrial & Management Optimization, 2015, 11 (2) : 685-700. doi: 10.3934/jimo.2015.11.685

[4]

Chengxin Luo. Single machine batch scheduling problem to minimize makespan with controllable setup and jobs processing times. Numerical Algebra, Control & Optimization, 2015, 5 (1) : 71-77. doi: 10.3934/naco.2015.5.71

[5]

Zhichao Geng, Jinjiang Yuan. Scheduling family jobs on an unbounded parallel-batch machine to minimize makespan and maximum flow time. Journal of Industrial & Management Optimization, 2018, 14 (4) : 1479-1500. doi: 10.3934/jimo.2018017

[6]

P. Liu, Xiwen Lu. Online scheduling of two uniform machines to minimize total completion times. Journal of Industrial & Management Optimization, 2009, 5 (1) : 95-102. doi: 10.3934/jimo.2009.5.95

[7]

Hongtruong Pham, Xiwen Lu. The inverse parallel machine scheduling problem with minimum total completion time. Journal of Industrial & Management Optimization, 2014, 10 (2) : 613-620. doi: 10.3934/jimo.2014.10.613

[8]

Bin Dan, Huali Gao, Yang Zhang, Ru Liu, Songxuan Ma. Integrated order acceptance and scheduling decision making in product service supply chain with hard time windows constraints. Journal of Industrial & Management Optimization, 2018, 14 (1) : 165-182. doi: 10.3934/jimo.2017041

[9]

Y. K. Lin, C. S. Chong. A tabu search algorithm to minimize total weighted tardiness for the job shop scheduling problem. Journal of Industrial & Management Optimization, 2016, 12 (2) : 703-717. doi: 10.3934/jimo.2016.12.703

[10]

Ran Ma, Jiping Tao. An improved 2.11-competitive algorithm for online scheduling on parallel machines to minimize total weighted completion time. Journal of Industrial & Management Optimization, 2018, 14 (2) : 497-510. doi: 10.3934/jimo.2017057

[11]

Peng Guo, Wenming Cheng, Yi Wang. A general variable neighborhood search for single-machine total tardiness scheduling problem with step-deteriorating jobs. Journal of Industrial & Management Optimization, 2014, 10 (4) : 1071-1090. doi: 10.3934/jimo.2014.10.1071

[12]

Jinjiang Yuan, Weiping Shang. A PTAS for the p-batch scheduling with pj = p to minimize total weighted completion time. Journal of Industrial & Management Optimization, 2005, 1 (3) : 353-358. doi: 10.3934/jimo.2005.1.353

[13]

Wen-Hung Wu, Yunqiang Yin, Wen-Hsiang Wu, Chin-Chia Wu, Peng-Hsiang Hsu. A time-dependent scheduling problem to minimize the sum of the total weighted tardiness among two agents. Journal of Industrial & Management Optimization, 2014, 10 (2) : 591-611. doi: 10.3934/jimo.2014.10.591

[14]

Chuanli Zhao. An fptas for the weighted number of tardy jobs minimization on a single machine with deteriorating jobs. Journal of Industrial & Management Optimization, 2017, 13 (2) : 587-593. doi: 10.3934/jimo.2016033

[15]

Alexander Khapalov. Controllability properties of a vibrating string with variable axial load. Discrete & Continuous Dynamical Systems - A, 2004, 11 (2&3) : 311-324. doi: 10.3934/dcds.2004.11.311

[16]

Soumya Kundu, Soumitro Banerjee, Damian Giaouris. Vanishing singularity in hard impacting systems. Discrete & Continuous Dynamical Systems - B, 2011, 16 (1) : 319-332. doi: 10.3934/dcdsb.2011.16.319

[17]

Frédéric Lebon, Raffaella Rizzoni. Modeling a hard, thin curvilinear interface. Discrete & Continuous Dynamical Systems - S, 2013, 6 (6) : 1569-1586. doi: 10.3934/dcdss.2013.6.1569

[18]

Viktor I. Gerasimenko, Igor V. Gapyak. Hard sphere dynamics and the Enskog equation. Kinetic & Related Models, 2012, 5 (3) : 459-484. doi: 10.3934/krm.2012.5.459

[19]

Sergei A. Avdonin, Boris P. Belinskiy. On controllability of a linear elastic beam with memory under longitudinal load. Evolution Equations & Control Theory, 2014, 3 (2) : 231-245. doi: 10.3934/eect.2014.3.231

[20]

Domokos Szász. Algebro-geometric methods for hard ball systems. Discrete & Continuous Dynamical Systems - A, 2008, 22 (1&2) : 427-443. doi: 10.3934/dcds.2008.22.427

2018 Impact Factor: 1.025

Metrics

  • PDF downloads (79)
  • HTML views (543)
  • Cited by (0)

Other articles
by authors

[Back to Top]